Listes chaînées en Java - java.util.LinkedList

LinkedList — Listes chaînées en Java

  Prérequis

Maîtriser les concepts de base des collections Java. Comprendre le fonctionnement d'ArrayList. Connaître les génériques et l'interface List.

  Objectifs

Comprendre la structure de données des listes chaînées et leur implémentation en Java avec LinkedList. Savoir choisir entre ArrayList et LinkedList selon les besoins. Maîtriser les méthodes spécifiques aux listes chaînées (addFirst, addLast, removeFirst, removeLast, etc.).

1. Qu'est-ce qu'une LinkedList ?

2. Hiérarchie et déclaration

import java.util.LinkedList;  // ou import java.util.*;

// Constructeur par défaut
LinkedList<String> noms = new LinkedList<>();

// À partir d'une autre collection
LinkedList<Integer> nombres = new LinkedList<>(autreCollection);

// Polymorphisme (via l'interface List)
List<String> liste = new LinkedList<>();

// Polymorphisme (via l'interface Deque)
Deque<String> deque = new LinkedList<>();

3. Méthodes principales

3.1 Méthodes héritées de List

3.2 Méthodes spécifiques aux listes chaînées (Deque)

4. Exemples d'utilisation

  Exemple 1 — Opérations de base

import java.util.LinkedList;

public class Test {
    public static void main(String[] args) {
        LinkedList<String> link = new LinkedList<>();

        // Ajout d'éléments
        link.add("Mostafa");
        link.add("Ismail");
        link.add("Dounia");
        link.add("Badr");
        link.add("Omar");

        // Ajout spécifique aux LinkedList
        link.addLast("Mohamed");   // Ajoute à la fin
        link.addFirst("Fatima");   // Ajoute au début
        link.add(1, "Haitam");     // Ajoute à l'index 1

        System.out.println("Contenu original : " + link);

        // Suppression d'éléments
        link.remove("Badr");        // Suppression par objet
        link.remove(2);             // Suppression par index

        System.out.println("Après suppression : " + link);

        // Suppression du premier et du dernier
        link.removeFirst();
        link.removeLast();

        System.out.println("Après suppression premier/dernier : " + link);

        // Modification d'un élément
        String val = link.get(2);
        link.set(2, val + " (modifié)");

        System.out.println("Après modification : " + link);
    }
}

Contenu original : [Fatima, Haitam, Mostafa, Ismail, Dounia, Badr, Omar, Mohamed]
Après suppression : [Fatima, Haitam, Ismail, Dounia, Omar, Mohamed]
Après suppression premier/dernier : [Haitam, Ismail, Dounia, Omar]
Après modification : [Haitam, Ismail, Dounia (modifié), Omar]

5. LinkedList comme pile (Stack)

  Exemple 2 — Utilisation comme pile (LIFO)

import java.util.LinkedList;

public class Pile {
    public static void main(String[] args) {
        LinkedList<Integer> pile = new LinkedList<>();

        // Empiler (push)
        pile.addFirst(10);
        pile.addFirst(20);
        pile.addFirst(30);
        System.out.println("Pile après push : " + pile);

        // Dépiler (pop)
        int sommet = pile.removeFirst();
        System.out.println("Élément dépilé : " + sommet);
        System.out.println("Pile après pop : " + pile);

        // Consulter le sommet (peek)
        System.out.println("Sommet de la pile : " + pile.getFirst());
    }
}

Pile après push : [30, 20, 10]
Élément dépilé : 30
Pile après pop : [20, 10]
Sommet de la pile : 20

6. LinkedList comme file (Queue)

  Exemple 3 — Utilisation comme file (FIFO)

import java.util.LinkedList;
import java.util.Queue;

public class File {
    public static void main(String[] args) {
        // Utilisation de l'interface Queue
        Queue<String> file = new LinkedList<>();

        // Enfiler (offer / add)
        file.offer("Client 1");
        file.offer("Client 2");
        file.offer("Client 3");
        System.out.println("File : " + file);

        // Défiler (poll / remove)
        String client = file.poll();
        System.out.println("Client traité : " + client);
        System.out.println("File après traitement : " + file);

        // Consulter la tête (peek)
        System.out.println("Prochain client : " + file.peek());
    }
}

File : [Client 1, Client 2, Client 3]
Client traité : Client 1
File après traitement : [Client 2, Client 3]
Prochain client : Client 2

7. Parcours d'une LinkedList

  Exemple 4 — Différentes façons de parcourir

import java.util.LinkedList;
import java.util.Iterator;
import java.util.ListIterator;

public class Parcours {
    public static void main(String[] args) {
        LinkedList<String> langages = new LinkedList<>();
        langages.add("Java");
        langages.add("Python");
        langages.add("JavaScript");
        langages.add("C++");

        // 1. Boucle for classique
        System.out.println("=== Boucle for classique ===");
        for (int i = 0; i < langages.size(); i++) {
            System.out.println(langages.get(i));  // O(n) par accès
        }

        // 2. Boucle for-each (recommandée)
        System.out.println("\n=== Boucle for-each ===");
        for (String lang : langages) {
            System.out.println(lang);
        }

        // 3. Avec Iterator
        System.out.println("\n=== Iterator ===");
        Iterator<String> it = langages.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }

        // 4. Avec ListIterator (parcours bidirectionnel)
        System.out.println("\n=== ListIterator (ordre inverse) ===");
        ListIterator<String> lit = langages.listIterator(langages.size());
        while (lit.hasPrevious()) {
            System.out.println(lit.previous());
        }

        // 5. Avec forEach() + lambda
        System.out.println("\n=== forEach() avec lambda ===");
        langages.forEach(lang -> System.out.println(lang));
    }
}

8. ArrayList vs LinkedList — Quand utiliser quoi ?

9. Exemple complet — Gestion de playlist musicale

  Exemple 5 — Playlist avec navigation (liste doublement chaînée)

import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Scanner;

class Chanson {
    private String titre;
    private String artiste;
    private int duree;  // secondes

    public Chanson(String titre, String artiste, int duree) {
        this.titre = titre;
        this.artiste = artiste;
        this.duree = duree;
    }

    public String getTitre() { return titre; }
    public String getArtiste() { return artiste; }
    public int getDuree() { return duree; }

    @Override
    public String toString() {
        return String.format("%s - %s (%d:%02d)", artiste, titre, duree / 60, duree % 60);
    }
}

public class Playlist {
    private LinkedList<Chanson> playlist;
    private ListIterator<Chanson> iterator;
    private boolean avancer;

    public Playlist() {
        playlist = new LinkedList<>();
        iterator = playlist.listIterator();
        avancer = true;
    }

    public void ajouterChanson(Chanson chanson) {
        playlist.add(chanson);
        System.out.println("Ajouté : " + chanson);
    }

    public void ajouterApresCourante(Chanson chanson) {
        if (!playlist.isEmpty()) {
            if (avancer && iterator.hasNext()) {
                iterator.next();
            } else if (!avancer && iterator.hasPrevious()) {
                iterator.previous();
            }
            iterator.add(chanson);
            System.out.println("Ajouté après la chanson courante : " + chanson);
        } else {
            playlist.add(chanson);
            System.out.println("Ajouté à la playlist vide : " + chanson);
        }
    }

    public void chansonSuivante() {
        if (!avancer) {
            // Si on reculait, il faut avancer d'abord
            if (iterator.hasNext()) iterator.next();
            avancer = true;
        }
        if (iterator.hasNext()) {
            Chanson chanson = iterator.next();
            System.out.println("Lecture : " + chanson);
        } else {
            System.out.println("Fin de la playlist.");
        }
    }

    public void chansonPrecedente() {
        if (avancer) {
            if (iterator.hasPrevious()) iterator.previous();
            avancer = false;
        }
        if (iterator.hasPrevious()) {
            Chanson chanson = iterator.previous();
            System.out.println("Lecture : " + chanson);
        } else {
            System.out.println("Début de la playlist.");
        }
    }

    public void afficherPlaylist() {
        if (playlist.isEmpty()) {
            System.out.println("Playlist vide.");
            return;
        }
        System.out.println("\n=== PLAYLIST ===");
        for (int i = 0; i < playlist.size(); i++) {
            System.out.printf("%d. %s%n", i + 1, playlist.get(i));
        }
        System.out.println("Total : " + playlist.size() + " chanson(s)\n");
    }

    public void supprimerChanson(int index) {
        if (index >= 0 && index < playlist.size()) {
            Chanson supprimee = playlist.remove(index);
            System.out.println("✗ Supprimé : " + supprimee);
            // Réinitialiser l'itérateur
            iterator = playlist.listIterator();
            avancer = true;
        } else {
            System.out.println("Index invalide !");
        }
    }

    public static void main(String[] args) {
        Playlist playlist = new Playlist();
        Scanner scanner = new Scanner(System.in);
        int choix;

        // Ajout de quelques chansons par défaut
        playlist.ajouterChanson(new Chanson("Bohemian Rhapsody", "Queen", 355));
        playlist.ajouterChanson(new Chanson("Imagine", "John Lennon", 183));
        playlist.ajouterChanson(new Chanson("Hotel California", "Eagles", 391));

        do {
            System.out.println("\n╔════════════════════════════════════╗");
            System.out.println("║         LECTEUR MUSICAL            ║");
            System.out.println("╠════════════════════════════════════╣");
            System.out.println("║ 1. Lecture suivante                ║");
            System.out.println("║ 2. Lecture précédente              ║");
            System.out.println("║ 3. Ajouter une chanson             ║");
            System.out.println("║ 4. Ajouter après chanson courante  ║");
            System.out.println("║ 5. Supprimer une chanson           ║");
            System.out.println("║ 6. Afficher la playlist            ║");
            System.out.println("║ 7. Quitter                         ║");
            System.out.println("╚════════════════════════════════════╝");
            System.out.print("Votre choix : ");
            choix = scanner.nextInt();
            scanner.nextLine();

            switch (choix) {
                case 1:
                    playlist.chansonSuivante();
                    break;
                case 2:
                    playlist.chansonPrecedente();
                    break;
                case 3:
                    System.out.print("Titre : ");
                    String titre = scanner.nextLine();
                    System.out.print("Artiste : ");
                    String artiste = scanner.nextLine();
                    System.out.print("Durée (secondes) : ");
                    int duree = scanner.nextInt();
                    playlist.ajouterChanson(new Chanson(titre, artiste, duree));
                    break;
                case 4:
                    System.out.print("Titre : ");
                    titre = scanner.nextLine();
                    System.out.print("Artiste : ");
                    artiste = scanner.nextLine();
                    System.out.print("Durée (secondes) : ");
                    duree = scanner.nextInt();
                    playlist.ajouterApresCourante(new Chanson(titre, artiste, duree));
                    break;
                case 5:
                    playlist.afficherPlaylist();
                    System.out.print("Numéro à supprimer : ");
                    int index = scanner.nextInt() - 1;
                    playlist.supprimerChanson(index);
                    break;
                case 6:
                    playlist.afficherPlaylist();
                    break;
                case 7:
                    System.out.println("Au revoir !");
                    break;
                default:
                    System.out.println("Choix invalide !");
            }
        } while (choix != 7);

        scanner.close();
    }
}

10. Exercice

import java.util.LinkedList;
import java.util.Scanner;

public class HistoriqueNavigation {
    private LinkedList<String> historiqueArriere;
    private LinkedList<String> historiqueAvant;
    private String pageCourante;

    public HistoriqueNavigation() {
        historiqueArriere = new LinkedList<>();
        historiqueAvant = new LinkedList<>();
        pageCourante = null;
    }

    public void visiter(String url) {
        if (pageCourante != null) {
            historiqueArriere.addFirst(pageCourante);
        }
        pageCourante = url;
        historiqueAvant.clear();  // L'historique avant est vidé après une nouvelle visite
        System.out.println("Visite : " + pageCourante);
    }

    public String retour() {
        if (historiqueArriere.isEmpty()) {
            System.out.println("Impossible de revenir en arrière.");
            return pageCourante;
        }
        historiqueAvant.addFirst(pageCourante);
        pageCourante = historiqueArriere.removeFirst();
        System.out.println("◀ Retour à : " + pageCourante);
        return pageCourante;
    }

    public String avancer() {
        if (historiqueAvant.isEmpty()) {
            System.out.println("Impossible d'avancer.");
            return pageCourante;
        }
        historiqueArriere.addFirst(pageCourante);
        pageCourante = historiqueAvant.removeFirst();
        System.out.println("▶ Avance vers : " + pageCourante);
        return pageCourante;
    }

    public void afficherPageCourante() {
        if (pageCourante == null) {
            System.out.println("Aucune page visitée.");
        } else {
            System.out.println("Page courante : " + pageCourante);
        }
    }

    public void afficherHistorique() {
        System.out.println("\n=== HISTORIQUE DE NAVIGATION ===");
        System.out.println("Pages précédentes : " + historiqueArriere);
        System.out.println("Page courante : " + pageCourante);
        System.out.println("Pages suivantes : " + historiqueAvant);
        System.out.println("Arrière : " + historiqueArriere.size() + " page(s)");
        System.out.println("Avant : " + historiqueAvant.size() + " page(s)\n");
    }

    public static void main(String[] args) {
        HistoriqueNavigation nav = new HistoriqueNavigation();
        Scanner scanner = new Scanner(System.in);
        int choix;

        do {
            System.out.println("\n╔════════════════════════════════════╗");
            System.out.println("║      HISTORIQUE DE NAVIGATION      ║");
            System.out.println("╠════════════════════════════════════╣");
            System.out.println("║ 1. Visiter une page               ║");
            System.out.println("║ 2. Retour (précédent)              ║");
            System.out.println("║ 3. Avancer (suivant)               ║");
            System.out.println("║ 4. Afficher la page courante       ║");
            System.out.println("║ 5. Afficher l'historique complet   ║");
            System.out.println("║ 6. Quitter                         ║");
            System.out.println("╚════════════════════════════════════╝");
            System.out.print("Votre choix : ");
            choix = scanner.nextInt();
            scanner.nextLine();

            switch (choix) {
                case 1:
                    System.out.print("URL : ");
                    String url = scanner.nextLine();
                    nav.visiter(url);
                    break;
                case 2:
                    nav.retour();
                    break;
                case 3:
                    nav.avancer();
                    break;
                case 4:
                    nav.afficherPageCourante();
                    break;
                case 5:
                    nav.afficherHistorique();
                    break;
                case 6:
                    System.out.println("Au revoir !");
                    break;
                default:
                    System.out.println("Choix invalide !");
            }
        } while (choix != 6);

        scanner.close();
    }
}

=== HISTORIQUE DE NAVIGATION ===
1. Visiter une page
2. Retour (précédent)
3. Avancer (suivant)
4. Afficher la page courante
5. Afficher l'historique complet
6. Quitter
Votre choix : 1
URL : google.com
Visite : google.com

Votre choix : 1
URL : youtube.com
Visite : youtube.com

Votre choix : 2
◀ Retour à : google.com

Votre choix : 5
=== HISTORIQUE DE NAVIGATION ===
Pages précédentes : []
Page courante : google.com
Pages suivantes : [youtube.com]
Arrière : 0 page(s)
Avant : 1 page(s)

  L'essentiel en bref