Quelle idée la classe LinkedList en Java met-elle en œuvre?

LinkedList implémente une liste doublement chaînée (doubly linked list).

• Chaque élément (nœud) contient des références à l’élément précédent et suivant dans la séquence.
• Il stocke des références au premier (head) et au dernier (tail) élément de la liste.
• Permet d’insérer et de supprimer efficacement des éléments au début, à la fin et au milieu de la liste (avec une complexité O(1) si la référence au nœud est connue, ou O(n) lors de la recherche par index).
• N’est pas efficace pour un accès arbitraire par index (nécessite une traversée séquentielle, complexité O(n)).
• Implémente les interfaces List et Deque, ce qui permet de l’utiliser comme une liste, une pile ou une file.

Comparaison avec ArrayList:

Caractéristique	LinkedList	ArrayList
Structure interne	Liste doublement chaînée	Tableau dynamique
Ajout/Suppression	O(1) (au début/fin ou par référence au nœud), O(n) (par index)	O(1) (à la fin), O(n) (au début/en milieu)
Accès arbitraire	O(n)	O(1)
Utilisation mémoire	Plus (stocke des références)	Moins (si pas besoin d’expansion)