Liste liée en Java

Bonjour! Toutes les conférences récentes ont été consacrées à l'étude de la liste ArrayList . Cette structure de données est très pratique et permet de résoudre de nombreux problèmes. Cependant, Java possède de nombreuses autres structures de données. Pourquoi? Tout d'abord, parce que l'éventail des tâches existantes est très large et que pour différentes tâches, différentes structures de données sont les plus efficaces . Aujourd'hui, nous allons nous familiariser avec une nouvelle structure - une liste doublement chaînée LinkedList . Voyons comment cela fonctionne, pourquoi on l'appelle doublement connecté et en quoi il diffère de ArrayList . Dans une LinkedList, les éléments sont en réalité des maillons d’une chaîne. Chaque élément, en plus des données qu'il stocke, possède un lien vers l'élément précédent et suivant . Ces liens permettent de passer d'un élément à un autre. Il est créé ainsi :

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

Conclusion:

[Hello World! My name is Earl, I love Java, I live in Moscow]

Voici à quoi ressemblera la structure de notre liste : Voyons comment un nouvel élément est ajouté. Cela se fait en utilisant le add().

earlBio.add(str2);

Au moment de cette ligne de code, notre liste se compose d'un seul élément : la chaîne str1. Voyons ce qui se passe ensuite dans l'image : En conséquence str2, et str1devenez connecté via les liens qui y sont stockés nextet previous: Vous devriez maintenant comprendre l'idée principale d'une liste doublement chaînée. Les éléments LinkedListconstituent une liste unique précisément grâce à cette chaîne de maillons. Il n'y a pas de tableau à l'intérieur LinkedList, comme dans ArrayList, ou quelque chose de similaire. Tout le travail avec ArrayList (dans l'ensemble) se résume à travailler avec le tableau interne. Tout travail avec LinkedListse résume à changer les liens. Cela se voit très clairement en ajoutant un élément au milieu de la liste :

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

Comme vous pouvez le constater, la méthode surchargée add()vous permet de spécifier un index spécifique pour le nouvel élément. Dans ce cas, nous souhaitons ajouter une ligne str2entre str1et str3. Voici ce qui se passera à l'intérieur : Et suite à la modification des liens internes, l'élément str2est ajouté avec succès à la liste : Désormais, les 3 éléments sont liés. Du premier élément de la chaîne, nextvous pouvez aller jusqu'au dernier et revenir en arrière. Nous avons plus ou moins compris l'insertion, mais qu'en est-il de la suppression d'éléments ? Le principe de fonctionnement est le même. On redéfinit simplement les liens des deux éléments « sur les côtés » de celui à supprimer :

public class Main {

   public static void main(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 Moscow");

       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 passera si l'on supprime l'élément d'index 1 (il est au milieu de la liste) : Après avoir redéfini les liens, on obtient le résultat souhaité : contrairement à la suppression, il ArrayListn'y a pas de décalage des éléments du tableau et autres. Nous redéfinissons simplement les références des éléments str1et str3. Maintenant, ils pointent l'un vers l'autre, et l'objet str2a « abandonné » cette chaîne de maillons et ne fait plus partie de la liste.

Aperçu des méthodes

Il LinkedListprésente de nombreuses similitudes avec ArrayListles méthodes. Par exemple, des méthodes telles que add(), remove(), indexOf(), clear(), contains()(est l'élément contenu dans la liste), set()(insertion d'un élément avec remplacement) size()sont présentes dans les deux classes. Bien que (comme nous l'avons découvert dans l'exemple add()et remove()) beaucoup d'entre eux fonctionnent différemment en interne, ils font finalement la même chose. Cependant, il LinkedListdispose de méthodes distinctes pour travailler avec le début et la fin de la liste, qui ne sont pas présentes dansArrayList :

• addFirst(), addLast(): méthodes pour ajouter un élément au début/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 + '\'' +
               '}';
   }
}

Conclusion:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
[Car{model='Ford Mondeo'}, Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}]

En conséquence, Ford s'est retrouvé en tête de liste et Fiat à la fin.

• peekFirst(), peekLast(): renvoie le premier/dernier élément de la liste. Renvoie nullsi 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());
}

Conclusion:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}

• pollFirst(), pollLast(): renvoie le premier/dernier élément de la liste et le supprime de la liste . Retourne nullsi 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 left on the list?");
   System.out.println(cars);
}

Conclusion:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What осталось в списке?
[Car{model='Bugatti Veyron'}]

• toArray(): renvoie un tableau d'éléments de 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));
}

Conclusion:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]

Nous savons maintenant comment cela fonctionne LinkedListet en quoi cela diffère de ArrayList. Quels sont les avantages de son utilisation LinkedList? Tout d'abord, en travaillant avec le milieu de la liste . L'insertion et la suppression au milieu LinkedListsont beaucoup plus simples que dans ArrayList. Nous redéfinissons simplement les maillons des éléments voisins, et l'élément inutile « tombe » de la chaîne de maillons. Pendant que ArrayListnous sommes :

• vérifiez s'il y a suffisamment d'espace (lors de l'insertion)
• si cela ne suffit pas, créez un nouveau tableau et copiez-y les données (lors du collage)
• supprimer/insérer un élément et décaler tous les autres éléments vers la droite/gauche (selon le type d'opération). De plus, la complexité de ce processus dépend grandement de la taille de la liste. C'est une chose de copier/déplacer 10 éléments, mais une autre de faire la même chose avec un million d'éléments.

Autrement dit, si dans votre programme les opérations d'insertion/suppression se produisent plus souvent au milieu de la liste, LinkedListelles devraient être plus rapides 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 to run for LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Conclusion:

Время работы для LinkedList (в мorсекундах) = 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 to run for ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Conclusion:

Время работы для ArrayList (в миллисекундах) = 181

Soudainement! Il semblerait que nous effectuions une opération qui LinkedListaurait dû être beaucoup plus efficace : insérer 100 éléments au milieu de la liste. Et notre liste est énorme - 5 000 000 d'éléments : ArrayListnous avons dû décaler quelques millions d'éléments à chaque fois que nous les insérions ! Quelle est la raison de sa victoire ? Premièrement, un élément est accessible dans ArrayListun laps de temps fixe. Lorsque vous indiquez :

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

alors dans le cas de ArrayList[2_000_000] il s'agit d'une adresse spécifique en mémoire, car elle contient un tableau. Alors que le LinkedListtableau ne le fait pas. Il recherchera l'élément numéro 2_000_000 le long de la chaîne de maillons. Pour lui, il ne s’agit pas d’une adresse en mémoire, mais d’un lien qu’il reste encore à atteindre :

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………

De ce fait, à chaque insertion (suppression) au milieu de la liste, ArrayListil connaît déjà l'adresse exacte en mémoire à laquelle il doit accéder, mais LinkedListil lui reste encore à « se retrouver » au bon endroit. Deuxièmement , le problème réside dans la structure de ArrayList« a » lui-même. L'extension du tableau interne, la copie de tous les éléments et le déplacement des éléments sont effectués par une fonction interne spéciale - System.arrayCopy(). Cela fonctionne très rapidement car il est spécialement optimisé pour ce travail. Mais dans les situations où il n'est pas nécessaire de « piétiner » jusqu'à l'index souhaité, LinkedListcela se montre vraiment mieux. Par exemple, si l'insertion a lieu au 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("Result in milliseconds: " + msDelay);
       return msDelay;

   }

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

}

Conclusion:

Результат в миллисекундах: 43448
Результат в миллисекундах: 107

Un résultat complètement différent ! Il a fallu plus de 43 secondes pour insérer un million d'éléments au début de la liste ArrayList, alors LinkedListqu'il a été complété en 0,1 seconde ! C’est précisément le fait que dans cette situation, LinkedListnous n’avons pas eu à chaque fois « parcourir » la chaîne des maillons jusqu’au milieu de la liste. Il a immédiatement trouvé l'index recherché au début de la liste, et là la différence de principes de fonctionnement était déjà de son côté :) En fait, la discussion « ArrayListversus LinkedList» est très répandue, et nous n'y reviendrons pas en profondeur à l'heure actuelle. niveau. La principale chose à retenir :

• Tous les avantages d'une collection particulière « sur papier » ne fonctionneront pas dans la réalité (nous l'avons examiné en utilisant l'exemple du milieu de la liste)
• Il ne faut pas aller aux extrêmes dans le choix d’une collection (« ArrayListc’est toujours plus rapide, utilisez-la et vous ne vous tromperez pas. LinkedListPersonne ne l’utilise depuis longtemps »).

Bien que même le créateur LinkedListJoshua Bloch le dise :) Cependant, ce point de vue est loin d'être correct à 100%, et nous en sommes convaincus. Dans notre exemple précédent, LinkedListcela fonctionnait 400 (!) fois plus vite. Une autre chose est qu’il existe très peu de situations dans lesquelles LinkedListce serait le meilleur choix. Mais ils existent, et au bon moment, LinkedListils peuvent sérieusement vous aider. N'oubliez pas ce dont nous avons parlé au début de la conférence : différentes structures de données sont plus efficaces pour différentes tâches. Il est impossible de dire avec une certitude à 100 % quelle structure de données sera la meilleure tant que toutes les conditions du problème ne seront pas connues. Plus tard, vous en saurez plus sur ces collections et il vous sera plus facile de faire un choix. Mais l’option la plus simple et la plus efficace est toujours la même : tester les deux sur des données réelles de votre programme. Ensuite, vous pourrez voir de vos propres yeux les résultats des deux listes et vous ne vous tromperez certainement pas :)