Quelle structure de données est une liste chaînée ?

Une liste chaînée est une structure de stockage non continue et non séquentielle sur une unité de stockage physique. L'ordre logique des éléments de données est réalisé via l'ordre des liens du pointeur dans la liste chaînée ; structure d'une liste linéaire, cela s'appelle une "liste chaînée". Chaque élément de données de la liste chaînée est composé de deux parties : 1. Les informations elles-mêmes, appelées « champ de données » 2. Le pointeur vers le successeur direct, appelé « champ de pointeur ». Ces deux parties d'informations forment la structure de stockage des éléments de données, appelés « nœuds » ; n nœuds sont liés les uns aux autres via des champs de pointeur pour former une liste chaînée.

L'environnement d'exploitation de ce tutoriel : système Windows 7, ordinateur Dell G3.

La structure des données est la façon dont les ordinateurs stockent et organisent les données. Une structure de données fait référence à un ensemble d'éléments de données qui entretiennent une ou plusieurs relations spécifiques les uns avec les autres. Souvent, des structures de données soigneusement sélectionnées peuvent conduire à une plus grande efficacité de fonctionnement ou de stockage. Les structures de données sont souvent liées à des algorithmes de récupération et à des techniques d'indexation efficaces.

La 链表

liste chaînée dans la structure de données est une structure de stockage non continue et non séquentielle sur l'unité de stockage physique. L'ordre logique des éléments de données est réalisé via l'ordre des liens du pointeur dans. la liste chaînée. Une liste chaînée se compose d'une série de nœuds (chaque élément de la liste chaînée est appelé un nœud) et les nœuds peuvent être générés dynamiquement au moment de l'exécution.

Les données qui se succèdent dans la structure logique ne sont pas côte à côte comme une table de séquence lorsqu'elles sont réellement stockées. Au contraire, les données sont réparties de manière aléatoire à différents endroits de la mémoire. Cette structure de stockage est appelée stockage lié d'une liste linéaire.

En raison du stockage décentralisé, afin de refléter la relation logique entre les éléments de données, chaque élément de données doit être équipé d'un pointeur pour pointer vers son élément successeur direct lors du stockage, c'est-à-dire que chaque élément de données pointe vers le suivant. éléments (le dernier pointe vers NULL (vide)).

Comme le montre l'image ci-dessus, lorsque chaque élément de données est lié à son élément de données suivant avec un pointeur, une chaîne est formée et la tête de cette chaîne est située au premier élément de données. Une telle méthode de stockage. est le stockage en chaîne.

Le tableau généré par la structure de stockage liée de la liste linéaire est appelé « liste liée ».

La composition des éléments de données dans la liste chaînée

Chaque élément lui-même est composé de deux parties :

• L'information elle-même est appelée "champ de données"

• Le pointeur vers le successeur immédiat ; est appelé « champ de pointeur ».

Ces deux parties d'informations forment la structure de stockage des éléments de données, qui sont appelés « nœuds ». n nœuds sont liés les uns aux autres via des champs de pointeur pour former une liste chaînée.

Nœud principal, pointeur principal et premier nœud

Nœud principal : Parfois, un nœud supplémentaire est ajouté avant le premier nœud de la liste chaînée, et le champ de données du nœud n'est généralement pas stocké de données (dans Dans certains cas, des informations telles que la longueur de la liste chaînée peuvent également être stockées), ce nœud est appelé nœud principal.

Si le champ de pointeur du nœud principal est NULL, cela indique que la liste chaînée est une liste vide. Le nœud principal n'est pas nécessaire pour la liste chaînée Lorsque vous traitez certains problèmes, l'ajout d'un nœud principal à la liste chaînée simplifiera le problème.

Premier nœud : Le nœud où se trouve le premier élément de la liste chaînée. C'est le premier nœud après le nœud principal.

Pointeur de tête : pointe toujours vers la position du premier nœud dans la liste chaînée (si la liste chaînée a un nœud de tête, le pointeur de tête pointe vers le nœud de tête ; sinon, le pointeur de tête pointe vers le premier nœud).

La différence entre le nœud principal et le pointeur principal : le pointeur principal est un pointeur qui pointe vers le nœud principal ou le premier nœud de la liste chaînée ; le nœud principal est un nœud réel qui contient des champs de données et un domaine de pointeurs. La manifestation directe des deux dans le programme est que le pointeur principal est uniquement déclaré mais aucun espace de stockage n'est alloué, et le nœud principal est déclaré et la mémoire physique réelle d'un nœud est allouée.

L'utilisation de la structure de liste chaînée peut surmonter l'inconvénient de la liste chaînée de tableau selon laquelle la taille des données doit être connue à l'avance. La structure de liste chaînée peut utiliser pleinement l'espace mémoire de l'ordinateur et obtenir une mémoire dynamique flexible. gestion. Cependant, la liste chaînée perd l'avantage de la lecture aléatoire du tableau, et en même temps, la surcharge spatiale de la liste chaînée est relativement importante en raison de l'augmentation du champ de pointeur du nœud. L'avantage le plus évident d'une liste chaînée est que la façon dont un tableau régulier organise les éléments associés peut être différente de l'ordre dans lequel ces éléments de données sont organisés en mémoire ou sur le disque, et l'accès aux données nécessite souvent de basculer entre différentes dispositions.

Caractéristiques

La caractéristique de la représentation de stockage lié d'un tableau linéaire est d'utiliser un ensemble d'unités de stockage arbitraires pour stocker les éléments de données du tableau linéaire (cet ensemble d'unités de stockage peut être continu ou discontinu). Par conséquent, afin de représenter la relation logique entre chaque élément de données et son élément de données successeur direct, pour l'élément de données, en plus de stocker ses propres informations, il est également nécessaire de stocker des informations indiquant son successeur direct (c'est-à-dire le stockage de l'emplacement successeur direct). Ces deux parties d'informations forment un « nœud » (comme le montre la figure ci-dessous), qui représente un élément de données dans le tableau linéaire. Un inconvénient de la représentation de stockage lié des tableaux linéaires est que pour trouver un nombre, vous devez repartir de zéro, ce qui est très gênant.

Selon la situation, vous pouvez également concevoir vous-même d'autres extensions de la liste chaînée. Cependant, les données ne sont généralement pas ajoutées aux arêtes, car les points et les arêtes de la liste chaînée sont essentiellement en correspondance biunivoque (sauf pour le premier ou le dernier nœud, mais aucune circonstance particulière ne se produira). Cependant, un cas particulier est que si la liste chaînée prend en charge l'inversion des pointeurs avant et arrière dans une section de la liste chaînée, il peut être plus pratique d'ajouter une marque d'inversion au bord.

Pour les listes chaînées non linéaires, vous pouvez vous référer à d'autres structures de données associées, telles que des arbres et des graphiques. Il existe également une structure de données basée sur plusieurs listes chaînées linéaires : les listes de sauts. La vitesse des opérations de base telles que l'insertion, la suppression et la recherche peut atteindre O(nlogn), identique à celle d'un arbre binaire équilibré.

Le domaine qui stocke les informations sur les éléments de données est appelé domaine de données (que le nom de domaine soit des données), et le domaine qui stocke l'emplacement de stockage du successeur direct est appelé le domaine de pointeur (que le nom de domaine soit le suivant). Les informations stockées dans le champ du pointeur sont également appelées pointeur ou chaîne.

Une liste chaînée composée de N nœuds qui représentent respectivement,,..., sont liés en séquence, est appelée une représentation de stockage liée d'une liste linéaire puisque chaque nœud de ce type de liste chaînée ne contient qu'un seul champ de pointeur, il. est également appelée liste chaînée unique ou liste chaînée linéaire.

Insertion et suppression de nœuds des listes liées

Les listes liées permettent l'insertion et la suppression de nœuds à n'importe quelle position sur la table, mais l'accès aléatoire n'est pas autorisé.

1. Insérez un nœud dans la liste chaînée

• Insérez le nœud principal dans la liste chaînée, qui est divisé en 3 types selon la position d'insertion :

• Insérez dans la tête de la liste chaînée, cela c'est-à-dire le nœud principal et le premier élément Au milieu du nœud ;

• est inséré quelque part au milieu de la liste chaînée ;

• est inséré à la toute fin de la liste chaînée ;

Bien que les emplacements d'insertion soient différents, ils utilisent tous la même technique d'insertion. Il est divisé en deux étapes, comme le montre l'image ci-dessus :

Pointez le pointeur suivant du nouveau nœud vers le nœud après la position d'insertion ;

• Pointez le pointeur suivant du nœud avant la position d'insertion ; le nœud d'insertion ;

• Conseils : Lorsque vous effectuez une opération d'insertion, vous devez d'abord trouver le nœud précédent à la position d'insertion, c'est-à-dire trouver le nœud 1. Le nœud correspondant 2 peut être représenté par le pointeur suivant. du nœud 1. De cette façon, passez d'abord à l'étape 1, puis passez à l'étape 2. Il n'est pas nécessaire d'ajouter d'autres pointeurs auxiliaires pendant le processus de mise en œuvre.

2. Supprimer un nœud de la liste chaînée

Lorsque vous devez supprimer un nœud de la liste chaînée, vous devez effectuer deux étapes :

Sélectionner le nœud dans la liste chaînée ;

• Libérer manuellement ; le nœud Cliquez pour recycler l'espace mémoire occupé par le nœud ;

• Pour plus de connaissances connexes, veuillez visiter la colonne

  FAQ
 !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!