Datastrukturer och algoritmer i Java, del 4: Enkel länkade listor

Liksom arrays, som introducerades i del 3 i denna handledningsserie, är länkade listor en grundläggande datastrukturkategori som mer komplexa datastrukturer kan baseras på. Till skillnad från en sekvens av element är en länkad lista dock en sekvens av noder, där varje nod är länkad till föregående och nästa nod i sekvensen. Kom ihåg att en nod är ett objekt som skapats från en självreferensklass och att en självreferensklass har minst ett fält vars referens typ är klassnamnet. Noder i en länkad lista är länkade via en nodreferens. Här är ett exempel:

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

I det här exemplet Employeeär en självreferensklass eftersom dess nextfält har typ Employee. Det här fältet är ett exempel på ett länkfält eftersom det kan lagra en referens till ett annat objekt i sin klass - i det här fallet ett annat Employeeobjekt.

Denna handledning introducerar ins och outs av enskilt länkade listor i Java-programmering. Du lär dig hur du skapar en enstaka länkad lista, infogar noder i en enstaka länkad lista, tar bort noder från en enstaka länkad lista, sammanfogar en enstaka länkad lista till en annan enstaka länkad lista och inverterar en enstaka länkad lista. Vi utforskar också algoritmer som oftast används för att sortera enstaka länkade listor och avslutar med ett exempel som visar Insertion Sort-algoritmen.

ladda ner Hämta koden Ladda ner de tre exempelapplikationerna för den här artikeln. Skapad av Jeff Friesen för JavaWorld.

Vad är en enstaka länkad lista?

En enstaka länkad lista är en länkad lista med noder där varje nod har ett enda länkfält. I denna datastruktur innehåller en referensvariabel en referens till den första (eller övre) noden; varje nod (förutom den sista eller nedre noden) länkar till nästa; och den sista nodens länkfält innehåller nollreferensen för att beteckna listans slut. Även om referensvariabeln ofta heter top, kan du välja vilket namn du vill.

Figur 1 presenterar en enstaka länkad lista med tre noder.

Nedan finns en pseudokod för en enstaka länkad lista.

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

Nodeär en självreferensklass med ett namedatafält och ett nextlänkfält. topär en referensvariabel av typen Nodesom innehåller en referens till det första Nodeobjektet i en enstaka länkad lista. Eftersom listan ännu inte finns är dess topursprungliga värde NULL.

Skapa en separat länkad lista i Java

Du skapar en enstaka länkad lista genom att bifoga ett enda Nodeobjekt. Följande pseudokod skapar ett Nodeobjekt, tilldelar sin referens till top, initialiserar sitt datafält och tilldelar NULLsitt länkfält:

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

Figur 2 visar den första enskilt länkade listan som framgår av denna pseudokod.

Denna operation har en tidskomplexitet av O (1) - konstant. Kom ihåg att O (1) uttalas "Big Oh of 1." (Se del 1 för en påminnelse om hur tids- och rymdkomplexitetsmätningar används för att utvärdera datastrukturer.)

Infoga noder i en enstaka länkad lista

Att infoga en nod i en enstaka länkad lista är något mer komplicerad än att skapa en enstaka länkad lista eftersom det finns tre fall att tänka på:

  • Insättning före den första noden.
  • Insättning efter den sista noden.
  • Insättning mellan två noder.

Insättning före den första noden

En ny nod infogas före den första noden genom att tilldela toppnodens referens till den nya nodens länkfält och tilldela den nya nodens referens till topvariabeln. Denna operation demonstreras av följande pseudokod:

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

Den resulterande tvålistan Nodevisas i figur 3.

Denna operation har en tidskomplexitet av O (1).

Insättning efter den sista noden

En ny nod infogas efter den sista noden genom att tilldela null till den nya nodens länkfält, korsa den enskilt länkade listan för att hitta den sista noden och tilldela den nya nodens referens till den sista nodens länkfält, som följande pseudokod visar:

 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 

Figur 4 visar listan efter införandet av NodeC efter NodeA.

Denna operation har en tidskomplexitet av O ( n ) - linjär. Dess tidskomplexitet kan förbättras till O (1) genom att bibehålla en referens till den sista noden. I så fall skulle det inte vara nödvändigt att söka efter den sista noden.

Insättning mellan två noder

Att infoga en nod mellan två noder är det mest komplexa fallet. Du infogar en ny nod mellan två noder genom att korsa listan för att hitta noden som kommer före den nya noden, tilldela referensen i den hittade nodens länkfält till den nya nodens länkfält och tilldela den nya nodens referens till den hittade nodens länk. fält. Följande pseudokod visar dessa uppgifter:

 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 

Figur 5 presenterar listan efter införandet av NodeD mellan Nodes A och C.

Denna operation har en tidskomplexitet av O ( n ).

Ta bort noder från en enstaka länkad lista

Att radera en nod från en enskilt länkad lista är också något mer komplicerad än att skapa en enskilt länkad lista. Det finns dock bara två fall att överväga:

  • Radering av den första noden.
  • Radering av vilken nod som helst utom den första noden.

Radering av den första noden

Att radera den första noden innebär att länken i den första nodens länkfält tilldelas variabeln som refererar till den första noden, men bara när det finns en första nod:

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

Figur 6 visar före och efter visningar av en lista där den första Nodehar raderats. Noden Bförsvinner och NodeA blir den första Node.

Denna operation har en tidskomplexitet av O (1).

Radering av vilken nod som helst utom den första noden

Att radera vilken nod som helst men den första noden innebär att lokalisera noden som föregår noden som ska raderas och tilldela referensen i nodfältet som ska raderas till föregående nodens länkfält. Tänk på följande pseudokod:

 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 

Figur 7 visar före och efter vyer av en lista där en mellanprodukt Noderaderas. NodeD försvinner.

Denna operation har en tidskomplexitet av O ( n ).

Exempel 1: Skapa, infoga och ta bort i en enstaka länkad lista

Jag har skapat ett Java-program med namnet SLLDemosom visar hur man skapar, infogar och tar bort noder i en enskilt länkad lista. Listning 1 visar applikationens källkod.

Listing 1. Java-applikationsdemo för enstaka länkade listor (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(); } } 

Sammanställa lista 1 enligt följande:

 javac SLLDemo.java 

Kör den resulterande applikationen enligt följande:

 java SLLDemo 

Följ följande utdata:

 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 

Sammankoppling av enskilt länkade listor

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

Jag har skapat en andra version av SLLDemoJava-applikationen som visar sammankoppling och inversion. Listning 2 visar applikationens källkod.