Fonctionnement interne de LinkedList
Explorez la structure de nœuds doublement chaînés de LinkedList et ses caractéristiques de complexité temporelle.
Fonctionnement interne de LinkedList est une leçon Java Academy gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Java Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Java Academy comprend 4 leçons au total.
Structure interne de LinkedList
La LinkedList de Java est une liste doublement chaînée : chaque nœud contient une référence vers le nœud précédent et le nœud suivant, ainsi que la valeur de l'élément. Contrairement à ArrayList, elle ne possède pas de tableau de stockage : la mémoire est allouée pour chaque nœud.
class Node<T> {
T data;
Node<T> prev;
Node<T> next;
Node(T data) { this.data = data; }
}Profil de complexité temporelle
Les caractéristiques de performance de LinkedList diffèrent considérablement de celles d'ArrayList :
- addFirst / addLast : O(1)
- get(index) : O(n) — il faut parcourir la liste depuis la tête ou la queue
- remove(index) : O(n) pour trouver l'élément, puis O(1) pour le délier
- Parcours avec un itérateur : O(n)
Utilisez LinkedList lorsque vous avez besoin d'insérer fréquemment en tête ou en queue, et non d'un accès aléatoire.
Créer et parcourir une LinkedList
La création d'une LinkedList et son parcours suivent la même interface List que vous connaissez déjà. La différence réside dans la structure interne.
import java.util.LinkedList;
LinkedList<String> list = new LinkedList<>();
list.add("Alice");
list.add("Bob");
list.add("Carol");
for (String name : list) {
System.out.println(name);
}
System.out.println("First: " + list.getFirst()); // Alice
System.out.println("Last: " + list.getLast()); // CaroladdFirst, addLast, removeFirst, removeLast
LinkedList expose des opérations sur la tête et la queue que ArrayList ne propose pas efficacement :
LinkedList<Integer> nums = new LinkedList<>();
nums.addLast(10); // [10]
nums.addLast(20); // [10, 20]
nums.addFirst(5); // [5, 10, 20]
System.out.println(nums.removeFirst()); // 5 → [10, 20]
System.out.println(nums.removeLast()); // 20 → [10]Déliaison d'un Node : suppression en O(1) après la recherche
Une fois que vous disposez d'une référence vers un nœud, obtenue via un itérateur, la suppression est en O(1), car il suffit de mettre à jour les pointeurs next/prev : aucun décalage d'éléments comme avec ArrayList.
import java.util.*;
LinkedList<String> tasks = new LinkedList<>(List.of("A","B","C","D"));
Iterator<String> it = tasks.iterator();
while (it.hasNext()) {
String t = it.next();
if (t.equals("B") || t.equals("D")) {
it.remove(); // O(1) unlink
}
}
System.out.println(tasks); // [A, C]Surcoût mémoire par rapport à ArrayList
Chaque nœud de LinkedList contient deux références supplémentaires, prev et next, ainsi qu'une référence vers l'élément, soit environ 48 octets par entrée sur une JVM 64 bits. ArrayList stocke uniquement la référence vers l'élément, soit 8 octets, dans un tableau contigu.
Pour les grands ensembles de données principalement consultés, ArrayList est généralement plus efficace pour le cache et utilise moins de mémoire.
Opérations sur une deque : pile et file
LinkedList implémente l'interface Deque, ce qui permet de l'utiliser à la fois comme une pile et comme une file.
import java.util.LinkedList;
import java.util.Deque;
// As a Queue (FIFO)
Deque<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
System.out.println(queue.poll()); // first
// As a Stack (LIFO)
Deque<String> stack = new LinkedList<>();
stack.push("bottom");
stack.push("top");
System.out.println(stack.pop()); // topPrésentation de PriorityQueue
PriorityQueue est une file fondée sur un tas, dans laquelle le plus petit élément, selon l'ordre naturel ou le comparateur, est toujours retiré en premier. Elle n'est NOT pas fondée sur une liste chaînée : elle utilise un tableau représentant un tas binaire.
import java.util.PriorityQueue;
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(40);
pq.offer(10);
pq.offer(25);
System.out.println(pq.poll()); // 10 (smallest)
System.out.println(pq.poll()); // 25
System.out.println(pq.poll()); // 40PriorityQueue avec un comparateur personnalisé
Transmettez un Comparator pour inverser l'ordre ou trier selon un champ personnalisé :
import java.util.*;
record Task(String name, int priority) {}
PriorityQueue<Task> tasks = new PriorityQueue<>(
Comparator.comparingInt(Task::priority).reversed() // highest first
);
tasks.offer(new Task("Low", 1));
tasks.offer(new Task("High", 10));
tasks.offer(new Task("Med", 5));
while (!tasks.isEmpty()) {
System.out.println(tasks.poll().name());
}
// High, Med, LowChoisir entre LinkedList et ArrayList
Règle générale :
- Utilisez ArrayList pour l'accès aléatoire, le parcours et la plupart des situations.
- Utilisez LinkedList lorsque vous avez besoin d'insérer ou de supprimer fréquemment en O(1) aux deux extrémités, sans accès par indice.
- Utilisez PriorityQueue lorsque vous avez besoin d'un traitement ordonné, par exemple pour la planification de tâches ou l'algorithme de Dijkstra.
Pièges courants
Évitez d'appeler get(i) dans une boucle sur une LinkedList : le coût total est O(n²) :
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) list.add(i);
// BAD: O(n^2) — each get(i) traverses from head
for (int i = 0; i < list.size(); i++) {
int val = list.get(i); // slow!
}
// GOOD: O(n) — use iterator
for (int val : list) {
// process val
}Vérification rapide
Quelle opération de LinkedList est en O(1), quelle que soit la taille de la liste ?
Récapitulatif : LinkedList et deque
Points essentiels :
- LinkedList est une liste doublement chaînée dont les opérations en tête et en queue sont en O(1)
- L'accès aléatoire, avec get/set par indice, est en O(n)
- Elle implémente Deque et peut être utilisée comme pile ou comme file
- PriorityQueue fournit un traitement ordonné par tas
- Préférez ArrayList dans la plupart des cas d'utilisation : LinkedList est particulièrement adaptée aux modifications fréquentes en tête ou en queue
Questions Fréquemment Posées
La leçon « Fonctionnement interne de LinkedList » est-elle gratuite ?
Oui — le texte complet de « Fonctionnement interne de LinkedList » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Java Academy, passe à CoddyKit PRO. Le cours Java Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Fonctionnement interne de LinkedList » ?
Explorez la structure de nœuds doublement chaînés de LinkedList et ses caractéristiques de complexité temporelle. Tu pratiques Java Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Java Academy ?
Aucune expérience préalable n'est requise. Java Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Fonctionnement interne de LinkedList » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Java Academy ?
Oui. Chaque leçon Java Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Fonctionnement interne de LinkedList
- Opérations sur une deque : pile et file
- LinkedList et ArrayList : compromis
- PriorityQueue pour le traitement ordonné