Apprendre Implémentation de LinkedList en Java | Structures de Données Fondamentales en Java

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 stockera 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, nous n’y reviendrons donc pas en détail.

Ensuite, créons la classe SinglyLinkedList, dans laquelle nous définirons toute la logique de notre structure de données :

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

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

Nous avons créé le champ Node head, qui stockera le premier élément de notre structure de données.

Dans une LinkedList classique, il existe également une head et une 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, nous initialisons ce champ à null dans le constructeur.

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

Création

Procédure étape par étape pour écrire une méthode permettant d’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, présentation de l’implémentation de la méthode permettant d’ajouter un élément à la fin de la liste. Analyse du fonctionnement de cette méthode :

Création d’un objet de la classe Node, nommé newNode, initialisé via le constructeur, en transmettant la data issue des paramètres de la méthode append() ;
Vérification si la liste est vide ; si tel 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 dans cette méthode d’un nouvel objet, current, représentant le Node head dans ce contexte ;
Utilisation d’une boucle while pour parcourir l’ensemble de 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 de la liste trouvé, affectation de son lien à newNode, ajoutant ainsi l’élément à la liste.

En d’autres termes, l’objectif de la méthode append est de définir le lien du dernier élément vers le nouvel élément. De cette manière, ajout d’un nouvel élément à 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 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 est plus intéressante :

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 avec l’algorithme habituel. Création d’un objet de la classe Node nommé current, initialisé avec la valeur de head ;
Au lieu d’utiliser une boucle while, utilisation 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 connue : 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 6

Demandez à l'IA

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

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 stockera 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, nous n’y reviendrons donc pas en détail.

Ensuite, créons la classe SinglyLinkedList, dans laquelle nous définirons toute la logique de notre structure de données :

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

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

Nous avons créé le champ Node head, qui stockera le premier élément de notre structure de données.

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

Création

Procédure étape par étape pour écrire une méthode permettant d’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, présentation de l’implémentation de la méthode permettant d’ajouter un élément à la fin de la liste. Analyse du fonctionnement de cette méthode :

Création d’un objet de la classe Node, nommé newNode, initialisé via le constructeur, en transmettant la data issue des paramètres de la méthode append() ;
Vérification si la liste est vide ; si tel 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 dans cette méthode d’un nouvel objet, current, représentant le Node head dans ce contexte ;
Utilisation d’une boucle while pour parcourir l’ensemble de 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 de la liste trouvé, affectation de son lien à newNode, ajoutant ainsi l’élément à la liste.

En d’autres termes, l’objectif de la méthode append est de définir le lien du dernier élément vers le nouvel élément. De cette manière, ajout d’un nouvel élément à 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 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 est plus intéressante :

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 avec l’algorithme habituel. Création d’un objet de la classe Node nommé current, initialisé avec la valeur de head ;
Au lieu d’utiliser une boucle while, utilisation 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 connue : 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 6