Comment créer une structure de données Liste Chaînée en Java

Créer une structure de données qui gère efficacement une collection d’éléments peut être un défi en programmation. L’une des structures les plus couramment utilisées est la Liste Chaînée. Dans cet article, nous allons vous guider à travers le processus de création d’une Liste Chaînée en Java, même s’il existe déjà une classe intégrée dans la bibliothèque standard Java.

Comprendre le Problème

Lorsque vous pensez aux structures de données, vous pourriez penser aux tableaux, mais parfois, ils ne suffisent pas. C’est là que les listes chaînées entrent en jeu. Une Liste Chaînée vous permet d’insérer et de supprimer des éléments de manière efficace sans avoir besoin de redimensionner un tableau. Elle consiste en une séquence de nœuds où chaque nœud contient des données et une référence au nœud suivant.

L’Option Intégrée

Java fournit une classe intégrée LinkedList dans le package java.util, qui est pratique et convient à de nombreuses situations. Cependant, pouvoir créer votre propre implémentation peut approfondir votre compréhension et vous donner plus de contrôle sur le comportement de la structure de données.

Créer Votre Propre Liste Chaînée

Ci-dessous, nous allons explorer la construction de notre propre Liste Chaînée simple à partir de zéro. Pour ce tutoriel, nous allons nous concentrer sur une liste chaînée simple qui permet d’insérer et de supprimer des nœuds depuis le début.

Étape 1 : Définir la Classe Link

Tout d’abord, nous devons créer une classe Link pour représenter chaque élément de la liste. Voici à quoi cela ressemble en code :

class Link {
    public int data1;
    public double data2;
    public Link nextLink;

    // Constructeur Link
    public Link(int d1, double d2) {
        data1 = d1;
        data2 = d2;
    }

    // Afficher les données du Link
    public void printLink() {
        System.out.print("{" + data1 + ", " + data2 + "} ");
    }
}

Étape 2 : Définir la Classe LinkList

Ensuite, nous avons besoin d’une classe pour l’ensemble de la liste elle-même :

class LinkList {
    private Link first;

    // Constructeur LinkList
    public LinkList() {
        first = null;
    }

    // Retourne vrai si la liste est vide
    public boolean isEmpty() {
        return first == null;
    }

    // Insère un nouveau Link au début de la liste
    public void insert(int d1, double d2) {
        Link link = new Link(d1, d2);
        link.nextLink = first;
        first = link;
    }

    // Supprime le lien en tête de la liste
    public Link delete() {
        Link temp = first;
        if (first == null) {
            return null; // ou lancer une exception
        }
        first = first.nextLink;
        return temp;
    }

    // Affiche tous les liens dans la liste
    public void printList() {
        Link currentLink = first;
        System.out.print("Liste : ");
        while (currentLink != null) {
            currentLink.printLink();
            currentLink = currentLink.nextLink;
        }
        System.out.println("");
    }
}

Étape 3 : Tester la LinkList

Enfin, mettons en œuvre une méthode principale pour tester notre Liste Chaînée :

class LinkListTest {
    public static void main(String[] args) {
        LinkList list = new LinkList();

        // Insérer quelques éléments
        list.insert(1, 1.01);
        list.insert(2, 2.02);
        list.insert(3, 3.03);
        list.insert(4, 4.04);
        list.insert(5, 5.05);

        // Afficher la liste
        list.printList();

        // Supprimer des éléments
        while (!list.isEmpty()) {
            Link deletedLink = list.delete();
            System.out.print("supprimé : ");
            deletedLink.printLink();
            System.out.println("");
        }
        list.printList();
    }
}

Conclusion

Dans cet article, nous avons exploré comment créer une Liste Chaînée personnalisée en Java, complète avec des méthodes essentielles pour insérer, supprimer et imprimer des nœuds. Bien que la classe LinkedList fournie par la bibliothèque standard de Java puisse suffire pour de nombreuses applications, implémenter la vôtre peut être une expérience enrichissante qui améliore vos compétences en programmation.

Améliorations Supplémentaires

Une fois que vous maîtrisez cette implémentation de base, envisagez d’ajouter :

• Liste Doublement Chaînée : Chaque nœud devrait avoir des références aux nœuds suivants et précédents.
• Insérer/Supprimer au Milieu/À la Fin : Méthodes pour ajouter ou enlever des nœuds à partir de diverses positions.
• Méthodes Get et Trier : Fonctions pour récupérer des éléments spécifiques ou trier la liste chaînée.

Se familiariser avec ces améliorations peut porter vos compétences au niveau supérieur. Bon codage !