Datastructuren en algoritmen in Java, deel 4: afzonderlijk gekoppelde lijsten

Net als arrays, die werden geïntroduceerd in deel 3 van deze tutorialserie, zijn gekoppelde lijsten een fundamentele datastructuurcategorie waarop complexere datastructuren kunnen worden gebaseerd. In tegenstelling tot een reeks elementen is een gekoppelde lijst echter een reeks knooppunten, waarbij elk knooppunt is gekoppeld aan het vorige en volgende knooppunt in de reeks. Bedenk dat een knooppunt een object is dat is gemaakt op basis van een naar zichzelf refererende klasse, en dat een naar zichzelf refererende klasse ten minste één veld heeft waarvan het referentietype de klassennaam is. Knooppunten in een gekoppelde lijst zijn gekoppeld via een knooppuntreferentie. Hier is een voorbeeld:

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

In dit voorbeeld Employeeis dit een naar zichzelf verwijzende klasse omdat het nextveld type heeft Employee. Dit veld is een voorbeeld van een linkveld omdat het een verwijzing naar een ander object van zijn klasse kan opslaan - in dit geval een ander Employeeobject.

Deze tutorial introduceert de ins en outs van enkelvoudig gekoppelde lijsten in Java-programmering. U leert bewerkingen voor het maken van een enkelvoudig gelinkte lijst, het invoegen van knooppunten in een enkelvoudig gelinkte lijst, het verwijderen van nodes uit een enkelvoudig gelinkte lijst, het aaneenschakelen van een enkelvoudig gelinkte lijst aan een ander enkelvoudig gelinkte lijst, en het omkeren van een enkelvoudig gelinkte lijst. We zullen ook de algoritmen onderzoeken die het meest worden gebruikt voor het sorteren van enkelvoudig gelinkte lijsten, en eindigen met een voorbeeld dat het Insertion Sort-algoritme demonstreert.

download Download de code Download de drie voorbeeldtoepassingen voor dit artikel. Gemaakt door Jeff Friesen voor JavaWorld.

Wat is een enkelvoudig gelinkte lijst?

Een enkelvoudig gekoppelde lijst is een gekoppelde lijst met knooppunten waarbij elk knooppunt een enkel linkveld heeft. In deze datastructuur bevat een referentievariabele een verwijzing naar het eerste (of bovenste) knooppunt; elk knooppunt (behalve het laatste of onderste knooppunt) linkt naar het volgende; en het linkveld van het laatste knooppunt bevat de nulreferentie om het einde van de lijst aan te duiden. Hoewel de referentievariabele gewoonlijk wordt genoemd top, kunt u elke gewenste naam kiezen.

Figuur 1 toont een enkelvoudig gekoppelde lijst met drie knooppunten.

Hieronder staat een pseudocode voor een enkelvoudig gelinkte lijst.

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

Nodeis een zelfreferentiële klasse met een namedataveld en een nextlinkveld. topis een referentievariabele van het type Nodedat een verwijzing bevat naar het eerste Nodeobject in een enkelvoudig gekoppelde lijst. Omdat de lijst nog niet bestaat, topis de oorspronkelijke waarde van NULL.

Een enkelvoudig gelinkte lijst maken in Java

U maakt een enkelvoudig gekoppelde lijst door een enkel Nodeobject toe te voegen . De volgende pseudocode maakt een Nodeobject aan, wijst zijn verwijzing toe aan top, initialiseert zijn gegevensveld en wijst toe NULLaan zijn linkveld:

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

Figuur 2 toont de eerste enkelvoudig gelinkte lijst die uit deze pseudocode naar voren komt.

Deze bewerking heeft een tijdcomplexiteit van O (1) - constante. Bedenk dat O (1) wordt uitgesproken als "Big Oh of 1." (Zie deel 1 voor een herinnering aan hoe tijd- en ruimtecomplexiteitsmetingen worden gebruikt om gegevensstructuren te evalueren.)

Knooppunten invoegen in een enkelvoudig gekoppelde lijst

Het invoegen van een knooppunt in een enkelvoudig gelinkte lijst is iets gecompliceerder dan het maken van een enkelvoudig gelinkte lijst, omdat er drie gevallen zijn om te overwegen:

  • Invoegen vóór het eerste knooppunt.
  • Invoegen na het laatste knooppunt.
  • Invoeging tussen twee knooppunten.

Invoegen vóór het eerste knooppunt

Een nieuw knooppunt wordt voor het eerste knooppunt ingevoegd door de referentie van het bovenste knooppunt toe te wijzen aan het linkveld van het nieuwe knooppunt en de referentie van het nieuwe knooppunt aan de topvariabele toe te wijzen . Deze operatie wordt gedemonstreerd door de volgende pseudocode:

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

De resulterende twee- Nodelijst verschijnt in Figuur 3.

Deze bewerking heeft een tijdcomplexiteit van O (1).

Invoegen na het laatste knooppunt

Een nieuw knooppunt wordt ingevoegd na het laatste knooppunt door null toe te wijzen aan het linkveld van het nieuwe knooppunt, de enkelvoudig gekoppelde lijst te doorlopen om het laatste knooppunt te vinden, en de referentie van het nieuwe knooppunt toe te wijzen aan het linkveld van het laatste knooppunt, zoals de volgende pseudocode laat zien:

 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 

Figuur 4 toont de lijst na het invoegen van NodeC na NodeA.

Deze bewerking heeft een tijdcomplexiteit van O ( n ) - lineair. De tijdcomplexiteit kan worden verbeterd tot O (1) door een verwijzing naar het laatste knooppunt te behouden. In dat geval zou het niet nodig zijn om naar het laatste knooppunt te zoeken.

Invoeging tussen twee knooppunten

Inserting a node between two nodes is the most complex case. You insert a new node between two nodes by traversing the list to find the node that comes before the new node, assigning the reference in the found node's link field to the new node's link field, and assigning the new node's reference to the found node's link field. The following pseudocode demonstrates these tasks:

 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 

Figure 5 presents the list following the insertion of Node D between Nodes A and C.

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

Deleting nodes from a singly linked list

Deleting a node from a singly linked list is also somewhat more complicated than creating a singly linked list. However, there are only two cases to consider:

  • Deletion of the first node.
  • Deletion of any node but the first node.

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

Ik heb een tweede versie van de SLLDemoJava-applicatie gemaakt die aaneenschakeling en inversie laat zien. Listing 2 presenteert de broncode van deze applicatie.