Qu'est-ce qu'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. 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. Chaque nœud se compose de deux parties : l'une est le champ de données qui stocke les éléments de données et l'autre est le champ de pointeur qui stocke l'adresse du nœud suivant. Par rapport à la structure de séquence de tableaux linéaires, l'opération est compliquée. Puisqu'il n'est pas nécessaire de la stocker dans l'ordre, la liste chaînée peut atteindre une complexité O(1) lors de l'insertion, ce qui est beaucoup plus rapide qu'une autre liste linéaire, une liste séquentielle, mais la recherche d'un nœud ou l'accès à un nœud numéroté spécifique nécessite O( n) le temps, et les complexités temporelles correspondantes des tableaux linéaires et des tableaux séquentiels sont respectivement O(logn) et O(1).

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 réaliser une gestion dynamique flexible de la mémoire. Cependant, la liste chaînée perd l'avantage de la lecture aléatoire du tableau. Dans le même temps, la liste chaînée a une surcharge d'espace 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 conventionnel organise les éléments associés peut être différente de l'ordre dans lequel ces éléments de données sont disposés en mémoire ou sur le disque, et l'accès aux données nécessite souvent de basculer entre différentes dispositions. Les listes chaînées permettent l'insertion et la suppression de nœuds à n'importe quel emplacement de la liste, mais n'autorisent pas un accès aléatoire. Il existe de nombreux types de listes chaînées : les listes chaînées unidirectionnelles, les listes chaînées doublement et les listes chaînées circulaires. Les listes chaînées peuvent être implémentées dans une variété de langages de programmation. Les types de données intégrés de langages comme Lisp et Scheme incluent l'accès et le fonctionnement des listes chaînées. Les langages de programmation ou orientés objet tels que C, C++ et Java s'appuient sur des outils mutables pour générer des listes chaînées.

Caractéristiques

La caractéristique de la représentation de stockage liée d'une table linéaire est d'utiliser un ensemble d'unités de stockage arbitraires pour stocker les éléments de données de la table linéaire (cet ensemble d'unités de stockage peut être continu ou différent) continu). 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 informations forment un « nœud » (comme le montre la figure à côté de l'aperçu), 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é le 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,,..., sont liés en séquence, est appelée une représentation de stockage liée d'une liste linéaire, car chaque nœud de ce type de liste chaînée ne contient qu'un seul pointeur. field , on l'appelle donc également liste chaînée unique ou liste chaînée linéaire.

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!