Einführung in die LinkedList-Sammlung

1. Geschichte vonLinkedList

Java verfügt über eine weitere Sammlungsklasse, die von der Sprache C++ geerbt wurde. Dies ist die LinkedListKlasse, die eine „verknüpfte Liste“ implementiert.

Äußerlich LinkedListscheint a dasselbe zu sein wie ein ArrayList. Die LinkedListKlasse verfügt über dieselben Methoden wie die ArrayListKlasse. Im Prinzip können Sie immer a LinkedListstatt an verwenden ArrayListund alles wird funktionieren.

Warum brauchen wir also eine weitere Listenklasse?

Die Antwort hat alles mit der internen Struktur der LinkedListKlasse zu tun. Anstelle eines Arrays wird eine doppelt verknüpfte Liste verwendet . Was das ist, erklären wir etwas später.

Aufgrund der LinkedListunterschiedlichen internen Struktur der Klasse können Elemente am schnellsten in die Mitte der Liste eingefügt werden.

Im Internet findet man häufig Vergleiche der ArrayListund- LinkedListKlassen:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Alles scheint klar genug: Wenn Sie häufig Elemente in die Liste einfügen müssen, verwenden Sie LinkedList; Wenn selten, dann verwenden Sie ArrayList. Doch die Realität sieht etwas anders aus.

2. Niemand benutztLinkedList

Niemand nutzt LinkedList.

Sogar der Autor des LinkedListKurses twitterte kürzlich: „Benutzt irgendjemand tatsächlich LinkedList? Ich habe es geschrieben und benutze es nie.“

Also, was ist der Deal?

Erstens konnte die Klasse sehr schnell Elemente in die Mitte der Liste einfügen. ArrayListWenn Sie ein Element in der Mitte der Liste einfügen, müssen Sie alle Elemente nach der Einfügemarke um 1 zum Ende der Liste verschieben. Früher dauerte das einige Zeit.

Aber jetzt hat sich alles verändert. Alle Elemente eines Arrays befinden sich nahe beieinander im selben Speicherblock, sodass die Operation zum Verschieben der Elemente durch einen sehr schnellen Low-Level-Befehl ausgeführt wird: .System.arraycopy()

Darüber hinaus verfügen heutige Prozessoren über einen großen Cache, der normalerweise das gesamte Array aufnehmen kann, wodurch die Array-Elemente innerhalb des Caches und nicht im Speicher verschoben werden können. Eine Million Elemente können problemlos in einer einzigen Millisekunde verschoben werden.

Zweitens kann die LinkedListKlasse Elemente schnell einfügen, wenn Sie sie mithilfe eines Iterators einfügen. Wenn Sie einen Iterator verwenden, um einen zu durchlaufen LinkedListund ständig neue Elemente einzufügen (oder vorhandene zu entfernen), ist der Vorgang superschnell.

Wenn Sie einfach Elemente zu einem LinkedListObjekt innerhalb einer Schleife hinzufügen, wird jeder schnelle Einfügevorgang von einem langsamen „Element abrufen“-Vorgang begleitet.

Die Realität liegt viel näher daran:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Warum ist das Abrufen eines Elements ein LinkedListso langsamer Vorgang?

Sie können diese Frage beantworten, nachdem Sie sich ein wenig mit der LinkedListStruktur vertraut gemacht haben.

3. Wie LinkedListist aufgebaut ?

LinkedListhat eine andere interne Struktur als ArrayList. Es gibt kein internes Array zum Speichern von Elementen. Stattdessen wird eine Datenstruktur verwendet, die als doppelt eingefärbte Liste bezeichnet wird .

Jedes Element einer doppelt verknüpften Liste speichert einen Verweis auf das vorherige und das nächste Element. Das ist ein bisschen wie eine Warteschlange in einem Geschäft, wo sich jeder an die Person erinnert, die vor ihm steht, sowie an die Person, die hinter ihm steht.

So sieht eine solche Liste im Speicher aus:

Der Kopf und das Ende (Zellen mit grauem Hintergrund) sind die firstund- lastVariablen, die Verweise auf NodeObjekte speichern.

In der Mitte befindet sich eine Kette von NodeObjekten (Objekte, keine Variablen). Jeder von ihnen besteht aus drei Feldern:

• prev– speichert einen Verweis (Link) zum vorherigen NodeObjekt (Zellen mit gelbem Hintergrund).
• value– speichert den Wert dieses Elements der Liste (Zellen mit grünem Hintergrund).
• next— speichert einen Verweis (Link) zum nächsten NodeObjekt (Zellen mit blauem Hintergrund)

Das zweite Objekt (Adresse F24) ist das nächste ( next) für das erste Objekt und das vorherige ( prev) für das dritte Objekt. Das gelbe Feld des dritten Objekts enthält die Adresse F24 und das blaue Feld des ersten Objekts enthält die Adresse F24.

Die Pfeile vom ersten und dritten Objekt zeigen auf dasselbe zweite Objekt. Es wäre also richtiger, die Pfeile so zu zeichnen.

4. Fügen Sie ein Element in eine verknüpfte Liste ein

Um jemanden auf diese Weise in die Reihe aufzunehmen, müssen Sie lediglich die Erlaubnis zweier nebeneinander stehender Personen einholen. Die erste Person erinnert sich an den Neuankömmling als „die Person hinter mir“, und die zweite Person erinnert sich an ihn als „die Person vor mir“.

Sie müssen lediglich die Referenzen der beiden benachbarten Objekte ändern:

Wir haben unserer Liste ein neues Element hinzugefügt, indem wir die Referenzen des zweiten und dritten Objekts geändert haben. Das neue Objekt ist das nächste für das alte zweite Objekt und das vorherige für das alte dritte Objekt. Und natürlich muss das neue Objekt selbst die richtigen Referenzen speichern: Sein vorheriges Objekt ist das alte zweite Objekt und sein nächstes Objekt ist das alte dritte Objekt.

nextDas Entfernen eines Elements ist noch einfacher: Wenn wir beispielsweise das 100. Objekt aus der Liste entfernen möchten, müssen wir nur das Feld für das 99. Objekt so ändern, dass es auf das 101. Objekt zeigt, und das prevFeld für das 101. ändern Objekt so, dass es auf die 99. zeigt. Das ist es.

Aber das 100. Objekt zu bekommen ist nicht so einfach.

5. Entfernen Sie ein Element aus einer Liste

Um das 100. Element einer verknüpften Liste zu erhalten, müssen Sie Folgendes tun:

Holen Sie sich das 1. Objekt: Sie tun dies mithilfe der firstVariablen im LinkedListObjekt. Das nextFeld des 1. Objekts speichert einen Verweis auf das 2. Objekt. So erhalten wir das zweite Objekt. Das zweite Objekt hat einen Verweis auf das dritte und so weiter.

Wenn wir einen Verweis auf das 100. Objekt benötigen, müssen wir nacheinander alle Objekte vom 1. bis zum 100. durchlaufen. Und wenn wir das millionste Element in einer Liste benötigen, müssen wir über eine Million Objekte nacheinander iterieren!

Und wenn diese Objekte zu unterschiedlichen Zeitpunkten zur Liste hinzugefügt wurden, befinden sie sich in unterschiedlichen Teilen des Speichers und landen wahrscheinlich nicht gleichzeitig im Cache des Prozessors. Das bedeutet, dass die Iteration über die Elemente einer verknüpften Liste nicht nur langsam, sondern sehr langsam ist.

Damit haben wir es zu tun.

Warum bringen wir Ihnen also bei, wie dieses Slow LinkedListfunktioniert?

Nun, bei Vorstellungsgesprächen werden Sie gefragt, was der LinkedListUnterschied zuArrayList . Definitiv.