Datenstrukturen und Algorithmen in Java, Teil 5: Doppelt verknüpfte Listen

Einfach verknüpfte Listen haben viele Verwendungszwecke, weisen jedoch auch einige Einschränkungen auf. Zum einen beschränken einfach verknüpfte Listen das Durchlaufen von Knoten auf eine einzige Richtung: Sie können eine einfach verknüpfte Liste nur dann rückwärts durchlaufen, wenn Sie zuerst die Knotenverknüpfungen umkehren, was einige Zeit in Anspruch nimmt. Wenn Sie eine umgekehrte Durchquerung durchführen und die Knotendurchquerung in der ursprünglichen Richtung wiederherstellen müssen, müssen Sie die Inversion wiederholen, was mehr Zeit in Anspruch nimmt. Einfach verknüpfte Listen beschränken auch das Löschen von Knoten. In dieser Art von Liste können Sie keinen beliebigen Knoten ohne Zugriff auf den Vorgänger des Knotens löschen.

Glücklicherweise bietet Java verschiedene Arten von Listen an, mit denen Sie gespeicherte Daten in Ihren Java-Programmen suchen und sortieren können. Dieses letzte Tutorial in der Reihe Datenstrukturen und Algorithmen führt in das Suchen und Sortieren mit doppelt verknüpften Listen und zirkular verknüpften Listen ein. Wie Sie sehen werden, bauen diese beiden Datenstrukturkategorien auf einfach verknüpften Listen auf, um ein breiteres Spektrum an Such- und Sortierverhalten in Ihren Java-Programmen zu bieten.

Doppelt verknüpfte Listen

Eine doppelt verknüpfte Liste ist eine verknüpfte Liste von Knoten, wobei jeder Knoten ein Paar von Verknüpfungsfeldern hat. Mit einem Verknüpfungsfeld können Sie die Liste in Vorwärtsrichtung durchlaufen, während Sie mit dem anderen Knoten die Liste in Rückwärtsrichtung durchlaufen können. Für die Vorwärtsrichtung enthält eine Referenzvariable eine Referenz auf den ersten Knoten. Jeder Knoten ist über das Linkfeld "next" mit dem nächsten Knoten verbunden, mit Ausnahme des letzten Knotens, dessen Linkfeld "next" die Nullreferenz enthält, um das Ende der Liste (in Vorwärtsrichtung) anzuzeigen. Die Rückwärtsrichtung funktioniert ähnlich. Eine Referenzvariable enthält eine Referenz auf den letzten Knoten der Vorwärtsrichtung, den Sie als ersten Knoten interpretieren. Jeder Knoten ist über das Feld "Vorheriger" mit dem vorherigen Knoten verbunden. Der "vorherige" des ersten KnotensDas Linkfeld enthält null, um das Ende der Liste anzuzeigen.

Stellen Sie sich eine doppelt verknüpfte Liste als ein Paar einfach verknüpfter Listen vor, die jeweils dieselben Knoten miteinander verbinden. Das Diagramm in Abbildung 1 zeigt einfach referenzierte topForwardund topBackwardreferenzierte einfach verknüpfte Listen.

CRUD-Operationen in doppelt verknüpften Listen

Das Erstellen, Einfügen und Löschen von Knoten sind allgemeine Vorgänge in einer doppelt verknüpften Liste. Sie ähneln den Operationen, die Sie für einfach verknüpfte Listen gelernt haben. (Denken Sie daran, dass eine doppelt verknüpfte Liste nur ein Paar einfach verknüpfter Listen ist, die dieselben Knoten miteinander verbinden.) Der folgende Pseudocode demonstriert das Erstellen und Einfügen von Knoten in die in Abbildung 1 gezeigte doppelt verknüpfte Liste. Der Pseudocode demonstriert auch den Knoten Streichung:

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next DECLARE Node prev END DECLARE DECLARE Node topForward DECLARE Node temp DECLARE Node topBackward topForward = NEW Node topForward.name = "A" temp = NEW Node temp.name = "B" topBackward = NEW Node topBackward.name = "C" // Create forward singly-linked list topForward.next = temp temp.next = topBackward topBackward.next = NULL // Create backward singly-linked list topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Delete Node B. temp.prev.next = temp.next; // Bypass Node B in the forward singly-linked list. temp.next.prev = temp.prev; // Bypass Node B in the backward singly-linked list. END 

Beispielanwendung: CRUD in einer doppelt verknüpften Liste

Die Java-Beispielanwendung DLLDemozeigt, wie Knoten in einer doppelt verknüpften Liste erstellt, eingefügt und gelöscht werden. Der Quellcode der Anwendung wird in Listing 1 angezeigt.

Listing 1. Eine Java-Anwendung, die CRUD in einer doppelt verknüpften Liste demonstriert

 public final class DLLDemo { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Reference node B. temp = topForward.next; // Delete node B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Dump forward singly-linked list. System.out.print("Forward singly-linked list (after deletion): "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list (after deletion): "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } } 

Kompilieren Sie Listing 4 wie folgt:

 javac DLLDemo.java 

Führen Sie die resultierende Anwendung wie folgt aus:

 java DLLDemo 

Sie sollten die folgende Ausgabe beachten:

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list (after deletion): AC Backward singly-linked list (after deletion): CA 

Mischen in doppelt verknüpften Listen

Das Java Collections Framework enthält eine CollectionsKlasse von Dienstprogrammmethoden, die Teil des java.utilPakets sind. Diese Klasse enthält eine void shuffle(List list)Methode, die " die angegebene Liste unter Verwendung einer Standardquelle für Zufälligkeit zufällig permutiert ". Sie können diese Methode beispielsweise verwenden, um ein Kartenspiel zu mischen, das als doppelt verknüpfte Liste ausgedrückt wird (die java.util.LinkedListKlasse ist ein Beispiel). Im folgenden Pseudocode können Sie sehen, wie der Shuffle-Algorithmus eine doppelt verknüpfte Liste mischen kann:

 DECLARE RANDOM rnd = new RANDOM DECLARE INTEGER i FOR i = 3 DOWNTO 2 swap(topForward, i - 1, rnd.nextInt(i)) END FOR FUNCTION swap(Node top, int i, int j) DECLARE Node nodei, nodej DECLARE INTEGER k // Locate ith node. Node nodei = top FOR k = 0 TO i - 1 nodei = nodei.next END FOR // Locate jth node. Node nodej = top FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Perform the swap. DECLARE STRING namei = nodei.name DECLARE STRING namej = nodej.name nodej.name = namei nodei.name = namej END FUNCTION END 

Der Shuffle-Algorithmus erhält eine Zufallsquelle und durchläuft dann die Liste vom letzten bis zum zweiten Knoten rückwärts. Es wird wiederholt ein zufällig ausgewählter Knoten (der eigentlich nur das Namensfeld ist) in die "aktuelle Position" getauscht. Knoten werden zufällig aus dem Teil der Liste ausgewählt, der vom ersten Knoten bis zur aktuellen Position einschließlich läuft. Beachten Sie, dass dieser Algorithmus grob aus void shuffle(List list)dem Quellcode extrahiert ist.

Der Pseudocode des Shuffle-Algorithmus ist faul, da er sich nur auf die vorwärts verlaufende, einfach verknüpfte Liste konzentriert. Es ist eine vernünftige Designentscheidung, aber wir zahlen einen Preis dafür in zeitlicher Komplexität. Die zeitliche Komplexität beträgt O ( n 2). Erstens haben wir die O ( n ) -Schleife, die aufruft swap(). Zweitens swap()haben wir innerhalb die zwei aufeinanderfolgenden O ( n ) -Schleifen. Erinnern Sie sich an die folgende Regel aus Teil 1:

 If f1(n) = O(g(n)) and f2(n) = O(h(n)) then (a) f1(n)+f2(n) = max(O(g(n)), O(h(n))) (b) f1(n)*f2(n) = O(g(n)*h(n)). 

Teil (a) befasst sich mit sequentiellen Algorithmen. Hier haben wir zwei O ( n ) Schleifen. Gemäß der Regel wäre die resultierende Zeitkomplexität O ( n ). Teil (b) befasst sich mit verschachtelten Algorithmen. In diesem Fall haben wir O ( n ) multipliziert mit O ( n ), was zu O ( n 2) führt.

Beachten Sie, dass die Raumkomplexität von Shuffle O (1) ist, was sich aus den deklarierten Hilfsvariablen ergibt.

Beispielanwendung: Mischen in einer doppelt verknüpften Liste

Die ShuffleAnwendung in Listing 2 ist eine Demonstration des Shuffle-Algorithmus.

Listing 2. Der Shuffle-Algorithmus in Java

 import java.util.Random; public final class Shuffle { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Shuffle list. Random rnd = new Random(); for (int i = 3; i > 1; i--) swap(topForward, i - 1, rnd.nextInt(i)); // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } public static void swap(Node top, int i, int j) { // Locate ith node. Node nodei = top; for (int k = 0; k < i; k++) nodei = nodei.next; // Locate jth node. Node nodej = top; for (int k = 0; k < j; k++) nodej = nodej.next; String namei = nodei.name; String namej = nodej.name; nodej.name = namei; nodei.name = namej; } } 

Kompilieren Sie Listing 5 wie folgt:

 javac Shuffle.java 

Führen Sie die resultierende Anwendung wie folgt aus:

 java Shuffle 

Sie sollten die folgende Ausgabe von einem Lauf beobachten:

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list: BAC Backward singly-linked list: CAB 

Zirkuläre verknüpfte Listen

Das Verknüpfungsfeld im letzten Knoten einer einfach verknüpften Liste enthält eine Nullverknüpfung. Dies gilt auch für eine doppelt verknüpfte Liste, die die Verknüpfungsfelder in den letzten Knoten der einfach verknüpften Vorwärts- und Rückwärtslisten enthält. Angenommen, die letzten Knoten enthielten Links zu den ersten Knoten. In dieser Situation erhalten Sie eine zirkular verknüpfte Liste , die in Abbildung 2 dargestellt ist.

Circular-linked lists, also known as circular buffers or circular queues, have many uses. For example, they're used by operating system interrupt handlers to buffer keystrokes. Multimedia applications use circular-linked lists to buffer data (for example, buffering data being written to a sound card). This technique is also used by the LZ77 family of lossless data compression algorithms.

Linked lists versus arrays

Throughout this series on data structures and algorithms, we've considered the strengths and weaknesses of different data structures. Since we've focused on arrays and linked lists, you might have questions about these types specifically. What advantages and disadvantages do linked lists and arrays offer? When do you use a linked list and when do you use an array? Can data structures from both categories be integrated into a useful hybrid data structure? I'll try to answer these questions below.

Linked lists offer the following advantages over arrays:

  • They don't require extra memory to support expansion. In contrast, arrays require extra memory when expansion is necessary. (Once all elements contain data items, no new data items can be appended to an array.)
  • Sie bieten ein schnelleres Einfügen / Löschen von Knoten als entsprechende Array-basierte Operationen. Nur Links müssen aktualisiert werden, nachdem die Einfüge- / Löschposition identifiziert wurde. Aus Array-Sicht erfordert das Einfügen von Datenelementen das Verschieben aller anderen Datenelemente, um ein leeres Element zu erstellen. Ebenso erfordert das Löschen eines vorhandenen Datenelements das Verschieben aller anderen Datenelemente, um ein leeres Element zu entfernen. Alle Bewegungen von Datenelementen brauchen Zeit.

Im Gegensatz dazu bieten Arrays gegenüber verknüpften Listen die folgenden Vorteile:

  • Array-Elemente belegen weniger Speicher als Knoten, da für Elemente keine Verknüpfungsfelder erforderlich sind.
  • Arrays bieten über ganzzahlige Indizes einen schnelleren Zugriff auf Datenelemente.