Java LinkedList

LinkedList<E> est une liste doublement chaînée : chaque élément vit dans son propre nœud sur le tas, avec un pointeur vers le nœud suivant et un pointeur vers le nœud précédent. Cela lui donne un profil de performance inverse à celui de ArrayList : l'insertion et la suppression aux extrémités sont en O(1), mais get(i) doit parcourir la liste depuis un bout jusqu'à l'index — O(n). La classe est également la seule List intégrée de Java qui implémente aussi Deque<E>, ce qui lui permet de doubler en tant que file d'attente. Ce chapitre explique quand cette combinaison est le bon outil, et la liste (légèrement plus longue) des cas où elle ne l'est pas.

La structure de données

Chaque élément est un nœud :

node:  prev ←—— element ——→ next

La liste conserve deux références de champs — first et last — et un compteur size. Pour ajouter à l'une ou l'autre extrémité, vous allouez un nœud, vous le raccordez en ajustant deux pointeurs, et vous incrémentez size. Pas de tableau, pas de redimensionnement, pas de mémoire inutilisée. C'est là tout l'attrait.

Le coût se manifeste partout ailleurs :

• Chaque élément paie pour un objet nœud — trois références et un en-tête d'objet. La surcharge mémoire par élément est bien plus élevée que le tableau plat d'ArrayList.
• get(i), set(i, x), add(i, x), remove(i) doivent tous parcourir la liste depuis l'extrémité la plus proche. Ainsi, list.get(size/2) est en O(n/2). Pour les longues listes, cela se cumule rapidement.
• La localité de cache est médiocre — les nœuds sont dispersés dans le tas, donc la traversée manque le cache CPU et ralentit même quand l'algorithme semble linéaire.

Quand LinkedList est le bon choix

La réponse honnête en 2026 : **rarement en tant que List, parfois en tant que Deque, presque jamais pour « accélérer les insertions ». ** Le folklore « utilisez LinkedList parce que vous allez insérer » n'a pas bien vieilli — pour la plupart des charges de travail, la convivialité du cache d'ArrayList et son ajout en O(1) amorti surpasse la navigation supplémentaire par pointeurs d'une liste chaînée, même quand l'algorithme appelle parfois add(0, x). Les cas où LinkedList gagne réellement :

• Vous avez besoin d'un Deque (ajout/suppression aux deux extrémités) et n'avez pas déjà un ArrayDeque à portée. ArrayDeque est plus rapide ; LinkedList est plus familier.
• Vous conservez des références persistantes à des nœuds spécifiques (via ListIterator) et souhaitez une insertion/suppression en O(1) à ces positions exactes. C'est le cas d'utilisation classique des listes chaînées dans les manuels — et cela survient presque jamais dans le Java quotidien.
• Vous souhaitez une implémentation de Queue qui expose également des méthodes List pour l'inspection. Exemple concret : une file de tâches qui est occasionnellement vidée dans un journal.

Pour « une liste à laquelle j'ajoute des éléments et que je lis par index », utilisez ArrayList. Pour « une file ou un deque », utilisez ArrayDeque. LinkedList se situe entre les deux et est rarement le meilleur choix pour l'un ou l'autre.

Créer une instance et l'utiliser comme List

La moitié List de l'API est identique à ArrayList :

List<String> tasks = new LinkedList<>();
tasks.add("compile");
tasks.add("test");
tasks.add(0, "lint");          // O(1) — at the head
String first = tasks.get(0);   // O(1) — head
String last  = tasks.get(tasks.size() - 1);   // O(1) — tail
String mid   = tasks.get(tasks.size() / 2);   // O(n/2) — has to walk

Le constructeur n'a pas de paramètre de capacité — il n'y a rien à pré-dimensionner, car les nœuds sont alloués un à la fois.

L'utiliser comme Queue et Deque

Parce que LinkedList implémente à la fois Queue<E> et Deque<E>, vous obtenez les méthodes de file en plus des méthodes List :

Deque<String> stack = new LinkedList<>();
stack.push("a");          // adds to head
stack.push("b");
String top = stack.pop(); // removes from head → "b"

Queue<String> jobs = new LinkedList<>();
jobs.offer("j1");         // adds to tail
jobs.offer("j2");
String next = jobs.poll();// removes from head → "j1"

Si votre besoin est purement une « file FIFO » ou une « pile LIFO », déclarez la variable comme Queue<E> ou Deque<E> — et préférez new ArrayDeque<>() comme implémentation. L'interface est la même ; l'implémentation basée sur un tableau est mesurably plus rapide.

Itération et ConcurrentModificationException

Même modèle fail-fast qu'ArrayList. Muter pendant une boucle for-each lève une exception :

LinkedList<Integer> xs = new LinkedList<>(List.of(1, 2, 3, 4));
for (int x : xs) if (x % 2 == 0) xs.remove(Integer.valueOf(x));  // throws

removeIf et l'Iterator.remove() explicite sont les deux formes sûres — identiques au chapitre ArrayList. La particularité intéressante de LinkedList est le ListIterator : comme l'itérateur conserve une référence directe au nœud courant, ses méthodes add et remove sont véritablement en O(1). Si vous avez vraiment besoin d'une insertion rapide à une position lors de l'itération, LinkedList.listIterator() est l'API qui tient la promesse du manuel.

Sécurité des threads

Même situation qu'ArrayList : aucune. Utilisez Collections.synchronizedList(new LinkedList<>()) pour un verrouillage global, ou — bien mieux — un ConcurrentLinkedDeque si votre cas d'utilisation est vraiment une file concurrente.

La comparaison avec ArrayDeque en un paragraphe

Quand vous utilisez LinkedList comme file ou pile, regardez d'abord ArrayDeque. ArrayDeque est un tableau circulaire — pas de nœud par élément, pas de navigation par pointeurs, pas de règles de rejet de null à mémoriser. Sur de grandes charges de travail réelles avec des piles/files, il surpasse généralement LinkedList — parfois par une large marge — car il évite un nœud de tas et un en-tête par élément et garde ses données contiguës en mémoire. Il n'implémente pas List, ce qui est son seul vrai inconvénient. (Ne sur-interprétez pas un micro-benchmark dans un sens ou dans l'autre ; voir l'exemple travaillé ci-dessous.)

Un exemple travaillé : la même tâche, deux structures de données

Le programme ci-dessous construit la même file avec ArrayList, LinkedList et ArrayDeque — pousse vers une extrémité, sort de l'autre 200 000 fois — et affiche le temps d'horloge pour chacun. Lisez les chiffres en contexte : il s'agit d'un micro-benchmark approximatif à exécution unique sur une JVM froide, pas d'un résultat rigoureux, donc traitez l'ordre relatif — et non les millisecondes exactes — comme la leçon. ArrayList est dramatiquement plus lent que les deux autres car remove(0) est en O(n), donc la boucle de vidage est quadratique. LinkedList et ArrayDeque sont tous deux rapides : chacun effectue un travail en O(1) en tête de liste. Lequel des deux prend l'avantage dépend de la machine, du JIT et du boxing d'Integer — c'est exactement pourquoi vous ne devriez jamais vous appuyer sur un benchmark aussi petit pour choisir entre eux.

Deux enseignements à retenir :

• Les deux premiers timings montrent pourquoi il ne faut jamais indexer une LinkedList dans une boucle. La forme for-each parcourt la liste une fois en O(n) ; la forme par index la parcourt une fois par index, vous donnant O(n²). Pour 10 000 éléments, c'est déjà douloureux ; pour 100 000, ce sont des secondes.
• Les trois timings de file montrent la vraie division : elle est entre ArrayList (vidage quadratique) et les deux structures en O(1) en tête, pas entre LinkedList et ArrayDeque. Une fois que vous avez écarté ArrayList pour le travail de file, préférez ArrayDeque de toute façon — il n'alloue pas de nœud par élément et a une bien meilleure localité de cache sur les files importantes et de longue durée, qu'une boucle de démarrage à froid de 200 000 éléments n'expose pas complètement. La seule raison véritablement légitime d'utiliser LinkedList est « je veux un Deque et une List », et même cela est rare.

La suite

LinkedList et ArrayList sont les deux implémentations de List polyvalentes intéressantes. La troisième — plus ancienne, synchronisée, principalement historique — est Vector. Savoir pourquoi ce n'est pas le bon choix dans un nouveau code fait partie de la maîtrise du framework.

Pratique