Java LinkedList : Guide Complet avec Exemples

Java LinkedList

Découvrez comment exploiter Java LinkedList pour une manipulation efficace des données, avec des exemples de code pratiques et des insights sur les bonnes pratiques.

La classe LinkedList du framework de collections Java implémente une liste doublement chaînée. Chaque élément, ou nœud, contient trois champs :

• prev – référence au nœud précédent (null pour le premier élément)
• next – référence au nœud suivant (null pour le dernier élément)
• data – la valeur réelle stockée dans le nœud

---

Création d'un LinkedList Java

Instanciez un LinkedList avec un type d'élément spécifique :

LinkedList<Type> list = new LinkedList<>();

Exemples :

// Liste d'entiers
LinkedList<Integer> numbers = new LinkedList<>();
// Liste de chaînes
LinkedList<String> words = new LinkedList<>();

---

Exemple : Créer un LinkedList en Java

import java.util.LinkedList;
class Main {
    public static void main(String[] args){
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Cow");
        System.out.println("LinkedList: " + animals);
    }
}

Sortie

LinkedList: [Dog, Cat, Cow]

Ce code démontre un LinkedList basique nommé animals peuplé avec trois éléments via add().

---

Fonctionnement d'un LinkedList Java

Contrairement aux tableaux, les nœuds sont dispersés en mémoire et liés entre eux. Le diagramme ci-dessous illustre trois nœuds et leurs connexions.

• Dog – premier nœud, prev = null, next = Cat
• Cat – nœud du milieu, prev = Dog, next = Cow
• Cow – dernier nœud, prev = Cat, next = null

Pour plus de détails, voir l'article Linked List.

---

Méthodes Clés de LinkedList

Voici les opérations les plus fréquemment utilisées :

• Ajouter des éléments
• Accéder aux éléments
• Mettre à jour des éléments
• Supprimer des éléments

---

1. Ajout d'Éléments

Utilisez add() pour ajouter un nœud, en spécifiant optionnellement un index :

import java.util.LinkedList;
class Main {
    public static void main(String[] args){
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Cow");
        System.out.println("LinkedList: " + animals);
        animals.add(1, "Horse");
        System.out.println("LinkedList Mis à Jour: " + animals);
    }
}

Sortie

LinkedList: [Dog, Cat, Cow] LinkedList Mis à Jour: [Dog, Horse, Cat, Cow]

Le second add() insère "Horse" à l'index 1, décalant les éléments suivants.

---

2. Accès aux Éléments

Récupérez un élément par index avec get() :

import java.util.LinkedList;
class Main {
    public static void main(String[] args){
        LinkedList<String> languages = new LinkedList<>();
        languages.add("Python");
        languages.add("Java");
        languages.add("JavaScript");
        System.out.println("LinkedList: " + languages);
        String str = languages.get(1);
        System.out.print("Élément à l'index 1: " + str);
    }
}

Sortie

LinkedList: [Python, Java, JavaScript] Élément à l'index 1: Java

L'itération peut aussi être effectuée via iterator() ou listIterator() pour un parcours avancé.

---

3. Mise à Jour d'Éléments

Remplacez un élément à un index spécifique en utilisant set() :

import java.util.LinkedList;
class Main {
    public static void main(String[] args){
        LinkedList<String> languages = new LinkedList<>();
        languages.add("Java");
        languages.add("Python");
        languages.add("JavaScript");
        languages.add("Java");
        System.out.println("LinkedList: " + languages);
        languages.set(3, "Kotlin");
        System.out.println("LinkedList Mis à Jour: " + languages);
    }
}

Sortie

LinkedList: [Java, Python, JavaScript, Java] LinkedList Mis à Jour: [Java, Python, JavaScript, Kotlin]

---

4. Suppression d'Éléments

Supprimez un élément par index avec remove() :

import java.util.LinkedList;
class Main {
    public static void main(String[] args){
        LinkedList<String> languages = new LinkedList<>();
        languages.add("Java");
        languages.add("Python");
        languages.add("JavaScript");
        languages.add("Kotlin");
        System.out.println("LinkedList: " + languages);
        String removed = languages.remove(1);
        System.out.println("Élément Supprimé: " + removed);
        System.out.println("LinkedList Mis à Jour: " + languages);
    }
}

Sortie

LinkedList: [Java, Python, JavaScript, Kotlin] Élément Supprimé: Python Nouveau LinkedList: [Java, JavaScript, Kotlin]

---

Autres Méthodes Utiles

Méthode	Description
contains()	Vérifie si une valeur existe
indexOf()	Index de la première occurrence
lastIndexOf()	Index de la dernière occurrence
clear()	Supprime tous les éléments
iterator()	Fournit un Iterator

---

LinkedList comme Queue et Deque

Puisque LinkedList implémente Queue et Deque, il supporte les opérations FIFO et LIFO. Méthodes courantes :

Méthode	Description
addFirst()	Ajouter au début
addLast()	Ajouter à la fin
getFirst()	Regarder le début
getLast()	Regarder la fin
removeFirst()	Dépiler le début
removeLast()	Dépiler la fin
peek()	Voir le début sans suppression
poll()	Récupérer et supprimer le début
offer()	Enfiler à la fin

Exemple : LinkedList comme Queue

import java.util.LinkedList;
import java.util.Queue;
class Main {
    public static void main(String[] args){
        Queue<String> languages = new LinkedList<>();
        languages.add("Python");
        languages.add("Java");
        languages.add("C");
        System.out.println("LinkedList: " + languages);
        String first = languages.peek();
        System.out.println("Élément Accédé: " + first);
        String removed = languages.poll();
        System.out.println("Élément Supprimé: " + removed);
        System.out.println("LinkedList après poll(): " + languages);
        languages.offer("Swift");
        System.out.println("LinkedList après offer(): " + languages);
    }
}

Sortie

LinkedList: [Python, Java, C] Élément Accédé: Python Élément Supprimé: Python LinkedList après poll(): [Java, C] LinkedList après offer(): [Java, C, Swift]

Exemple : LinkedList comme Deque

import java.util.LinkedList;
import java.util.Deque;
class Main {
    public static void main(String[] args){
        Deque<String> animals = new LinkedList<>();
        animals.add("Cow");
        System.out.println("LinkedList: " + animals);
        animals.addFirst("Dog");
        System.out.println("LinkedList après addFirst(): " + animals);
        animals.addLast("Zebra");
        System.out.println("LinkedList après addLast(): " + animals);
        animals.removeFirst();
        System.out.println("LinkedList après removeFirst(): " + animals);
        animals.removeLast();
        System.out.println("LinkedList après removeLast(): " + animals);
    }
}

Sortie

LinkedList: [Cow] LinkedList après addFirst(): [Dog, Cow] LinkedList après addLast(): [Dog, Cow, Zebra] LinkedList après removeFirst(): [Cow, Zebra] LinkedList après removeLast(): [Cow]

---

Itération sur un LinkedList

La boucle for-each améliorée offre un moyen concis de parcourir les éléments :

import java.util.LinkedList;
class Main {
    public static void main(String[] args){
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Cow");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);
        System.out.println("Accès aux éléments de la linked list:");
        for(String animal: animals){
            System.out.print(animal + ", ");
        }
    }
}

Sortie

LinkedList: [Cow, Cat, Dog] Accès aux éléments de la linked list: Cow, Cat, Dog,

---

LinkedList vs ArrayList

Les deux classes implémentent List, mais diffèrent dans les caractéristiques de performance :

LinkedList	ArrayList
Implémente List, Queue, Deque	Implémente List
Nœud stocke prev, data, next	Un élément par slot de tableau
Structure doublement chaînée	Tableau redimensionnable
Insertions/suppressions O(1) quand position connue	Insertions après un index nécessitent décalage O(n)
Accès aléatoire nécessite parcours O(n)	Accès direct par index O(1)

---

Note : Vous pouvez instancier un LinkedList via l'une de ses interfaces :

// via List
List<String> animals1 = new LinkedList<>();
// via Queue
Queue<String> animals2 = new LinkedList<>();
// via Deque
Deque<String> animals3 = new LinkedList<>();

Lorsqu'on utilise une référence d'interface, seules les méthodes définies par cette interface sont disponibles.