Différentes structures de données sont créées à des fins différentes. Vous connaissez peut-être
ArrayList (si ce n'est toujours pas le cas, nous vous recommandons de lire d'abord à ce sujet). Dans cet article, nous allons en savoir plus sur
LinkedList et comprendre à quoi sert cette collection. Si vous regardez dans le code source de la classe LinkedList Java 8 (ou version ultérieure du langage) (sur le site Web d'Oracle ou dans votre IDE, dans le cas d'IDEA : crtl+B sur le nom de la classe), vous verrez la déclaration suivante :
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
Pour le moment, l'information la plus importante du code est le fait que
LinkedList implémente les interfaces
List et
Deque . L'interface List conserve la séquence d'ajout d'éléments et permet l'accès à l'élément par index. La
file d'attente "ordinaire" prend en charge l'ajout d'éléments à la fin et leur extraction depuis le début. Deque est une file d'attente bidirectionnelle et prend en charge l'ajout et la suppression d'éléments des deux côtés. Vous pouvez le considérer comme une combinaison de pile et de file d'attente.
![Structure de données Java LinkedList - 2]()
Donc, LinkedList est une implémentation de ces deux, et cela nous permet de créer une file d'attente bidirectionnelle composée de tous les objets, y compris null.
Liste liéeest un ensemble d'éléments. On peut le voir dans le code source de la classe, cette fois faites attention aux champs :
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
Chaque élément, généralement appelé
Node , contient un objet et des références à deux objets voisins - le précédent et le suivant. Par conséquent, il n'est pas très efficace en termes d'utilisation de la mémoire.
![Structure de données Java LinkedList - 3]()
Comme
LinkedList est en fait une structure bidirectionnelle, nous pouvons facilement ajouter ou supprimer des éléments des deux côtés.
Constructeurs de listes liées
De retour au code source, nous pouvons découvrir que
LinkedList a deux constructeurs
- LinkedList() sans paramètres est utilisé pour construire une liste vide.
- >LinkedList(Collection<? extend E> c) sert à créer une liste contenant les éléments de la collection spécifiée, dans l'ordre, ils sont renvoyés par l'itérateur de la collection.
Déclaration LinkedList
En fait, une liste chaînée (Java ou dans tout autre langage) consiste en une séquence de nœuds. Chaque nœud est conçu pour stocker un objet d'un type défini lors de la création. Donc, pour créer
LinkedList , le code Java est le suivant :
LinkedList<Integer> myList = new LinkedList<>();
Nous avons un objet pour conserver une séquence d'entiers et des liens vers les voisins. Cependant, il est vide pour le moment.
Opérations principales de LinkedList
Comme d'habitude, dans le cas des collections, vous pouvez mettre des éléments dans
LinkedList (à la fin ou au milieu), les supprimer et obtenir un élément par index. Alors les voici :
- add(E element) Ajoute l'élément spécifié à la fin de cette liste ;
- add(int index, E element) Insère l' élément à la position spécifiée index ;
- get(int index) Renvoie l'élément à la position spécifiée dans cette liste ;
- remove(int index) Supprime l'élément qui se trouve à la position index ;
- remove(Object o) Supprime la première occurrence de ? o élément de cette liste s'il s'y trouve.
- remove() Récupère et supprime le premier élément de la liste.
Implémentation de listes chaînées en Java, ajout et suppression d'éléments. Exemple
Essayons ces opérations sur la pratique. Tout d'abord, l'implémentation de Java LinkedList : créer une LinkedList de chaînes, en y ajoutant 3 éléments. Retirez-en ensuite un, puis ajoutez-en un au milieu.
public class MyLinkedTest {
public static void main(String[] args) {
String h1 = "my";
String h2 = "favorite";
String h3 = "book";
LinkedList<String> linkedList = new LinkedList();
linkedList.add(h1);
linkedList.add(h2);
linkedList.add(h3);
System.out.println("my list after adding 3 elements:");
System.out.println(linkedList);
System.out.println("element #2 of my list:");
System.out.println(linkedList.get(2));
linkedList.remove(1);
System.out.println("my list after removing #1:");
System.out.println(linkedList);
linkedList.add(1,"first");
System.out.println("my list after adding an element in the middle");
System.out.println(linkedList);
}
Le résultat de l'exécution de ce programme :
my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]
Une
LinkedList fait partie du framework
Collection , vous pouvez utiliser Iterator pour supprimer des éléments, ainsi qu'un itérateur spécial pour les listes —
ListIterator . De plus, les opérations avec iterator offrent les principaux avantages de la classe
LinkedList : de bonnes performances des opérations d'insertion/suppression. En utilisant Iterator, vous pouvez obtenir un temps constant pour eux. Plus loin dans cet article, nous écrirons un exemple de code pour comparer
ArrayList et
LinkedList+Iterator
- Iterator.remove() supprime le dernier élément renvoyé par cet itérateur.
- ListIterator.add(E element) insère un élément dans la liste
Exemple Java LinkedList : comment fonctionne Iterator
Ici, nous avons un petit exemple de code Java
LinkedList , où nous essayons d'ajouter et de supprimer via Iterator.
public class MyLinkedTest {
public static void main(String[] args) {
String h1 = "my";
String h2 = "favorite";
String h3 = "book";
LinkedList<String> linkedList = new LinkedList();
linkedList.add(h1);
linkedList.add(h2);
linkedList.add(h3);
Iterator i = linkedList.iterator();
String str = "";
while (i.hasNext()) {
str = (String)i.next();
if (str.equals("favorite")) {
i.remove();
break;
}
}
System.out.println("linkedList after removing element via Iterator:");
System.out.println(linkedList);
ListIterator listIterator = linkedList.listIterator();
listIterator.add("I've got");
System.out.println("linkedList after adding the element via ListIterator");
System.out.println(linkedList);
}
}
Le résultat de l'exécution de ce programme :
linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]
Plus d'opérations Java
LinkedList :
- addFirst() , addLast() ajoute un élément au début/à la fin d'une liste
- clear() supprime tous les éléments de la liste
- contains(Object o) renvoie true si la liste contient l'élément o.
- indexOf(Object o) renvoie l'index de la première occurrence de l'élément o, ou -1 s'il n'est pas dans la liste.
- set(int index, E element) remplace l'élément à la position d'index par l'élément
- size() Renvoie la quantité d'éléments dans la liste.
- toArray() renvoie un tableau contenant tous les éléments de la liste du premier au dernier élément.
BTW étant une file d'attente de deux tailles,
LinkedList en Java a des opérations spécifiques à la pile :
- pop() qui extrait un élément de la pile (représenté par la liste)
- push(E e) qui pousse un élément sur la pile (représenté par cette liste)
Comment inverser LinkedList : exemple
Voici un petit exemple, une tâche populaire, mais facile pour les débutants. Nous avons une
LinkedList et devrions l'inverser. L'algorithme le plus simple consiste à parcourir la
LinkedList dans l'ordre inverse et à placer chaque élément dans le nouveau. Cependant, peut-être trouverez-vous un meilleur moyen? Voici le code du programme Java de liste chaînée inversée :
public class MyLinkedTest {
public static void main(String[] args) {
String h1 = "my";
String h2 = "favorite";
String h3 = "book";
LinkedList<String> linkedList = new LinkedList();
linkedList.add(h1);
linkedList.add(h2);
linkedList.add(h3);
System.out.println(linkedList);
System.out.println("Reversed LinkedList:");
System.out.println(reverseLinkedList(linkedList));
}
public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
{
LinkedList<String> LinkedList = new LinkedList<String>();
for (int i = list.size() - 1; i >= 0; i--) {
LinkedList.add(list.get(i));
}
return LinkedList;
}
}
Le résultat:
[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]
LinkedList vs ArrayList : quand utiliser la première
LinkedList et
ArrayList sont des implémentations de l'
interface List .
LinkedList l'implémente avec une liste doublement liée.
ArrayList l'implémente en utilisant un tableau de redimensionnement dynamique. Comme vous le savez déjà, chaque nœud de
LinkedList contient des objets et deux références aux voisins. Cela signifie des coûts de mémoire supplémentaires pour stocker les références entre les éléments dans le cas de Java
LinkedList .
ArrayList l'implémente avec un tableau de redimensionnement dynamique. Certaines des opérations
LinkedList et
ArrayList se ressemblent, mais elles fonctionnent différemment. Dans la
ArrayListcas, vous manipulez avec des tableaux internes, dans
LinkedList - avec des références.
ArrayList est l' implémentation
de liste la plus populaire . Vous devez absolument utiliser
ArrayList lorsque l'accès à l'index est prioritaire car ces opérations sont effectuées en temps constant. L'ajout en fin de liste se fait en moyenne également en temps constant. De plus,
ArrayList n'a pas de coûts supplémentaires pour stocker un tas d'éléments. Vous pouvez compter comme Cons la rapidité des opérations d'insertion et de suppression lorsqu'elle n'est pas effectuée en fin de liste.
Liste liéeest plus utile dans le cas des performances des opérations d'insertion et de suppression à certains égards : si vous utilisez des itérateurs, cela se produit en temps constant. Les opérations d'accès par index sont effectuées en recherchant du début à la fin (celui qui est le plus proche) jusqu'à l'élément souhaité. Cependant, n'oubliez pas les coûts supplémentaires liés au stockage des références entre les éléments. Voici donc les opérations standard
LinkedList et
ArrayList avec des runtimes algorithmiques. N fait référence au nombre d'éléments qui sont déjà sur la liste.
O(N) signifie que dans le pire des cas, nous devrions "parcourir" toute la liste jusqu'à ce que la position nécessaire soit trouvée, par exemple, pour l'insertion du nouvel élément dans la liste.
O(1)signifie que l'opération se déroule en temps constant, indépendamment du nombre d'éléments.
Complexité temporelle de la liste liée
Opération Java LinkedList |
Efficacité algorithmique |
obtenir (index entier) |
O(n) , en moyenne — n/4 étapes, où n est une taille LinkedList |
ajouter (élément E) |
O(1) |
ajouter (index int, élément E) |
O(n) , en moyenne — n/4 étapes ; si index = 0 alors O(1) , donc si vous avez besoin d'ajouter quelque chose au début de la liste, LinkedList<E> pourrait être un bon choix |
supprimer (index int) |
O(n) , en moyenne — n/4 étapes |
Itérateur.remove() |
O(1) C'est la principale raison d'utiliser LinkedList<E> |
Complexité temporelle de ArrayList
Opération de liste liée |
Efficacité algorithmique |
obtenir (index entier) |
O(1) , l'une des principales raisons d'utiliser ArrayList<E> |
ajouter (élément E) |
O(n) est le pire des cas puisque le tableau doit être redimensionné et copié, cependant, en pratique, ce n'est pas si mal |
ajouter (index int, élément E) |
O(n) , n/2 étapes en moyenne |
supprimer (index int) |
O(n) , n/2 étapes en moyenne |
Itérateur.remove() |
O(n) , n/2 étapes en moyenne |
ListIterator.add(élément E) |
O(n) , n/2 étapes en moyenne |
Quand utiliser LinkedList : Exemple
Sans aucun doute,
ArrayList est l' implémentation
de liste la plus populaire . Cependant, vous pouvez rencontrer des situations où les opérations d'ajout/suppression sont nécessaires trop souvent. Dans ce cas,
LinkedList avec Iterator pourrait être bénéfique. Voici un exemple. Nous avons une longue liste et nous devrions supprimer tous les éléments de cette liste. Faisons cette tâche avec
ArrayList et
LinkedList +
Iterator . Nous comparons le temps de chaque opération et l'imprimons dans la console. Ici le code :
import java.util.*;
import java.util.function.BiPredicate;
public class ListTest2 {
static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
ListIterator<Double> iterator = list.listIterator(list.size());
while (iterator.hasPrevious()) {
Double element = iterator.previous();
if (predicate.test(iterator.previousIndex()+1, element)) {
iterator.remove();
}
}
}
static class TestCase1 {
public static void main(String[] args) {
LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
removeElements(testedList1, (index, value) -> (value % 3 == 0));
System.out.println("testedList1 after removeElements(..): " + testedList1);
ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
removeElements(testedList2, (index, value) -> (value % 3 == 0));
System.out.println("testedList2 after removeElements(..): " + testedList2);
}
}
static class TestLinkedListPerformance {
public static void main(String[] args) {
LinkedList<Double> testedList = new LinkedList<>();
System.out.println("start filling testedList");
for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
testedList.add((double)i);
}
System.out.println("start treating testedList");
long startTime = System.nanoTime();
removeElements(testedList, (index, value) -> (value % 3 == 0));
long endTime = System.nanoTime();
System.out.println("testedList.size after removeElements(..): " + testedList.size());
System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
}
}
static class TestArrayListPerformance {
public static void main(String[] args) {
ArrayList<Double> testedList = new ArrayList<>();
System.out.println("start filling testedList");
for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
testedList.add((double)i);
}
System.out.println("start treating testedList");
long startTime = System.nanoTime();
removeElements(testedList, (index, value) -> (value % 3 == 0));
long endTime = System.nanoTime();
System.out.println("testedList.size after removeElements(..): " + testedList.size());
System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
}
}
}
Résultat pour ArrayList :
start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414
Résultat pour LinkedList :
start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458
Comme vous pouvez le voir dans ce cas, LinkedList est bien plus efficace. Soyons honnêtes. Dans le développement de logiciels réels, l'utilisation
de LinkedList est une sorte d'événement rare. Néanmoins, un professionnel doit connaître l'existence de cette structure de données et ses avantages. Si dans le code réel
LinkedList est un invité rare, sur les interviews de Java Junior, il est très populaire. Et pourtant, voici ce que Joshua Bloch a écrit à propos de
LinkedList :
![Structure de données Java LinkedList - 4]()
Module complémentaire : Java de liste chaînée unique
Il n'y a pas
de liste liée singulièrement parmi
les collections classiques en Java,
la liste liée singulièrement est une structure où chaque nœud contient un objet et une référence au nœud suivant, mais pas au nœud précédent. Java
LinkedList est à deux liens, mais personne ne vous empêche de créer votre propre structure de données, telle qu'une liste unique, code> liée. Voici quelques étapes pour résoudre ces tâches :
- Créez une classe Node avec deux attributs, data et next. Next est une référence au nœud suivant.
- Créez la classe FirstLast avec deux attributs, head et tail.
- Créez une méthode add() pour ajouter un nouveau nœud à la liste. Vérifiez d'abord si la liste est vide ( head == null ). Si c'est le cas, la tête et la queue font référence au nouveau nœud. Si la liste n'est pas vide, le nouveau nœud sera ajouté à la fin, donc l'attribut suivant de la queue fait référence au nœud ajouté et le nouveau nœud devient la queue de la liste.
Au fait, vous pouvez également essayer de créer votre propre
LinkedList comme exercice. Bonne chance dans votre apprentissage.
GO TO FULL VERSION