La collection LinkedList<T>

1. Présentation

Dans une liste chaînée, on a un pointeur vers une liste d’éléments dans laquelle chaque élément pointe sur l’élément suivant et est pointé par l’élément précédent. Dans une liste doublement chaînée, chaque élément pointe à la fois sur l’élément suivant et sur l’élément précédent. De ce fait, on peut parcourir la liste d’éléments dans les deux sens.

Voici une représentation possible d’une double liste chaînée en Rust :

images/11EP2.png

Représentation d’une LinkedList<i64>

Comme on le voit dans cet exemple d’une liste doublement chaînée d’entiers, en l’occurrence une LinkedList<i64>, celle-ci est en quelque sorte composée d’un triplet :

  • Un pointeur vers le début de liste « avant ».

  • Un pointeur vers la fin de liste « arrière ».

  • La longueur (ou la taille) de la liste doublement chaînée.

Chaque élément de la liste contient sa valeur (ici une valeur entière, mais ce pourrait être une instance de structure par exemple) et un ou deux pointeurs :

  • Les deux extrémités ont un seul pointeur vers l’élément suivant.

  • Les autres éléments ont deux pointeurs sur chacun de leurs deux...

Pour consulter la suite, découvrez le livre suivant :
couv_EIRUST.png
60-signet.svg
En version papier
20-ecran_lettre.svg
En version numérique
41-logo_abonnement.svg
En illimité avec l'abonnement ENI
130-boutique.svg
Sur la boutique officielle ENI
Précédent
La collection VecDeque<T>
Suivant
La collection BinaryHeap<T>