Datenstruktur verknüpfter Listen in Java

Für unterschiedliche Zwecke werden unterschiedliche Datenstrukturen erstellt. Möglicherweise kennen Sie ArrayList (falls noch nicht bekannt ist, empfehlen wir Ihnen, sich zuerst darüber zu informieren). In diesem Artikel lernen wir LinkedList kennen und erkennen, wozu diese Sammlung gut ist. Wenn Sie sich die Codequelle der Klasse LinkedList Java 8 (oder eine spätere Version der Sprache) ansehen (auf der Oracle-Website oder in Ihrer IDE, im Fall von IDEA: Strg+B für den Klassennamen), sehen Sie die nächste Deklaration:

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

Die derzeit wichtigste Information aus dem Code ist die Tatsache, dass LinkedList List- und Deque- Schnittstellen implementiert . Die List-Schnittstelle behält die Reihenfolge des Hinzufügens von Elementen bei und ermöglicht den Zugriff auf das Element über den Index. Die „normale“ Warteschlange unterstützt das Hinzufügen von Elementen am Ende und das Extrahieren von Elementen am Anfang. Deque ist eine bidirektionale Warteschlange und unterstützt das Hinzufügen und Entfernen von Elementen auf beiden Seiten. Sie können es sich als eine Kombination aus Stapel und Warteschlange vorstellen. LinkedList ist also eine Implementierung dieser beiden und ermöglicht es uns, eine bidirektionale Warteschlange zu erstellen, die aus beliebigen Objekten einschließlich Null besteht. LinkedListist eine Sammlung von Elementen. Wir können es in der Codequelle der Klasse sehen. Achten Sie dieses Mal auf die Felder:

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

Jedes Element, normalerweise nennen wir es Node , enthält ein Objekt und Verweise auf zwei benachbarte Objekte – das vorherige und das nächste. Daher ist es im Hinblick auf die Nutzung des Speichers nicht sehr effektiv. Da es sich bei LinkedList tatsächlich um eine bidirektionale Struktur handelt, können wir problemlos Elemente auf beiden Seiten hinzufügen oder entfernen.

LinkedList-Konstruktoren

Zurück zur Codequelle können wir feststellen, dass LinkedList zwei Konstruktoren hat

• LinkedList() ohne Parameter wird verwendet, um eine leere Liste zu erstellen.
• >LinkedList(Collection<? erweitert E> c) dient zum Erstellen einer Liste mit den Elementen der angegebenen Sammlung in der Reihenfolge, in der sie vom Iterator der Sammlung zurückgegeben werden.

LinkedList-Deklaration

Tatsächlich besteht eine verknüpfte Liste (Java oder in einer anderen Sprache) aus einer Folge von Knoten. Jeder Knoten ist so konzipiert, dass er ein Objekt eines beim Erstellen definierten Typs speichert. Um LinkedList zu erstellen , ist der nächste Java-Code:

LinkedList<Integer> myList = new LinkedList<>();

Wir haben ein Objekt, um eine Folge von Ganzzahlen und Links zu den Nachbarn zu behalten. Allerdings ist es im Moment leer.

LinkedList-Hauptoperationen

Wie üblich können Sie bei Sammlungen Elemente in LinkedList einfügen (bis zum Ende oder in die Mitte), von dort entfernen und ein Element per Index erhalten. Hier sind sie also:

• add(E-Element) Hängt das angegebene Element an das Ende dieser Liste an;
• add(int index, E element) Fügt das Element an der angegebenen Position ein index ;
• get(int index) Gibt das Element an der angegebenen Position in dieser Liste zurück;
• remove(int index) Entfernt das Element, das sich an der Position index befindet;
• remove(Object o) Entfernt das erste Vorkommen von ? o Element aus dieser Liste, falls vorhanden.
• remove() Ruft das erste Element der Liste ab und entfernt es.

Implementierung einer verknüpften Liste in Java, Hinzufügen und Entfernen von Elementen. Beispiel

Lassen Sie uns diese Operationen in der Praxis ausprobieren. Zuerst die Java LinkedList-Implementierung: Erstellen einer LinkedList von Strings und Hinzufügen von drei Elementen. Dann entfernen Sie einen und fügen dann einen in der Mitte hinzu.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

Das Ergebnis der Ausführung dieses Programms:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

Eine LinkedList ist Teil des Collection- Frameworks. Sie können Iterator zum Entfernen von Elementen sowie einen speziellen Iterator für Listen verwenden – ListIterator . Darüber hinaus bieten Operationen mit Iterator die Hauptvorteile der LinkedList- Klasse: gute Leistung bei Einfüge-/Löschvorgängen. Mit Iterator erhalten Sie möglicherweise eine konstante Zeit für sie. Später in diesem Artikel schreiben wir ein Codebeispiel zum Vergleich von ArrayList und LinkedList+Iterator

• Iterator.remove() entfernt das letzte von diesem Iterator zurückgegebene Element.
• ListIterator.add(E element) fügt ein Element in die Liste ein

Java LinkedList-Beispiel: Funktionsweise von Iterator

Hier haben wir einen kleinen Java LinkedList- Beispielcode, in dem wir versuchen, über Iterator etwas hinzuzufügen und zu löschen.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
 
       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);
 
   }
}

Das Ergebnis der Ausführung dieses Programms:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

Weitere Java LinkedList- Operationen:

• addFirst() , addLast() fügen ein Element am Anfang/Ende einer Liste hinzu
• clear() entfernt alle Elemente aus der Liste
• enthält(Objekt o) gibt true zurück, wenn die Liste das o-Element enthält.
• indexOf(Object o) gibt den Index des ersten Vorkommens des o-Elements zurück oder -1, wenn es nicht in der Liste enthalten ist.
• set(int index, E element) ersetzt das Element an der Indexposition durch das Element
• size()Gibt die Anzahl der Elemente in der Liste zurück.
• toArray() gibt ein Array zurück, das alle Elemente der Liste vom ersten bis zum letzten Element enthält.

Da LinkedList in Java übrigens eine Warteschlange mit zwei Größen ist, verfügt sie über stapelspezifische Operationen:

• pop() , das ein Element vom Stapel entfernt (dargestellt durch die Liste)
• push(E e) , das ein Element auf den Stapel schiebt (dargestellt durch diese Liste)

So kehren Sie LinkedList um: Beispiel

Hier ist ein kleines Beispiel, eine beliebte und dennoch einfache Aufgabe für Anfänger. Wir haben eine LinkedList und sollten sie umkehren. Der einfachste Algorithmus besteht darin, die LinkedList in umgekehrter Reihenfolge durchzugehen und jedes Element in das neue einzufügen. Aber vielleicht finden Sie einen besseren Weg? Hier ist der Code des Java-Programms für umgekehrt verknüpfte Listen:

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

Das Ergebnis:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList vs. ArrayList: Wann sollte die erste verwendet werden?

Sowohl LinkedList als auch ArrayList sind Implementierungen der List- Schnittstelle. LinkedList implementiert es mit einer doppelt verknüpften Liste. ArrayList implementiert es mithilfe eines Arrays mit dynamischer Größenänderung. Wie Sie bereits wissen, enthält jeder Knoten von LinkedList Objekte und zwei Verweise auf die Nachbarn. Das bedeutet im Fall von Java LinkedList zusätzliche Speicherkosten für die Speicherung von Referenzen zwischen Elementen . ArrayList implementiert es mit einem Array mit dynamischer Größenänderung. Einige der LinkedList- und ArrayList- Operationen sehen gleich aus, funktionieren jedoch auf unterschiedliche Weise. In der ArrayListIn diesem Fall manipulieren Sie mit internen Arrays, in LinkedList – mit Referenzen. ArrayList ist die beliebteste List- Implementierung. Sie sollten ArrayList auf jeden Fall verwenden , wenn der Indexzugriff Priorität hat, da diese Vorgänge in konstanter Zeit ausgeführt werden. Auch das Hinzufügen am Ende der Liste erfolgt im Durchschnitt in konstanter Zeit. Darüber hinaus fallen bei ArrayList keine zusätzlichen Kosten für die Speicherung einer Reihe von Elementen an. Als Nachteile können Sie die Geschwindigkeit der Einfügungs- und Entfernungsvorgänge zählen, wenn diese nicht am Ende der Liste erfolgen. LinkedListist in mancher Hinsicht nützlicher für die Leistung von Einfüge- und Löschvorgängen: Wenn Sie Iteratoren verwenden, erfolgt dies in konstanter Zeit. Zugriffsoperationen nach Index werden durchgeführt, indem vom Anfang bis zum Ende (je nachdem, was näher liegt) bis zum gewünschten Element gesucht wird. Vergessen Sie jedoch nicht die zusätzlichen Kosten für die Speicherung von Referenzen zwischen Elementen. Hier also Standard- LinkedList- und ArrayList- Operationen mit algorithmischen Laufzeiten. N bezieht sich auf die Anzahl der Elemente, die bereits in der Liste enthalten sind. O(N) bedeutet, dass wir im schlimmsten Fall die gesamte Liste „durchgehen“ sollten, bis die benötigte Position gefunden ist, um beispielsweise das neue Element in die Liste einzufügen. O(1)bedeutet, dass der Vorgang unabhängig von der Anzahl der Elemente in konstanter Zeit erfolgt.

LinkedList-Zeitkomplexität

Zeitkomplexität von ArrayList

Wann LinkedList verwendet werden sollte: Beispiel

ArrayList ist definitiv die beliebteste List- Implementierung. Es kann jedoch vorkommen, dass die Vorgänge zum Hinzufügen/Entfernen zu oft erforderlich sind. In diesem Fall könnte LinkedList zusammen mit Iterator von Vorteil sein. Hier ist ein Beispiel. Wir haben eine lange Liste und sollten jedes Element aus dieser Liste löschen. Lassen Sie uns diese Aufgabe mit ArrayList und LinkedList + Iterator erledigen . Wir vergleichen die Zeit jedes Vorgangs und geben sie in der Konsole aus. Hier der Code:

import java.util.*;
import java.util.function.BiPredicate;
 
public class ListTest2 {
 
   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());
 
       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }
 
   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);
 
           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }
 
   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
 
   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

Ergebnis für ArrayList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

Ergebnis für LinkedList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

Wie Sie sehen können, ist LinkedList in diesem Fall viel effektiver. Lass uns ehrlich sein. In der realen Softwareentwicklung ist die Verwendung von LinkedList ein seltenes Ereignis. Dennoch sollte ein Fachmann über die Existenz dieser Datenstruktur und ihre Vorteile Bescheid wissen. Während LinkedList im realen Code ein seltener Gast ist, ist es bei Java Junior-Interviews sehr beliebt. Und doch hat Joshua Bloch Folgendes über LinkedList geschrieben :

AddOn: Einfach verknüpfte Liste Java

Unter den klassischen Sammlungen in Java gibt es keine einfach verknüpfte Liste . Eine einfach verknüpfte Liste ist eine Struktur, in der jeder Knoten ein Objekt und einen Verweis auf den nächsten Knoten enthält, jedoch nicht auf den vorherigen. Java LinkedList ist zweifach verknüpft, aber niemand hindert Sie daran, Ihre eigene Datenstruktur zu erstellen, z. B. eine einfach verknüpfte Liste. Hier sind einige Schritte, um diese Aufgaben zu lösen:

1. Erstellen Sie eine Node -Klasse mit zwei Attributen, data und next. Next ist ein Verweis auf den nächsten Knoten.
2. Erstellen Sie die FirstLast- Klasse mit zwei Attributen: head und tail.
3. Erstellen Sie eine add()- Methode, um der Liste einen neuen Knoten hinzuzufügen. Überprüfen Sie zunächst, ob die Liste leer ist ( head == null ). Wenn ja, beziehen sich Kopf und Schwanz auf den neuen Knoten. Wenn die Liste nicht leer ist, wird der neue Knoten am Ende hinzugefügt, sodass sich das nächste Attribut des Endes auf den hinzugefügten Knoten bezieht und der neue Knoten zum Ende der Liste wird.

Als Übung können Sie übrigens auch versuchen, Ihre eigene LinkedList zu erstellen. Viel Glück beim Lernen.