What is a Doubly Linked List?

Une liste doublement chaînée est une séquence de nœuds où chaque nœud contient une valeur et deux pointeurs : prev vers le nœud précédent, et next vers le nœud suivant. La liste elle-même garde la trace des deux extrémités, la tête (premier nœud) et la queue (dernier nœud).

Les deux pointeurs par nœud et la référence supplémentaire tail nous apportent beaucoup. L'ajout à la fin est désormais en O(1) (on saute directement à tail au lieu de parcourir la chaîne), et la suppression du dernier nœud est également en O(1) (car nous pouvons atteindre l'avant-dernier nœud à partir de tail.prev). Le compromis est une consommation de mémoire plus importante par nœud, ainsi que plus de pointeurs à synchroniser lors de chaque insertion et suppression.

Les cinq opérations principales sur une liste doublement chaînée sont :

1. AddFirst : Ajouter une valeur au début de la liste.
2. AddLast : Ajouter une valeur à la fin de la liste (O(1) !).
3. Get : Retourner la valeur à un index donné.
4. RemoveLast : Supprimer le dernier nœud (O(1) !).
5. Size : Retourner le nombre de nœuds actuellement stockés.

Créons d'abord une classe Node, puis construisons la DoublyLinkedList par-dessus !