Quelles sont les caractéristiques des listes chaînées ?

La caractéristique de la liste chaînée est d'utiliser un ensemble d'unités de stockage arbitraires pour stocker les éléments de données de la liste linéaire. Par conséquent, afin d'exprimer la relation logique entre chaque élément de données et ses éléments de données successeurs directs, pour les éléments de données, en plus du stockage En plus de ses propres informations, il est également nécessaire de stocker des informations indiquant son successeur immédiat.

Caractéristiques

Liste chaînée unique, la fin de la flèche est le nœud

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 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 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!