Glissez pour afficher le menu

Et si les objets étaient liés entre eux ?

Passons à la prochaine structure de données, particulièrement intéressante : LinkedList.

Examinons la syntaxe et le schéma de fonctionnement de LinkedList :

Comme vous pouvez le constater, la syntaxe est absolument identique à la déclaration d’un ArrayList. De manière générale, toute liste peut être déclarée de cette façon.

Mais l’aspect intéressant commence lorsque l’on cherche à comprendre le fonctionnement de LinkedList.

Comment la LinkedList est-elle structurée ?

En interne, LinkedList fonctionne avec des Nodes. Un Node est un objet qui est stocké à l'intérieur de la LinkedList. Il est implémenté dans la LinkedList de la manière suivante :

Main.java


              1234567891011
            
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Analysons la composition de cette classe. Tout d'abord, il faut répondre à la question principale qui se pose : Que signifie <E> ? Il s'agit d'un générique.

En termes simples, il s'agit ici de laisser un espace réservé pour le type de données qui sera spécifié lors de l'initialisation. Ce placeholder est utilisé dans le code, et il sera ensuite remplacé par le type de données indiqué par l'utilisateur.

Cela peut être comparé à la surcharge.

Voyons comment cela fonctionne :

Ainsi, au lieu de surcharger cette méthode pour chaque type de données, on utilise un générique dans lequel on insère le type de données avec lequel la méthode fonctionnera. La lettre E sera simplement remplacée par le type de données requis. Dans notre cas, il s'agit de Integer.

Ensuite, portons attention au champ item E. Il s'agit de la valeur de l'objet qui sera stockée dans ce Node. Ainsi, si l'on crée une liste comme {0, 1, 2, 3}, le premier nœud stockera l'élément 0, le second nœud stockera l'élément 1, et ainsi de suite.

Ensuite, on observe des références à d'autres objets Node : Node<E> next et Node<E> prev. C'est la principale caractéristique d'une liste chaînée. Dans un Node, il existe une référence vers le Node suivant et vers le précédent. C'est ainsi que l'on parcourt la liste. Examinons de plus près l'itération à travers une LinkedList.

En observant un tel schéma, on peut conclure que le parcours de cette liste fonctionne différemment.

Dans ArrayList<>(), en interne, le programme utilise un tableau qui double de taille lorsque le nombre d'éléments atteint les 3/4 de sa capacité.

Dans une LinkedList<>(), il n'est pas nécessaire de recréer un tableau car il n'y a pas de tableau dans une LinkedList. À la place, lors de l'ajout d'un nouvel élément, un nouvel objet Node est créé et lié par des références à l'ancien dernier élément.

Cela peut sembler un peu compliqué, mais en tant que programmeur, il n'est pas nécessaire de tout configurer vous-même.

Les méthodes de LinkedList sont identiques à celles de ArrayList car elles héritent toutes deux de l'interface List, qui définit les méthodes que tous ses descendants doivent implémenter.

Complexité algorithmique

Vous pouvez constater que la recherche d’un élément par index dans une ArrayList présente une complexité constante car il suffit simplement d’accéder à l’index dans le tableau.

En revanche, dans une LinkedList, la recherche par index prend beaucoup plus de temps car il faut parcourir tous les nœuds pour trouver l’objet souhaité à l’index donné.

D’un autre côté, si l’on considère l’insertion d’un élément, la LinkedList présente une complexité constante, tandis que la ArrayList a une complexité linéaire. Cela s’explique par le fait que pour insérer un élément dans une LinkedList, il suffit de modifier les liens entre les nœuds pour insérer le nouvel élément entre eux. Pour une ArrayList, il est nécessaire de recréer le tableau avec le nouvel élément, ce qui implique de copier l’ancien tableau et d’insérer l’élément, ce qui prend beaucoup plus de temps.

Voyons un exemple :

Main.java


              1234567891011121314151617181920212223242526272829
            
package com.example;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        List<Integer> arrayList = new ArrayList<>();

        Random random = new Random();

        for (int i = 0; i < 1000000; i++) {
            int randomValue = random.nextInt(100);
            arrayList.add(randomValue);
            linkedList.add(randomValue);
        }
        long startTimeArrayList = System.nanoTime();
        arrayList.add(1000, 50);
        long endTimeArrayList = System.nanoTime();
        long elapsedTimeArrayList = endTimeArrayList - startTimeArrayList;
        System.out.println("Time taken to put data in ArrayList: " + elapsedTimeArrayList + " nanoseconds");

        long startTimeLinkedList = System.nanoTime();
        linkedList.add(1000, 50);
        long endTimeLinkedList = System.nanoTime();
        long elapsedTimeLinkedList = endTimeLinkedList - startTimeLinkedList;
        System.out.println("Time taken to put data in LinkedList: " + elapsedTimeLinkedList + " nanoseconds");
    }
}

Nous avons créé deux listes : l’une est une ArrayList, l’autre une LinkedList. Ensuite, nous les avons remplies avec 1 000 000 d’entiers aléatoires. Les listes contiennent les mêmes éléments, chacune comprenant un million de nombres de 1 à 100.

Ensuite, nous avons mesuré le temps nécessaire pour ajouter un élément à l’index millième avec la valeur 50. Nous avons utilisé la méthode System.nanoTime() pour mesurer le temps, qui indique l’heure actuelle en nanosecondes. Puis, pour chaque liste, nous avons soustrait le temps de début du temps de fin, déterminant ainsi le temps écoulé pour ajouter un élément au milieu de la liste.

Vous pouvez constater que la LinkedList a été nettement plus rapide, comme le montre le tableau. La LinkedList présente une complexité algorithmique constante, tandis que la ArrayList a une complexité linéaire.

C’est pourquoi il existe différents types de listes. Si votre projet traite une grande quantité de données où l’optimisation est cruciale, il est pertinent de reconsidérer le type de liste qui offrira les meilleures performances dans certains cas. Mais je vais vous confier un secret : j’utilise presque toujours ArrayList.

SinglyLinkedList

Il existe une autre structure de données non divulguée appelée SinglyLinkedList. Comme son nom l'indique, cette structure de données utilise l'itération dans une seule direction. Alors que la classe LinkedList de Node possède les champs : item, next et prev, la classe SinglyLinkedList de Node ne possède que 2 champs : item et next.

Main.java


              123456789
            
class Node<E> {
    E item;
    Node<E> next;

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

Cette structure de données est utilisée dans des structures telles que les maps, où l'itération n'est nécessaire que dans une seule direction. Nous aborderons les maps, en particulier HashMap, dans les sections suivantes.

Dans le prochain chapitre, nous écrirons une implémentation de SinglyLinkedList afin de mieux comprendre le fonctionnement de cette structure de données intéressante.

1. Quelle structure de données sera la plus rapide si l'on souhaite trouver un élément par son index ?

2. Quelle structure de données sera la plus rapide lors de l'exécution d'une opération de suppression ?

3. Comment la classe `Node` intervient-elle dans le fonctionnement de la `LinkedList` ?

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

Section 1. Chapitre 6

Linkedlist en Java

Et si les objets étaient liés entre eux ?

Comment la LinkedList est-elle structurée ?

Complexité algorithmique

SinglyLinkedList

1. Quelle structure de données sera la plus rapide si l'on souhaite trouver un élément par son index ?

2. Quelle structure de données sera la plus rapide lors de l'exécution d'une opération de suppression ?

3. Comment la classe Node intervient-elle dans le fonctionnement de la LinkedList ?

3. Comment la classe `Node` intervient-elle dans le fonctionnement de la `LinkedList` ?