Quel est le concept et la structure de la liste chaînée dans la structure de données Java ?

1. Le concept de liste chaînée

Concept : La liste chaînée est une structure de stockage physique non continue et non séquentielle. via la liste chaînée. Implémentation de la séquence de liens du pointeur

1 La 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).

2. Les nœuds peuvent être générés dynamiquement (malloc) au moment de l'exécution.

3. Chaque nœud comprend 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 (voir la section 1.2 Nœud pour plus de détails).

4. Par rapport à la structure de séquence de liste linéaire, l'opération de liste chaînée est compliquée. Cependant, comme elle n'a pas besoin d'être stockée dans l'ordre, la liste chaînée peut atteindre une complexité O(1) lors de l'insertion, ce qui est beaucoup plus rapide que la liste séquentielle, cependant, la recherche d'un nœud ou l'accès à un nœud avec un numéro spécifique nécessite ; O(n) time, et La liste de séquences n'a besoin que de O(1)

2 Nœud

La liste chaînée est composée de nœuds, et chaque nœud prend la forme de. une structure. Les premières variables de la structure sont données selon les besoins. La dernière variable est un pointeur de ce type de structure, utilisé pour stocker la première adresse du nœud suivant«

Le nœud de liste chaînée est divisé en deux champs. #🎜🎜 #Data domain : stocke diverses données réelles
Pointer domain : stocke l'adresse du nœud suivant

(l'image montre le position sentinelle Liste chaînée du nœud principal)

3. Scénarios d'utilisation des listes chaînées

Les listes linéaires conviennent lorsque

besoin d'insérer ou de supprimer fréquemment des éléments de données#🎜 🎜# Adopter une structure de stockage en chaîne. Parce que pour une liste chaînée, l'insertion ou la suppression de données nécessite uniquement de créer un nœud, de saisir des données, de modifier le pointeur et de connecter le nœud à une certaine position dans la liste chaînée ; L'insertion d'une donnée peut nécessiter le déplacement d'autres données, ce qui est très complexe.

4. Classification des listes chaînées et structures couramment utilisées

Bien la combinaison Il existe un total de 8 types de listes chaînées parmi lesquelles choisir, mais les plus couramment utilisées dans la pratique sont

Headless unidirectionnel non cyclique

liste chaînée et Headed two- façon circulaire liste chaînée. 1. Liste chaînée acyclique unidirectionnelle sans tête : communément appelée « liste chaînée unique ». La structure est simple et n’est généralement pas utilisée uniquement pour stocker des données. En fait, il s'agit plutôt d'une sous-structure d'autres structures de données (telles que des compartiments de hachage, des listes de contiguïté de graphiques, des structures de chaînes de pile, etc.)

2 Liste chaînée circulaire bidirectionnelle : la structure la plus complexe. , Généralement utilisé pour stocker les données séparément. La plupart des listes chaînées réellement utilisées sont des listes chaînées circulaires bidirectionnelles. Bien que la structure soit la plus complexe, cette structure apporte de nombreux avantages.

5. Comparaison avec une liste séquentielle

Liste chaînée :

La liste chaînée relie des données discrètes dans une table via des nœuds. accès aux données.

Table de séquence :

La table de séquence stocke les données en ouvrant une mémoire continue (directement à l'aide d'un tableau ou d'un malloc puis d'une extension de réallocation). Mais comme

realloc

l'expansion est divisée en expansion in situ et expansion hors site, la première est moins coûteuse, tandis que la seconde nécessite non seulement la copie des données, mais également libérer l'ancien espace lors de l'expansion. De plus, lors de l'expansion, il sera généralement étendu à 2 fois la capacité d'origine. Une expansion trop fréquente entraînera facilement une perte d'espace. Le type de données du nœud peut être un type c standard ou un type de structure défini par l'utilisateur.

Objet de comparaison

Liste de séquenceListe liéeContinuDiscontinuInsérer ou supprimer des donnéesIl peut être nécessaire de déplacer les données, la complexité est O(n)Il suffit de modifier le pointeur# 🎜🎜## 🎜🎜#pushTable de séquence dynamique : l'espace n'est pas suffisant et doit être agrandiIl n'y a pas de concept de "capacité", et les nouveaux nœuds sont directement alloués lors de la poussée insertion et suppression fréquentes de données#🎜 🎜#

# 🎜🎜#		Espace de stockage
# 🎜 🎜#

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!