Liste liée Java

Salut! Toutes les dernières leçons ont été consacrées à ArrayList . Cette structure de données est très pratique et utile. Il peut gérer de nombreuses tâches. Mais Java a beaucoup d'autres structures de données. Pourquoi? Surtout, parce que la gamme de tâches est énorme et que les structures de données les plus efficaces sont différentes pour différentes tâches. Aujourd'hui nous allons rencontrer une nouvelle structure : Java LinkedList , une liste doublement liée.

Voyons comment il est organisé, pourquoi il est appelé doublement lié, en quoi il diffère de ArrayList . Les éléments d'une LinkedList Java sont en fait des liens dans une seule chaîne. En plus des données, chaque élément stocke des références aux éléments précédents et suivants. Ces références permettent de passer d'un élément à un autre. Voici comment vous en créez un :

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

Sortie : [Bonjour le monde ! Je m'appelle Earl, j'adore Java, j'habite au Canada] Voici à quoi ressemble notre liste : Liste liée - 2

Voyons comment ajouter un nouvel élément. Ceci est fait en utilisant la méthode add() .

earlBio.add(str2);

Au point du code, notre liste se compose d'un élément : le String str1 . Voyons ce qui se passe ensuite dans l'image : Liste liée - 3

En conséquence, str2 et str1 sont liés via les liens suivants et précédents stockés dans ces nœuds de la liste : Liste liée - 4

vous devez maintenant comprendre l'idée principale d'une liste à double lien. Cette chaîne de liens est précisément ce qui fait des éléments LinkedList une liste unique. Contrairement à ArrayList , LinkedList n'a pas de tableau ou quoi que ce soit de semblable à un tableau à l'intérieur. Tout travail (enfin, la plupart) avec ArrayList se résume à travailler avec le tableau interne. Tout travail avec Java LinkedListse résume à changer de liens. Cela se voit très clairement en ajoutant un élément au milieu de la liste :

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

Comme vous pouvez le voir, la méthode add() surchargée vous permet de spécifier un index spécifique pour un nouvel élément. Dans ce cas, nous voulons ajouter String str2 entre str1 et str3 . Voici ce qui se passera en interne : Liste liée - 5

Après avoir changé les liens internes, str2 a été ajouté avec succès à la liste : Liste liée - 6

Maintenant, les 3 éléments sont connectés. Vous pouvez vous déplacer via le maillon suivant du premier élément de la chaîne au dernier et vice-versa. Donc, nous sommes assez à l'aise avec l'insertion, mais qu'en est-il de la suppression d'éléments ? Le principe est exactement le même. On met juste à jour les liens dans les deux éléments "à gauche et à droite" de l'élément en cours de suppression :

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

Voici ce qui se passe si nous supprimons l'élément d'index 1 (il est au milieu de la liste) : Liste liée - 7

Après mise à jour des liens, nous obtenons le résultat souhaité : Liste liée - 8

Contrairement à l'opération de suppression dans ArrayList , ici, il n'est pas nécessaire de décaler les éléments du tableau ni de faire n'importe quoi de ce genre. Nous venons de mettre à jour les liens pour str1 et str3 . Ils pointent maintenant l'un vers l'autre, et str2 a " abandonné " la chaîne de liens et ne fait plus partie de la liste.

Aperçu des méthodes

LinkedList a beaucoup de méthodes en commun avec ArrayList . Par exemple, les deux classes ont des méthodes telles que add() , remove() , indexOf() , clear() , contains() (indique si un élément est dans la liste), set() (remplace un élément existant) et taille() . Bien que beaucoup d'entre eux fonctionnent différemment en interne (comme nous l'avons constaté avec add() et remove() ), le résultat final est le même. Cependant, LinkedList a des méthodes distinctes pour travailler avec le début et la fin de la liste, ce qu'ArrayList n'a pas :

addFirst() , addLast() : Ces méthodes pour ajouter un élément au début/à la fin de la liste

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

Sortie : [Voiture{model='Ferrari 360 Spider'}, Voiture{model='Bugatti Veyron'}, Voiture{model='Lamborghini Diablo'}] [Voiture{model='Ford Mondeo'}, Voiture{model=' Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}] On se retrouve avec "Ford" en tête de liste , et "Fiat" à la fin.

peekFirst() , peekLast() : Les méthodes renvoient le premier/dernier élément de la liste. Ils retournent null si la liste est vide.

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

Sortie : Voiture{model='Ferrari 360 Spider'} Voiture{model='Lamborghini Diablo'}

pollFirst() , pollLast() : Ces méthodes renvoient le premier/dernier élément de la liste et le suppriment de la liste. Ils retournent null si la liste est vide

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println ("What's on the list?");
   System.out.println(cars);
}

Sortie : Car{model='Ferrari 360 Spider'} Car{model='Lamborghini Diablo'} Que reste-t-il sur la liste ? [Voiture{model='Bugatti Veyron'}]

toArray() : Cette méthode renvoie un tableau contenant les éléments de la liste

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

Sortie : [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] Nous savons maintenant comment LinkedList fonctionne et comment son organisation diffère de ArrayList . Quels sont les avantages d'utiliser LinkedList ? Surtout, on gagne quand on travaille en milieu de liste. Les opérations d'insertion et de suppression au milieu d'une LinkedList sont beaucoup plus simples que dans une ArrayList . Nous mettons simplement à jour les liens des éléments voisins, et l'élément indésirable "sort" de la chaîne de liens. Mais dans une ArrayList , nous devons

vérifier s'il y a suffisamment d'espace (lors de l'insertion)
sinon, nous créons un nouveau tableau et y copions les données (lors de l'insertion)
on retire/insère l'élément, et on déplace tous les autres éléments vers la droite/gauche (selon le type d'opération). Et la complexité de ce processus dépend fortement de la taille de la liste. C'est une chose de copier/déplacer 10 éléments, et c'en est une autre de faire la même chose avec un million d'éléments.

En d'autres termes, si les opérations d'insertion/suppression au milieu de la liste sont les plus courantes dans votre programme, LinkedList devrait être plus rapide que ArrayList .

En théorie

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Sortie : temps pris par LinkedList (en millisecondes) = 1873

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Sortie : Temps pris par ArrayList (en millisecondes) = 181 C'était inattendu ! Nous avons effectué une opération là où LinkedList devrait être beaucoup plus efficace : insérer 100 éléments au milieu d'une liste. Et notre liste est énorme : 5 000 000 d'éléments. ArrayList devait déplacer quelques millions d'éléments à chaque insertion ! Comment a-t-il gagné ? Tout d'abord, le temps nécessaire à ArrayList pour accéder aux éléments est fixe (constant). Quand tu écris

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

alors ArrayList [2_000_000] est une adresse mémoire spécifique (après tout, la liste a un tableau interne). Mais, une LinkedList n'a pas de tableau. Il recherchera l'élément numéro 2_000_000 le long de la chaîne de liens. Pour LinkedList, ce n'est pas une adresse mémoire, mais un lien qui doit encore être atteint : fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next……… En conséquence, lors de chaque insertion (suppression) au milieu de la liste , ArrayList connaît déjà l'adresse mémoire exacte à laquelle accéder, mais LinkedList doit encore "y arriver". Deuxièmement, il y a la structure de la ArrayListlui-même. Une fonction interne spéciale ( System.arrayCopy() ) développe le tableau interne et copie et décale tous les éléments. Il est très rapide, car optimisé pour ce travail spécifique. Mais lorsque vous n'avez pas à "accéder" à un index particulier, LinkedList est le gagnant. Supposons que nous insérions au tout début de la liste. Essayons d'y insérer un million d'éléments :

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       // Write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
       System.out.println("The result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

Sortie : Le résultat en millisecondes : 43448 Le résultat en millisecondes : 107 Nous obtenons maintenant un résultat complètement différent ! ArrayList a passé plus de 43 secondes à insérer un million d'éléments au début de la liste, tandis que LinkedList a réussi à le faire en 0,1 seconde ! LinkedList en a profité ici, car il n'a pas eu à parcourir la chaîne de liens jusqu'au milieu de la liste à chaque fois. Il trouve immédiatement l'index nécessaire au début de la liste, donc l'algorithme différent est déjà un avantage. :) En fait, la discussion " ArrayList contre LinkedList " est très répandue, et nous n'allons pas plonger dans le détail au niveau actuel. La chose principale dont vous devez vous souvenir est celle-ci :

Tous les avantages théoriques d'une collection particulière ne fonctionnent pas toujours dans la réalité (nous l'avons vu avec l'exemple impliquant le milieu de la liste)
N'adoptez pas une position extrême quand il s'agit de choisir une collection (" ArrayList est toujours plus rapide. Utilisez-le et vous ne pouvez pas vous tromper. Personne n'utilise LinkedList depuis longtemps").

Bien que même l'auteur de LinkedList , Joshua Bloch, affirme que c'est le cas. :) Pourtant, cette perspective est loin d'être correcte à 100 %, et nous nous en sommes convaincus. Dans notre exemple précédent, LinkedList était 400 (!) fois plus rapide. Une autre chose est qu'il y a vraiment peu de situations où LinkedList est le meilleur choix. Mais ils existent, et au bon moment LinkedListpeut vous récompenser généreusement. N'oubliez pas ce que nous avons dit au début de la leçon : les structures de données les plus efficaces sont différentes pour différentes tâches. Il est impossible d'être sûr à 100 % de la meilleure structure de données tant que vous ne connaissez pas toutes les conditions de votre tâche. Vous en saurez plus sur ces collections plus tard, ce qui facilitera le choix. Mais l'option la plus simple et la plus efficace est toujours la même : essayez les deux sur les données réelles utilisées dans votre programme. Ensuite, vous pourrez voir par vous-même comment les deux types de listes fonctionnent et vous ne vous tromperez certainement pas. :) Pour renforcer ce que vous avez appris, nous vous suggérons de regarder une leçon vidéo de notre cours Java

Plus de lecture :
Structure de données Java LinkedList