Strukture podataka i algoritmi u Javi, 4. dio: Popisi s jednom vezom

Poput nizova koji su uvedeni u 3. dijelu ove serije tutorijala, povezani su popisi temeljna kategorija strukture podataka na kojoj se mogu temeljiti složenije strukture podataka. Međutim, za razliku od niza elemenata, povezani je popis slijed čvorova, gdje je svaki čvor povezan s prethodnim i sljedećim čvorom u nizu. Sjetimo se da je čvor objekt stvoren iz autoreferencijalne klase, a autoreferencijalna klasa ima barem jedno polje čiji je referentni tip naziv klase. Čvorovi na povezanom popisu povezani su putem reference čvora. Evo primjera:

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

U ovom primjeru Employeeje autoreferencijalna klasa jer njezino nextpolje ima tip Employee. Ovo je polje primjer poveznog polja jer može pohraniti referencu na drugi objekt svoje klase - u ovom slučaju na drugi Employeeobjekt.

Ovaj tutorial uvodi detalje pojedinačno povezanih popisa u Java programiranju. Naučit ćete operacije za stvaranje pojedinačno povezanog popisa, umetanje čvorova u pojedinačno povezani popis, brisanje čvorova s ​​pojedinačno povezanog popisa, spajanje pojedinačno povezanog popisa u drugi pojedinačno povezani popis i obrtanje pojedinačno povezanog popisa. Također ćemo istražiti algoritme koji se najčešće koriste za sortiranje pojedinačno povezanih popisa i zaključiti primjerom koji demonstrira algoritam sortiranja umetanja.

preuzimanje Preuzmite kod Preuzmite tri primjera aplikacija za ovaj članak. Stvorio Jeff Friesen za JavaWorld.

Što je pojedinačno povezani popis?

Pojedinačno povezani popis je povezani popis čvorova gdje svaki čvor ima jedno polje veze. U ovoj strukturi podataka referentna varijabla sadrži referencu na prvi (ili gornji) čvor; svaki čvor (osim zadnjeg ili donjeg čvora) povezuje se sa sljedećim; a polje veze zadnjeg čvora sadrži nulu referencu koja označava kraj popisa. Iako se referentna varijabla obično naziva top, možete odabrati bilo koje ime koje želite.

Na slici 1. prikazan je pojedinačno povezani popis s tri čvora.

Ispod je pseudokod za pojedinačno povezani popis.

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

Nodeje autoreferencijalna klasa s namepodatkovnim poljem i nextpoljem veze. topje referentna varijabla tipa Nodekoja sadrži referencu na prvi Nodeobjekt na pojedinačno povezanom popisu. Budući da popis još ne postoji, toppočetna vrijednost je NULL.

Stvaranje pojedinačno povezanog popisa na Javi

Popis s jednim povezivanjem stvarate dodavanjem jednog Nodeobjekta. Sljedeći pseudokod stvara Nodeobjekt, dodjeljuje mu referencu top, inicijalizira njegovo polje podataka i dodjeljuje NULLnjegovom polju veze:

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

Slika 2 prikazuje početni pojedinačno povezani popis koji proizlazi iz ovog pseudokoda.

Ova operacija ima vremensku složenost O (1) - konstantna. Podsjetimo da se O (1) izgovara "Veliki Oh od 1". (Pogledajte 1. dio za podsjetnik na to kako se mjerenja složenosti vremena i prostora koriste za procjenu struktura podataka.)

Umetanje čvorova u pojedinačno povezani popis

Umetanje čvora u pojedinačno povezani popis nešto je složenije od stvaranja pojedinačno povezanog popisa, jer treba razmotriti tri slučaja:

  • Umetanje prije prvog čvora.
  • Umetanje nakon posljednjeg čvora.
  • Umetanje između dva čvora.

Umetanje prije prvog čvora

Novi čvor se umetne prije prvog čvora dodjeljivanjem reference na gornji čvor polju veze novog čvora i dodjeljivanjem reference novog čvora topvarijabli. Ova operacija prikazana je sljedećim pseudokodom:

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

Dobiveni Nodepopis s dva pojavljuje se na slici 3.

Ova operacija ima vremensku složenost O (1).

Umetanje nakon posljednjeg čvora

Novi čvor se umeće nakon zadnjeg čvora dodjeljivanjem nule polju veze novog čvora, prelaskom pojedinačno povezanog popisa kako bi se pronašao zadnji čvor i dodjeljivanjem reference novog čvora zadnjem polju čvora, kao što pokazuje sljedeći pseudokod:

 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 

Slika 4 otkriva popis nakon umetanja NodeC nakon NodeA.

Ova operacija ima vremensku složenost O ( n ) - linearna. Njegova vremenska složenost mogla bi se poboljšati na O (1) zadržavanjem reference na posljednji čvor. U tom slučaju ne bi bilo potrebno tražiti posljednji čvor.

Umetanje između dva čvora

Umetanje čvora između dva čvora najsloženiji je slučaj. Novi čvor umetnete između dva čvora prelaskom po popisu kako biste pronašli čvor koji dolazi prije novog čvora, dodijelivši referencu u polju veze pronađenog čvora polju novog čvora i dodijelivši referencu novog čvora vezi pronađenog čvora. polje. Sljedeći pseudokod prikazuje ove zadatke:

 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 

Slika 5 predstavlja popis nakon umetanja NodeD između Nodes A i C.

Ova operacija ima vremensku složenost O ( n ).

Brisanje čvorova s ​​pojedinačno povezanog popisa

Brisanje čvora s pojedinačno povezanog popisa također je nešto složenije od stvaranja pojedinačno povezanog popisa. Međutim, postoje samo dva slučaja koja treba razmotriti:

  • Brisanje prvog čvora.
  • Brisanje bilo kojeg čvora osim prvog čvora.

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

Stvorio sam drugu verziju SLLDemoJava aplikacije koja pokazuje spajanje i inverziju. Popis 2 predstavlja izvorni kod ove aplikacije.