LinkedList in Java

Hallo! Alle neueren Vorlesungen waren dem Studium der ArrayList- Liste gewidmet . Diese Datenstruktur ist sehr praktisch und ermöglicht die Lösung vieler Probleme. Java verfügt jedoch über viele andere Datenstrukturen. Warum? Erstens, weil das Spektrum der vorhandenen Aufgaben sehr groß ist und für verschiedene Aufgaben unterschiedliche Datenstrukturen am effektivsten sind . Heute lernen wir eine neue Struktur kennen – eine doppelt verknüpfte Liste LinkedList . Lassen Sie uns herausfinden, wie es funktioniert, warum es doppelt verbunden heißt und wie es sich von ArrayList unterscheidet . In einer LinkedList sind die Elemente tatsächlich Glieder einer Kette. Jedes Element verfügt zusätzlich zu den darin gespeicherten Daten über einen Link zum vorherigen und nächsten Element . Mit diesen Links können Sie von einem Element zum anderen wechseln. Es wird so erstellt:

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);

   }
}

Abschluss:

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

So sieht die Struktur unserer Liste aus: Schauen wir uns an, wie ein neues Element hinzugefügt wird. Dies erfolgt über die add().

earlBio.add(str2);

Zum Zeitpunkt dieser Codezeile besteht unsere Liste aus einem Element – ​​dem string str1. Schauen wir uns an, was als nächstes im Bild passiert: Als Ergebnis werden str2, und str1durch die darin gespeicherten Links verbunden nextund previous: Jetzt sollten Sie die Grundidee einer doppelt verknüpften Liste verstehen. LinkedListGerade dank dieser Verknüpfungskette bilden die Elemente eine einzige Liste. LinkedListEs gibt kein Array wie in oder ArrayListetwas Ähnliches. Die gesamte Arbeit mit ArrayList läuft (im Großen und Ganzen) auf die Arbeit mit dem internen Array hinaus. Die ganze Arbeit LinkedListläuft darauf hinaus, die Links zu ändern. Dies wird sehr deutlich, wenn man in der Mitte der Liste ein Element hinzufügt:

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);

   }
}

Wie Sie sehen, add()können Sie mit der überladenen Methode einen bestimmten Index für das neue Element angeben. str2In diesem Fall möchten wir eine Zeile zwischen str1und hinzufügen str3. Folgendes wird im Inneren passieren: Und durch die Änderung der internen Links str2wird das Element erfolgreich zur Liste hinzugefügt: Jetzt sind alle 3 Elemente verknüpft. Vom ersten Element entlang der Kette nextkönnen Sie zum letzten und zurück gehen. Wir haben das Einfügen mehr oder weniger herausgefunden, aber wie sieht es mit dem Löschen von Elementen aus? Das Funktionsprinzip ist das gleiche. Wir definieren einfach die Verknüpfungen der beiden Elemente „an den Seiten“ des zu entfernenden Elements neu:

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);
   }
}

Folgendes passiert, wenn wir das Element mit Index 1 löschen (es befindet sich in der Mitte der Liste): Nach der Neudefinition der Verknüpfungen erhalten wir das gewünschte Ergebnis: Im Gegensatz zum Löschen ArrayListkommt es zu keinen Verschiebungen von Array-Elementen und dergleichen. Wir definieren einfach die Referenzen der str1und- Elemente neu str3. Jetzt zeigen sie aufeinander und das Objekt str2ist aus dieser Gliederkette „herausgefallen“ und nicht mehr Teil der Liste.

Methodenübersicht

Es LinkedListweist viele Ähnlichkeiten mit ArrayListden Methoden auf. Beispielsweise sind Methoden wie add(), remove(), indexOf(), clear(), contains()(ist das in der Liste enthaltene Element) set()(Einfügen eines Elements mit Ersetzung) size()in beiden Klassen vorhanden. add()Zwar arbeiten (wie wir im Beispiel und herausgefunden haben remove()) viele von ihnen intern unterschiedlich, aber letztendlich machen sie das Gleiche. Es verfügt jedoch LinkedListüber separate Methoden zum Arbeiten mit dem Anfang und Ende der Liste, die in nicht vorhanden sind ArrayList:

• addFirst(), addLast(): Methoden zum Hinzufügen eines Elements am Anfang/Ende der 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 + '\'' +
               '}';
   }
}

Abschluss:

[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'}]

Infolgedessen landete Ford ganz oben auf der Liste und Fiat am Ende.

• peekFirst(), peekLast(): Gibt das erste/letzte Element der Liste zurück. Gibt zurück null, wenn die Liste leer ist.

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());
}

Abschluss:

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

• pollFirst(), pollLast(): Gibt das erste/letzte Element der Liste zurück und entfernt es aus der Liste . Gibt zurück null, wenn die Liste leer ist

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(„Was steht noch auf der Liste?“);
   System.out.println(cars);
}

Abschluss:

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

• toArray(): Gibt ein Array von Listenelementen zurück

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));
}

Abschluss:

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

Jetzt wissen wir, wie es funktioniert LinkedListund wie es sich von unterscheidet ArrayList. Welche Vorteile bietet die Verwendung LinkedList? Zunächst einmal bei der Arbeit mit der Mitte der Liste . Das Einfügen und Löschen in der Mitte LinkedListist viel einfacher als in ArrayList. Wir definieren einfach die Verknüpfungen benachbarter Elemente neu und das unnötige Element „fällt“ aus der Verknüpfungskette heraus. Während ArrayListwir hier sind:

• Prüfen Sie, ob genügend Platz vorhanden ist (beim Einfügen)
• Wenn es nicht ausreicht, erstellen Sie ein neues Array und kopieren Sie die Daten dorthin (beim Einfügen).
• Löschen/Einfügen eines Elements und Verschieben aller anderen Elemente nach rechts/links (abhängig von der Art der Operation). Darüber hinaus hängt die Komplexität dieses Prozesses stark von der Größe der Liste ab. Es ist eine Sache, 10 Elemente zu kopieren/verschieben, aber eine ganz andere, dasselbe mit einer Million Elementen zu tun.

Das heißt, wenn in Ihrem Programm Einfüge-/Löschvorgänge in der Mitte der Liste häufiger vorkommen, LinkedListsollte dies schneller sein als ArrayList.

In der Theorie

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(„Laufzeit für LinkedList (in Millisekunden) =“ + (System.currentTimeMillis()-start));
   }
}

Abschluss:

Время работы для LinkedList (в мoderсекундах) = 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(„Laufzeit für ArrayList (in Millisekunden) =“ + (System.currentTimeMillis()-start));
   }
}

Abschluss:

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

Plötzlich! Es scheint, dass wir eine Operation durchgeführt haben, die LinkedListviel effizienter hätte sein sollen – das Einfügen von 100 Elementen in die Mitte der Liste. Und unsere Liste ist riesig – 5.000.000 Elemente: ArrayListWir mussten jedes Mal, wenn wir sie einfügten, ein paar Millionen Elemente verschieben! Was ist der Grund für seinen Sieg? Zunächst wird in ArrayListeiner festgelegten Zeitspanne auf ein Element zugegriffen. Wenn Sie Folgendes angeben:

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

dann ist dies im Fall von ArrayList[2_000_000] eine bestimmte Adresse im Speicher, da darin ein Array enthalten ist. Während das LinkedListArray dies nicht tut. Entlang der Gliederkette wird nach dem Element mit der Nummer 2_000_000 gesucht. Für ihn handelt es sich hierbei nicht um eine Adresse im Gedächtnis, sondern um einen Link, der noch erreicht werden muss:

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

Dadurch ArrayListkennt es bei jedem Einfügen (Löschen) in der Mitte der Liste bereits die genaue Adresse im Speicher, auf die es zugreifen soll, LinkedListmuss aber noch die richtige Stelle „herausfinden“. Zweitens liegt die Materie in der Struktur von ArrayList„a“ selbst. Das Erweitern des internen Arrays, das Kopieren aller Elemente und das Verschieben von Elementen erfolgt durch eine spezielle interne Funktion - System.arrayCopy(). Es arbeitet sehr schnell, da es speziell für diese Aufgabe optimiert ist. Aber in Situationen, in denen es nicht nötig ist, zum gewünschten Index zu „stapfen“, LinkedListzeigt es sich wirklich besser. Zum Beispiel, wenn die Einfügung am Anfang der Liste erfolgt. Versuchen wir, dort eine Million Elemente einzufügen:

public class Main {

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

   public static long getTimeMsOfInsert(List list) {
       //Schreiben Sie hier Ihren Code
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); //Berechnen Sie die Differenz
       System.out.println(„Ergebnis in Millisekunden:“ + msDelay);
       return msDelay;

   }

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

}

Abschluss:

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

Ein völlig anderes Ergebnis! Das Einfügen einer Million Elemente am Anfang der Liste dauerte mehr als 43 Sekunden ArrayList, während LinkedListes in 0,1 Sekunden abgeschlossen war! Gerade weil LinkedListwir in dieser Situation nicht jedes Mal durch die Gliederkette bis zur Mitte der Liste „laufen“ mussten. Den gesuchten Index fand er sofort am Anfang der Liste und schon war der Unterschied in den Funktionsprinzipien auf seiner Seite :) Tatsächlich ist die „ ArrayListversus LinkedList“-Diskussion sehr weit verbreitet, und wir werden zum jetzigen Zeitpunkt nicht näher darauf eingehen Ebene. Das Wichtigste, was Sie beachten müssen:

• Nicht alle Vorteile einer bestimmten Sammlung „auf dem Papier“ funktionieren in der Realität (wir haben uns das am Beispiel aus der Mitte der Liste angesehen)
• Sie sollten bei der Auswahl einer Sammlung nicht ins Extreme gehen („ ArrayListEs geht immer schneller, verwenden Sie es und Sie werden sich nicht irren. LinkedListNiemand hat es schon lange verwendet“).

Obwohl LinkedListdas sogar der Schöpfer Joshua Bloch sagt :) Allerdings ist dieser Standpunkt bei weitem nicht 100 % richtig und wir sind davon überzeugt. In unserem vorherigen Beispiel LinkedListfunktionierte es 400 (!) Mal schneller. Eine andere Sache ist, dass es wirklich wenige Situationen gibt, in denen LinkedListes die beste Wahl wäre. Aber es gibt sie, und zum richtigen Zeitpunkt LinkedListkönnen sie Ihnen ernsthaft helfen. Vergessen Sie nicht, worüber wir zu Beginn der Vorlesung gesprochen haben: Unterschiedliche Datenstrukturen sind für unterschiedliche Aufgaben am effektivsten. Es ist unmöglich, mit hundertprozentiger Sicherheit zu sagen, welche Datenstruktur besser ist, bis alle Bedingungen des Problems bekannt sind. Später erfahren Sie mehr über diese Kollektionen und können leichter eine Auswahl treffen. Die einfachste und effektivste Option ist jedoch immer dieselbe: Testen Sie beides anhand realer Daten aus Ihrem Programm. Dann können Sie die Ergebnisse beider Listen mit eigenen Augen sehen und werden garantiert nichts falsch machen :)