Datenstrukturen und Algorithmen in Java, Teil 4: Einfach verknüpfte Listen

Wie Arrays, die in Teil 3 dieser Lernserie vorgestellt wurden, sind verknüpfte Listen eine grundlegende Datenstrukturkategorie, auf der komplexere Datenstrukturen basieren können. Im Gegensatz zu einer Folge von Elementen ist eine verknüpfte Liste jedoch eine Folge von Knoten, wobei jeder Knoten mit dem vorherigen und nächsten Knoten in der Folge verknüpft ist. Denken Sie daran, dass ein Knoten ein Objekt ist, das aus einer selbstreferenziellen Klasse erstellt wurde, und dass eine selbstreferenzielle Klasse mindestens ein Feld hat, dessen Referenztyp der Klassenname ist. Knoten in einer verknüpften Liste werden über eine Knotenreferenz verknüpft. Hier ist ein Beispiel:

 class Employee { private int empno; private String name; private double salary; public Employee next; // Other members. }

In diesem Beispiel Employeehandelt es sich um eine selbstreferenzielle Klasse, da ihr nextFeld den Typ hat Employee. Dieses Feld ist ein Beispiel für ein Verknüpfungsfeld, da es einen Verweis auf ein anderes Objekt seiner Klasse speichern kann - in diesem Fall ein anderes EmployeeObjekt.

In diesem Tutorial werden die Vor- und Nachteile einfach verknüpfter Listen in der Java-Programmierung vorgestellt. Sie lernen Operationen zum Erstellen einer einfach verknüpften Liste, zum Einfügen von Knoten in eine einfach verknüpfte Liste, zum Löschen von Knoten aus einer einfach verknüpften Liste, zum Verketten einer einfach verknüpften Liste mit einer anderen einfach verknüpften Liste und zum Invertieren einer einzeln verknüpften Liste. Wir werden auch Algorithmen untersuchen, die am häufigsten zum Sortieren einfach verknüpfter Listen verwendet werden, und mit einem Beispiel schließen, das den Einfügungssortierungsalgorithmus demonstriert.

download Holen Sie sich den Code Laden Sie die drei Beispielanwendungen für diesen Artikel herunter. Erstellt von Jeff Friesen für JavaWorld.

Was ist eine einfach verknüpfte Liste?

Eine einfach verknüpfte Liste ist eine verknüpfte Liste von Knoten, wobei jeder Knoten ein einzelnes Verknüpfungsfeld hat. In dieser Datenstruktur enthält eine Referenzvariable eine Referenz auf den ersten (oder obersten) Knoten. Jeder Knoten (mit Ausnahme des letzten oder unteren Knotens) ist mit dem nächsten verknüpft. und das Verknüpfungsfeld des letzten Knotens enthält die Nullreferenz, um das Ende der Liste anzuzeigen. Obwohl die Referenzvariable häufig benannt wird top, können Sie einen beliebigen Namen auswählen.

Abbildung 1 zeigt eine einfach verknüpfte Liste mit drei Knoten.

Unten finden Sie einen Pseudocode für eine einfach verknüpfte Liste.

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next END DECLARE DECLARE Node top = NULL 

Nodeist eine selbstreferenzielle Klasse mit einem nameDatenfeld und einem nextVerknüpfungsfeld. topist eine Referenzvariable vom Typ Node, die eine Referenz auf das erste NodeObjekt in einer einfach verknüpften Liste enthält. Da die Liste noch nicht vorhanden ist, toplautet der Anfangswert NULL.

Erstellen einer einfach verknüpften Liste in Java

Sie erstellen eine einfach verknüpfte Liste, indem Sie ein einzelnes NodeObjekt anhängen . Der folgende Pseudocode erstellt ein NodeObjekt, weist seine Referenz zu top, initialisiert sein Datenfeld und weist NULLseinem Verknüpfungsfeld zu:

 top = NEW Node top.name = "A" top.next = NULL 

Abbildung 2 zeigt die erste einfach verknüpfte Liste, die aus diesem Pseudocode hervorgeht.

Diese Operation hat eine Zeitkomplexität von O (1) - Konstante. Denken Sie daran, dass O (1) "Big Oh of 1" ausgesprochen wird. (In Teil 1 wird daran erinnert, wie Zeit- und Raumkomplexitätsmessungen zur Bewertung von Datenstrukturen verwendet werden.)

Einfügen von Knoten in eine einfach verknüpfte Liste

Das Einfügen eines Knotens in eine einfach verknüpfte Liste ist etwas komplizierter als das Erstellen einer einfach verknüpften Liste, da drei Fälle zu berücksichtigen sind:

  • Einfügen vor dem ersten Knoten.
  • Einfügen nach dem letzten Knoten.
  • Einfügen zwischen zwei Knoten.

Einfügen vor dem ersten Knoten

Ein neuer Knoten wird vor dem ersten Knoten eingefügt, indem die Referenz des obersten Knotens dem Verknüpfungsfeld des neuen Knotens zugewiesen und der topVariablen die Referenz des neuen Knotens zugewiesen wird. Diese Operation wird durch den folgenden Pseudocode demonstriert:

 DECLARE Node temp temp = NEW Node temp.name = "B" temp.next = top top = temp 

Die resultierende Zwei- NodeListe wird in Abbildung 3 angezeigt.

Diese Operation hat eine zeitliche Komplexität von O (1).

Einfügen nach dem letzten Knoten

Ein neuer Knoten wird nach dem letzten Knoten eingefügt, indem dem Verknüpfungsfeld des neuen Knotens Null zugewiesen wird, die einfach verknüpfte Liste durchlaufen wird, um den letzten Knoten zu finden, und die Referenz des neuen Knotens dem Verknüpfungsfeld des letzten Knotens zugewiesen wird, wie der folgende Pseudocode zeigt:

 temp = NEW Node temp.name = "C" temp.next = NULL DECLARE Node temp2 temp2 = top // We assume top (and temp2) are not NULL // because of the previous pseudocode. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 now references the last node. temp2.next = temp 

Abbildung 4 zeigt die Liste nach dem Einfügen von NodeC nach NodeA.

Diese Operation hat eine zeitliche Komplexität von O ( n ) - linear. Seine zeitliche Komplexität könnte auf O (1) verbessert werden, indem ein Verweis auf den letzten Knoten beibehalten wird. In diesem Fall wäre es nicht erforderlich, nach dem letzten Knoten zu suchen.

Einfügen zwischen zwei Knoten

Das Einfügen eines Knotens zwischen zwei Knoten ist der komplexeste Fall. Sie fügen einen neuen Knoten zwischen zwei Knoten ein, indem Sie die Liste durchlaufen, um den Knoten zu finden, der vor dem neuen Knoten liegt, die Referenz im Verknüpfungsfeld des gefundenen Knotens dem Verknüpfungsfeld des neuen Knotens zuweisen und die Referenz des neuen Knotens der Verknüpfung des gefundenen Knotens zuweisen Feld. Der folgende Pseudocode demonstriert diese Aufgaben:

 temp = NEW Node temp.name = "D" temp2 = top // We assume that the newly created Node inserts after Node // A and that Node A exists. In the real world, there is no // guarantee that any Node exists, so we would need to check // for temp2 containing NULL in both the WHILE loop's header // and after the WHILE loop completes. WHILE temp2.name NE "A" temp2 = temp2.next END WHILE // temp2 now references Node A. temp.next = temp2.next temp2.next = temp 

Fig. 5 zeigt die Liste nach dem Einfügen von NodeD zwischen Nodes A und C.

Diese Operation hat eine zeitliche Komplexität von O ( n ).

Löschen von Knoten aus einer einfach verknüpften Liste

Das Löschen eines Knotens aus einer einfach verknüpften Liste ist auch etwas komplizierter als das Erstellen einer einfach verknüpften Liste. Es sind jedoch nur zwei Fälle zu berücksichtigen:

  • Löschen des ersten Knotens.
  • Löschen eines beliebigen Knotens außer dem ersten Knoten.

Deletion of the first node

Deleting the first node involves assigning the link in the first node's link field to the variable that references the first node, but only when there is a first node:

 IF top NE NULL THEN top = top.next; // Reference the second Node (or NULL when there's only one Node). END IF 

Figure 6 presents before and after views of a list where the first Node has been deleted. Node B disappears and Node A becomes the first Node.

This operation has a time complexity of O(1).

Deletion of any node but the first node

Deleting any node but the first node involves locating the node that precedes the node to be deleted and assigning the reference in the node-to-be-deleted's link field to the preceding node's link field. Consider the following pseudocode:

 IF top NE NULL THEN temp = top WHILE temp.name NE "A" temp = temp.next END WHILE // We assume that temp references Node A. temp.next = temp.next.next // Node D no longer exists. END IF 

Figure 7 presents before and after views of a list where an intermediate Node is deleted. Node D disappears.

This operation has a time complexity of O(n).

Example #1: Create, insert, and delete in a singly linked list

I've created a Java application named SLLDemo that demonstrates how to create, insert, and delete nodes in a singly linked list. Listing 1 presents this application's source code.

Listing 1. Java application demo for singly linked lists (SSLDemo.java, version 1)

 public final class SLLDemo { private static class Node { String name; Node next; } public static void main(String[] args) { Node top = null; // 1. The singly linked list does not exist. top = new Node(); top.name = "A"; top.next = null; dump("Case 1", top); // 2. The singly linked list exists and the node must be inserted // before the first node. Node temp; temp = new Node(); temp.name = "B"; temp.next = top; top = temp; dump("Case 2", top); // 3. The singly linked list exists and the node must be inserted // after the last node. temp = new Node(); temp.name = "C"; temp.next = null; Node temp2; temp2 = top; while (temp2.next != null) temp2 = temp2.next; temp2.next = temp; dump("Case 3", top); // 4. The singly linked list exists and the node must be inserted // between two nodes. temp = new Node(); temp.name = "D"; temp2 = top; while (temp2.name.equals("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; dump("Case 4", top); // 5. Delete the first node. top = top.next; dump("After first node deletion", top); // 5.1 Restore node B. temp = new Node(); temp.name = "B"; temp.next = top; top = temp; // 6. Delete any node but the first node. temp = top; while (temp.name.equals("A") == false) temp = temp.next; temp.next = temp.next.next; dump("After D node deletion", top); } private static void dump(String msg, Node topNode) { System.out.print(msg + " "); while (topNode != null) { System.out.print(topNode.name + " "); topNode = topNode.next; } System.out.println(); } } 

Compile Listing 1 as follows:

 javac SLLDemo.java 

Run the resulting application as follows:

 java SLLDemo 

You should observe the following output:

 Case 1 A Case 2 B A Case 3 B A C Case 4 B A D C After first node deletion A D C After D node deletion B A C 

Concatenating singly linked lists

You might occasionally need to concatenate a singly linked list to another singly linked list. For example, suppose you have a list of words that start with letters A through M and another list of words starting with letters N through Z, and you want to combine these lists into a single list. The following pseudocode describes an algorithm for concatenating one singly linked list to another:

 DECLARE Node top1 = NULL DECLARE Node top2 = NULL // Assume code that creates top1-referenced singly linked list. // Assume code that creates top2-referenced singly linked list. // Concatenate top2-referenced list to top1-referenced list. IF top1 EQ NULL top1 = top2 END END IF // Locate final Node in top1-referenced list. DECLARE Node temp = top1 WHILE temp.next NE NULL temp = temp.next END WHILE // Concatenate top2 to top1. temp.next = top2 END 

In the trivial case, there is no top1-referenced list, and so top1 is assigned top2's value, which would be NULL if there was no top2-referenced list.

This operation has a time complexity of O(1) in the trivial case and a time complexity of O(n) otherwise. However, if you maintain a reference to the last node, there's no need to search the list for this node; the time complexity changes to O(1).

Inverting a singly linked list

Another useful operation on a singly linked list is inversion, which reverses the list's links to let you traverse its nodes in the opposite direction. The following pseudocode reverses the top1-referenced list's links:

 DECLARE Node p = top1 // Top of original singly linked list. DECLARE Node q = NULL // Top of reversed singly linked list. DECLARE Node r // Temporary Node reference variable. WHILE p NE NULL // For each Node in original singly linked list ... r = q // Save future successor Node's reference. q = p // Reference future predecessor Node. p = p.next // Reference next Node in original singly linked list. q.next = r // Link future predecessor Node to future successor Node. END WHILE top1 = q // Make top1 reference first Node in reversed singly linked list. END 

This operation has a time complexity of O(n).

Example #2: Concatenating and inverting a singly linked list

Ich habe eine zweite Version der SLLDemoJava-Anwendung erstellt, die Verkettung und Inversion demonstriert. Listing 2 zeigt den Quellcode dieser Anwendung.