Java LinkedList

Hallo! Alle letzten Lektionen waren ArrayList gewidmet . Diese Datenstruktur ist sehr praktisch und nützlich. Es kann viele Aufgaben bewältigen. Aber Java hat viele andere Datenstrukturen. Warum? Vor allem, weil das Aufgabenspektrum enorm ist und die effizientesten Datenstrukturen für verschiedene Aufgaben unterschiedlich sind. Heute lernen wir eine neue Struktur kennen: Java LinkedList , eine doppelt verknüpfte Liste.

Sehen wir uns an, wie es organisiert ist, warum es doppelt verknüpft heißt und wie es sich von ArrayList unterscheidet . Die Elemente in einer Java LinkedList sind tatsächlich Links in einer einzelnen Kette. Zusätzlich zu den Daten speichert jedes Element Verweise auf das vorherige und das nächste Element. Mit diesen Referenzen können Sie von einem Element zum anderen wechseln. So erstellen Sie eines:

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

   }
}

Ausgabe: [Hallo Welt! Mein Name ist Earl, ich liebe Java, ich lebe in Kanada] So sieht unsere Liste aus: LinkedList – 2

Mal sehen, wie man ein neues Element hinzufügt. Dies geschieht mit der Methode add() .

earlBio.add(str2);

An der Stelle im Code besteht unsere Liste aus einem Element: dem String str1 . Schauen wir uns an, was als nächstes im Bild passiert: LinkedList – 3

Dadurch werden str2 und str1 über die in diesen Knoten der Liste gespeicherten nächsten und vorherigen Links verknüpft : LinkedList – 4

Jetzt sollten Sie die Grundidee einer doppelt verknüpften Liste verstehen. Genau diese Verknüpfungskette macht LinkedList- Elemente zu einer einzigen Liste. Im Gegensatz zu ArrayList enthält LinkedList kein Array oder etwas Array-ähnliches. Jede (naja, die meiste) Arbeit mit ArrayList läuft darauf hinaus, mit dem internen Array zu arbeiten. Jede Arbeit mit Java LinkedListläuft darauf hinaus, Links zu ändern. Dies lässt sich sehr deutlich erkennen, wenn man in der Mitte der Liste ein Element hinzufügt:

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

   }
}

Wie Sie sehen, können Sie mit der überladenen add()- Methode einen bestimmten Index für ein neues Element angeben. In diesem Fall möchten wir String str2 zwischen str1 und str3 hinzufügen . Folgendes wird intern passieren: LinkedList – 5

Nach der Änderung der internen Links wurde str2 erfolgreich zur Liste hinzugefügt: LinkedList – 6

Jetzt sind alle 3 Elemente verbunden. Über das nächste Glied können Sie vom ersten Element der Kette zum letzten und wieder zurück wechseln. Mit dem Einfügen sind wir also ziemlich vertraut, aber wie sieht es mit dem Entfernen von Elementen aus? Das Prinzip ist genau das gleiche. Wir aktualisieren lediglich die Links in den beiden Elementen „links und rechts“ des zu entfernenden Elements:

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

Folgendes passiert, wenn wir das Element mit Index 1 löschen (es befindet sich in der Mitte der Liste): LinkedList – 7

Nach dem Aktualisieren der Links erhalten wir das gewünschte Ergebnis: LinkedList – 8

Im Gegensatz zur Entfernungsoperation in ArrayList besteht hier keine Notwendigkeit, Array-Elemente zu verschieben oder zu tun irgendetwas in der Art. Wir aktualisieren lediglich die Links für str1 und str3 . Sie zeigen nun aufeinander und str2 ist aus der Gliederkette „ herausgefallen “ und nicht mehr Teil der Liste.

Methodenübersicht

LinkedList hat viele Methoden mit ArrayList gemeinsam . Beispielsweise verfügen beide Klassen über Methoden wie add() , remove() , indexOf() , clear() , enthält() (zeigt an, ob sich ein Element in der Liste befindet), set() (ersetzt ein vorhandenes Element) und size() . Obwohl viele von ihnen intern unterschiedlich funktionieren (wie wir bei add() und remove() festgestellt haben ), ist das Endergebnis dasselbe. Allerdings verfügt LinkedList über separate Methoden zum Arbeiten mit dem Anfang und Ende der Liste, die ArrayList nicht hat:

addFirst() , addLast() : Diese 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 + '\'' +
               '}';
   }
}

Ausgabe: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] [Car{model='Ford Mondeo'}, Car{model=' Ferrari 360 Spider'}, Auto{model='Bugatti Veyron'}, Auto{model='Lamborghini Diablo'}, Auto{model='Fiat Ducato'}] Am Ende steht „Ford“ ganz oben auf der Liste , und „Fiat“ am Ende.

peekFirst() , peekLast() : Die Methoden geben das erste/letzte Element in der Liste zurück. Sie geben null zurück , 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());
}

Ausgabe: Auto{model='Ferrari 360 Spider'} Auto{model='Lamborghini Diablo'}

pollFirst() , pollLast() : Diese Methoden geben das erste/letzte Element in der Liste zurück und entfernen es aus der Liste. Sie geben null zurück, 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 ("What's on the list?");
   System.out.println(cars);
}

Ausgabe: Auto{model='Ferrari 360 Spider'} Auto{model='Lamborghini Diablo'} Was steht noch auf der Liste? [Auto{model='Bugatti Veyron'}]

toArray() : Diese Methode gibt ein Array zurück, das die Listenelemente enthält

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

Ausgabe: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] Jetzt wissen wir, wie LinkedList funktioniert und wie sich seine Organisation von ArrayList unterscheidet . Welche Vorteile bietet die Verwendung von LinkedList ? Wir profitieren vor allem davon, wenn wir in der Mitte der Liste arbeiten. Einfügungs- und Entfernungsvorgänge in der Mitte einer LinkedList sind viel einfacher als in einer ArrayList . Wir aktualisieren einfach die Verknüpfungen benachbarter Elemente und das unerwünschte Element „fällt“ aus der Verknüpfungskette heraus. Aber in einer ArrayList müssen wir

prüfen, ob genügend Platz vorhanden ist (beim Einfügen)
wenn nicht, dann erstellen wir ein neues Array und kopieren die Daten dorthin (beim Einfügen)
Wir entfernen/fügen das Element ein und verschieben alle anderen Elemente nach rechts/links (abhängig von der Art der Operation). Und die Komplexität dieses Prozesses hängt stark von der Größe der Liste ab. Es ist eine Sache, 10 Elemente zu kopieren/verschieben, und eine ganz andere, dasselbe mit einer Million Elementen zu tun.

Mit anderen Worten: Wenn Einfüge-/Entfernungsvorgänge in der Mitte der Liste in Ihrem Programm am häufigsten vorkommen, sollte LinkedList schneller als ArrayList sein .

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("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Ausgabe: Von LinkedList benötigte Zeit (in Millisekunden) = 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));
   }
}

Ausgabe: Von ArrayList benötigte Zeit (in Millisekunden) = 181 Das war unerwartet! Wir haben eine Operation durchgeführt, bei der LinkedList viel effizienter sein sollte: das Einfügen von 100 Elementen in die Mitte einer Liste. Und unsere Liste ist riesig: 5.000.000 Elemente. ArrayList musste bei jeder Einfügung ein paar Millionen Elemente verschieben! Wie hat es gewonnen? Erstens ist die Zeit, die ArrayList benötigt, um auf Elemente zuzugreifen, fest (konstant). Wenn du schreibst

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

dann ist ArrayList [2_000_000] eine bestimmte Speicheradresse (schließlich verfügt die Liste über ein internes Array). Eine LinkedList verfügt jedoch nicht über ein Array. Entlang der Gliederkette wird nach dem Element mit der Nummer 2_000_000 gesucht. Bei LinkedList handelt es sich hierbei nicht um eine Speicheradresse, sondern um einen Link, der noch erreicht werden muss: faustElement.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……… Als Ergebnis bei jedem Einfügen (Entfernen) in der Mitte der Liste , ArrayList kennt bereits die genaue Speicheradresse, auf die zugegriffen werden soll, LinkedList muss jedoch noch „dahin gelangen“. Zweitens gibt es die Struktur der ArrayListselbst. Eine spezielle interne Funktion ( System.arrayCopy() ) erweitert das interne Array und kopiert und verschiebt alle Elemente. Es ist sehr schnell, da es für diese spezielle Arbeit optimiert ist. Wenn Sie jedoch nicht zu einem bestimmten Index gelangen müssen, ist LinkedList der Gewinner. Angenommen, wir fügen ganz am Anfang der Liste ein. 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) {
       // 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());
       }
   }

}

Ausgabe: Das Ergebnis in Millisekunden: 43448 Das Ergebnis in Millisekunden: 107 Jetzt erhalten wir ein völlig anderes Ergebnis! ArrayList hat mehr als 43 Sekunden damit verbracht, eine Million Elemente am Anfang der Liste einzufügen, während LinkedList dies in 0,1 Sekunden geschafft hat! Hier profitierte LinkedList , da es nicht jedes Mal die Linkkette bis zur Mitte der Liste durchlaufen musste. Der benötigte Index wird sofort am Anfang der Liste gefunden, sodass der unterschiedliche Algorithmus bereits von Vorteil ist. :) Tatsächlich ist die Diskussion „ ArrayList versus LinkedList “ sehr weit verbreitet und wir werden uns auf der aktuellen Ebene nicht näher damit befassen. Das Wichtigste, was Sie sich merken müssen, ist Folgendes:

Nicht alle theoretischen Vorteile einer bestimmten Sammlung funktionieren auch in der Realität (wir haben dies am Beispiel in der Mitte der Liste gesehen).
Nehmen Sie keine extreme Position ein, wenn es um die Auswahl einer Sammlung geht („ ArrayList ist immer schneller. Verwenden Sie es und Sie können nichts falsch machen. LinkedList verwendet schon lange niemand mehr“).

Obwohl sogar der Autor von LinkedList , Joshua Bloch, sagt, dass dies der Fall ist. :) Dennoch ist diese Perspektive bei weitem nicht 100 % richtig, und davon haben wir uns selbst überzeugt. In unserem vorherigen Beispiel war LinkedList 400 (!) Mal schneller. Eine andere Sache ist, dass es wirklich nur wenige Situationen gibt, in denen LinkedList die beste Wahl ist. Aber es gibt sie, und zwar im richtigen Moment LinkedListkann dich reichlich belohnen. Vergessen Sie nicht, was wir zu Beginn der Lektion gesagt haben: Die effizientesten Datenstrukturen sind für verschiedene Aufgaben unterschiedlich. Es ist unmöglich, 100 % sicher zu sein, welche Datenstruktur die beste ist, bis Sie alle Bedingungen Ihrer Aufgabe kennen. Später erfahren Sie mehr über diese Kollektionen, was Ihnen die Auswahl erleichtern wird. Die einfachste und effektivste Option ist jedoch immer dieselbe: Probieren Sie beides mit den tatsächlichen Daten aus, die in Ihrem Programm verwendet werden. Dann können Sie sich selbst davon überzeugen, wie beide Arten von Listen funktionieren, und Sie werden garantiert nichts falsch machen. :) Um das Gelernte zu vertiefen, empfehlen wir Ihnen, sich eine Videolektion aus unserem Java-Kurs anzusehen

Mehr Lektüre:
LinkedList-Java-Datenstruktur