Apprendre Implémentation de LinkedList en Java

Glissez pour afficher le menu

Il est temps de vous mettre au défi avec des tâches vraiment complexes.

Nous allons implémenter notre structure de données simplifiée—plus précisément, la SinglyLinkedList.

Commençons par implémenter la classe Node, qui va stocker une valeur et une référence vers le Node suivant.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

L’implémentation de la classe Node dans SinglyLinkedList a déjà été présentée dans le chapitre précédent, il n’est donc pas nécessaire de s’y attarder longuement.

Ensuite, création de la classe SinglyLinkedList, dans laquelle toute la logique de la structure de données sera définie :

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }
}

Le champ Node head a été créé pour stocker le premier élément de la structure de données.

Dans une LinkedList classique, il existe également un head et un tail qui stockent respectivement le premier et le dernier élément de la structure de données. Puisque la structure de données doit être vide lors de l’initialisation, ce champ est initialisé à null dans le constructeur.

La structure de données doit prendre en charge toutes les opérations CRUD.

Création

Procédons étape par étape et écrivons une méthode pour ajouter un élément à la fin de la liste, représentant l’opération de création :

SinglyLinkedList.java


              12345678910111213141516171819202122
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        current.next = newNode;
    }
}

Ci-dessus, vous pouvez voir l’implémentation de la méthode permettant d’ajouter un élément à la fin de la liste. Analysons le fonctionnement de cette méthode :

Création d’un objet de la classe Node, nommé newNode, initialisé via le constructeur, en passant la valeur data issue des paramètres de la méthode append() ;
Vérification si la liste est vide ; si c’est le cas, remplacement du premier élément de la liste (head) par newNode via réaffectation ;
Ajout d’une instruction return pour quitter la méthode ;
Si la liste n’est pas vide, création d’un nouvel objet, current, représentant le Node head dans ce contexte ;
Utilisation d’une boucle while pour parcourir toute la liste jusqu’à ce que current.next soit null, c’est-à-dire jusqu’à ce que l’élément suivant de la liste soit vide ;
Une fois le dernier élément non nul trouvé dans la liste, définition de son lien vers newNode, ajoutant ainsi l’élément à la liste.

En d’autres termes, l’objectif de la méthode append était d’établir le lien du dernier élément vers le nouvel élément. De cette façon, un nouvel élément est ajouté à la liste.

Lecture

Passons à la suite ; nous devons maintenant implémenter l’opération de lecture.

SinglyLinkedList.java


              12345678
            
public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

L’opération de lecture est assez simple. Il faut itérer sur chaque élément de la liste et les afficher à l’écran. Dans notre cas, nous utilisons également le placeholder current, que nous initialisons avec le Node head ;
Ensuite, nous définissons la condition de la boucle while à current != null et nous affichons le champ data à l’écran ;
Pour parcourir la liste, nous utilisons la référence en réaffectant current, ce qui donne current = current.next; ;
Nous répétons cela jusqu’à ce que le Node current soit vide. Après cela, nous sortons de la boucle et passons à la ligne suivante.

Au fait, réfléchissez à comment remplacer cette boucle while par une boucle do-while. Est-ce possible ?

Mise à jour

Passons maintenant à la méthode de mise à jour, dont l’implémentation présente un intérêt particulier :

SinglyLinkedList.java


              12345678910111213
            
public void update(int index, int newData) {
    if (index < 0 || index >= size()) {
        System.out.println("Invalid index");
        return;
    }

    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }

    current.data = newData;
}

Tout d'abord, vérification de la présence de cet index dans la liste à l'aide d'une instruction if. Si ce n'est pas le cas, affichage du message "Invalid index" et arrêt de la méthode. Cette étape est réalisée pour éviter les erreurs ;
Si l’index est compris dans les limites de la liste, poursuite de l’algorithme habituel. Création d’un objet de la classe Node nommé current, initialisé avec la valeur de head ;
Utilisation d’une boucle while au lieu d’une boucle for, plus appropriée ici puisque le nombre exact d’itérations est connu. Le nombre d’itérations correspond à la valeur du paramètre index ;
La boucle s’écrit ainsi :
for (int i = 0; i < index; i++). Dans cette boucle, recherche de l’élément souhaité à l’aide de l’opération habituelle : current = current.next ;
Une fois l’élément trouvé, affectation d’une nouvelle valeur à son attribut data via l’opération
current.data = newData. La valeur newData est fournie en paramètre de cette méthode.

Tout était clair ?

Merci pour vos commentaires !

Section 1. Chapitre 7

Demandez à l'IA

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

Section 1. Chapitre 7