Structure de données de liste liée en Java

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. 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;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
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. 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 implementation in Java
       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 ArrayList cas, 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

Complexité temporelle de ArrayList

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) {
       // start navigation from end to preserve indexes of removed items
       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));
           // should print `[2.0, 5.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));
           // should print `[2.0, 5.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();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           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();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           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 :

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 :

1. Créez une classe Node avec deux attributs, data et next. Next est une référence au nœud suivant.
2. Créez la classe FirstLast avec deux attributs, head et tail.
3. 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.