LinkedList en Java
Et si les objets étaient liés entre eux ?
Passons à la prochaine structure de données, particulièrement intéressante : la LinkedList.
Examinons la syntaxe et le schéma de fonctionnement de la LinkedList :
Comme vous pouvez le constater, la syntaxe est absolument identique à la déclaration d'une 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 la 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 LinkedList de la manière suivante :
Main.java
1234567891011class 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 convient de 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. Vous utilisez cet espace réservé dans le code, qui sera ensuite remplacé par le type de données spécifié 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, vous utilisez un générique dans lequel vous insérez 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 nous créons 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, vous voyez des références à d'autres objets Node : Node<E> next et Node<E> prev.
C'est la caractéristique principale d'une liste chaînée. Dans un Node, il y a une référence vers le Node suivant et 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 soi-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
Dans le framework Collection, il existe de nombreuses structures de données différentes, et chacune possède sa propre complexité algorithmique.
La complexité algorithmique est exprimée à l’aide de la notation grand O (par exemple, O(n), O(n^2)), où "O" signifie "grand O" et indique une borne supérieure de la croissance du temps d’exécution en fonction de la taille de l’entrée.
Voici les principaux types de complexité algorithmique :
-
O(1)(temps constant) : la complexité temporelle ne dépend pas de la taille des données d'entrée. Par exemple, accéder à un élément d'un tableau par son indice ; -
O(log n)(temps logarithmique) : la complexité temporelle augmente de façon logarithmique avec la taille des données d'entrée. Exemple : recherche binaire dans un tableau trié ; -
O(n)(temps linéaire) : la complexité temporelle augmente linéairement avec la taille des données d'entrée. Exemple : itération sur tous les éléments dans unArrayList; -
O(n^2)(temps quadratique) : la complexité temporelle est proportionnelle au carré de la taille des données d'entrée. Exemple : tri à bulles.
Ce sont des catégories de base, et il existe de nombreux autres types de complexité algorithmique, tels que O(n log n), O(2^n), O(n!) et d'autres, caractérisant des algorithmes plus complexes. Le choix d'un algorithme efficace, en tenant compte de sa complexité, constitue un aspect crucial du développement logiciel.
Revenons maintenant aux structures de données en Java. Chaque structure de données possède sa propre complexité algorithmique selon l'opération à effectuer. Examinons le tableau :
On peut constater que la recherche d'un élément par indice dans un ArrayList présente une complexité constante, car il suffit simplement d'accéder à l'indice dans le tableau.
En revanche, dans une LinkedList, la recherche par indice prend beaucoup plus de temps car il faut parcourir tous les nœuds et trouver l'objet souhaité par son indice.
D'autre part, si l'on considère l'insertion d'un élément, la LinkedList présente une complexité constante, tandis que l'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.
Examinons un exemple :
Main.java
1234567891011121314151617181920212223242526272829package 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'indice millième avec la valeur 50. Nous avons utilisé la méthode System.nanoTime() pour mesurer le temps, qui affiche l'heure actuelle en nanosecondes. Puis, pour chaque liste, nous avons soustrait le temps de début du temps de fin, déterminant ainsi combien de temps a été consacré à l'ajout d'un élément au milieu de la liste.
Vous pouvez constater que la LinkedList est nettement plus rapide, comme le montre le tableau. LinkedList présente une complexité algorithmique constante, tandis que ArrayList a une complexité linéaire.
C'est pourquoi différents types de listes sont nécessaires. Si votre projet traite une grande quantité de données où l'optimisation est cruciale, il peut être pertinent de reconsidérer le type de liste qui offrira de 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 méconnue 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 comporte que 2 champs : item et next.
Main.java
123456789class 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 offre de meilleures performances lors d'une opération de suppression ?
3. Comment la classe Node intervient-elle dans le fonctionnement de LinkedList ?
Merci pour vos commentaires !
Demandez à l'IA
Demandez à l'IA
Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion
What are the main differences between ArrayList and LinkedList?
Can you explain how generics work in Java with more examples?
Why would I choose LinkedList over ArrayList in a real project?
Génial!
Completion taux amélioré à 4LinkedList en Java
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 : la LinkedList.
Examinons la syntaxe et le schéma de fonctionnement de la LinkedList :
Comme vous pouvez le constater, la syntaxe est absolument identique à la déclaration d'une 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 la 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 LinkedList de la manière suivante :
Main.java
1234567891011class 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 convient de 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. Vous utilisez cet espace réservé dans le code, qui sera ensuite remplacé par le type de données spécifié 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, vous utilisez un générique dans lequel vous insérez 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 nous créons 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, vous voyez des références à d'autres objets Node : Node<E> next et Node<E> prev.
C'est la caractéristique principale d'une liste chaînée. Dans un Node, il y a une référence vers le Node suivant et 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 soi-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
Dans le framework Collection, il existe de nombreuses structures de données différentes, et chacune possède sa propre complexité algorithmique.
La complexité algorithmique est exprimée à l’aide de la notation grand O (par exemple, O(n), O(n^2)), où "O" signifie "grand O" et indique une borne supérieure de la croissance du temps d’exécution en fonction de la taille de l’entrée.
Voici les principaux types de complexité algorithmique :
-
O(1)(temps constant) : la complexité temporelle ne dépend pas de la taille des données d'entrée. Par exemple, accéder à un élément d'un tableau par son indice ; -
O(log n)(temps logarithmique) : la complexité temporelle augmente de façon logarithmique avec la taille des données d'entrée. Exemple : recherche binaire dans un tableau trié ; -
O(n)(temps linéaire) : la complexité temporelle augmente linéairement avec la taille des données d'entrée. Exemple : itération sur tous les éléments dans unArrayList; -
O(n^2)(temps quadratique) : la complexité temporelle est proportionnelle au carré de la taille des données d'entrée. Exemple : tri à bulles.
Ce sont des catégories de base, et il existe de nombreux autres types de complexité algorithmique, tels que O(n log n), O(2^n), O(n!) et d'autres, caractérisant des algorithmes plus complexes. Le choix d'un algorithme efficace, en tenant compte de sa complexité, constitue un aspect crucial du développement logiciel.
Revenons maintenant aux structures de données en Java. Chaque structure de données possède sa propre complexité algorithmique selon l'opération à effectuer. Examinons le tableau :
On peut constater que la recherche d'un élément par indice dans un ArrayList présente une complexité constante, car il suffit simplement d'accéder à l'indice dans le tableau.
En revanche, dans une LinkedList, la recherche par indice prend beaucoup plus de temps car il faut parcourir tous les nœuds et trouver l'objet souhaité par son indice.
D'autre part, si l'on considère l'insertion d'un élément, la LinkedList présente une complexité constante, tandis que l'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.
Examinons un exemple :
Main.java
1234567891011121314151617181920212223242526272829package 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'indice millième avec la valeur 50. Nous avons utilisé la méthode System.nanoTime() pour mesurer le temps, qui affiche l'heure actuelle en nanosecondes. Puis, pour chaque liste, nous avons soustrait le temps de début du temps de fin, déterminant ainsi combien de temps a été consacré à l'ajout d'un élément au milieu de la liste.
Vous pouvez constater que la LinkedList est nettement plus rapide, comme le montre le tableau. LinkedList présente une complexité algorithmique constante, tandis que ArrayList a une complexité linéaire.
C'est pourquoi différents types de listes sont nécessaires. Si votre projet traite une grande quantité de données où l'optimisation est cruciale, il peut être pertinent de reconsidérer le type de liste qui offrira de 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 méconnue 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 comporte que 2 champs : item et next.
Main.java
123456789class 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 offre de meilleures performances lors d'une opération de suppression ?
3. Comment la classe Node intervient-elle dans le fonctionnement de LinkedList ?
Merci pour vos commentaires !
