Strukture podataka i algoritmi u Javi, 5. dio: Dvostruko povezani popisi

Iako se pojedinačno povezani popisi mnogo koriste, oni također sadrže određena ograničenja. Prvo, pojedinačno povezani popisi ograničavaju okretanje čvorova u jednom smjeru: ne možete prelaziti pojedinačno povezani popis unatrag ako prethodno ne preokrenete njegove veze čvorova, što zahtijeva vrijeme. Ako napravite obrnuto okretanje i trebate vratiti prelazak čvora u izvorni smjer, morat ćete ponoviti inverziju, što traje više vremena. Popisi s jednim povezivanjem također ograničavaju brisanje čvorova. U ovoj vrsti popisa ne možete izbrisati proizvoljni čvor bez pristupa prethodniku čvora.

Srećom, Java nudi nekoliko vrsta popisa pomoću kojih možete pretraživati ​​i sortirati pohranjene podatke u svojim Java programima. Ovaj posljednji vodič u seriji Strukture podataka i algoritmi uvodi pretraživanje i sortiranje s dvostruko povezanim popisima i kružno povezanim popisima. Kao što ćete vidjeti, ove dvije kategorije strukture podataka grade se na pojedinačno povezanim popisima kako bi ponudile širi spektar ponašanja pretraživanja i sortiranja u vašim Java programima.

Dvostruko povezani popisi

Dvostruko povezana lista je vezana lista čvorova gdje svaki čvor ima par linkova polja. Jedno polje veze omogućuje vam prelazak popisa u smjeru prema naprijed, dok drugi čvor omogućuje prelazak popisa u smjeru unatrag. Za smjer prema naprijed, referentna varijabla sadrži referencu na prvi čvor. Svaki čvor povezuje se sa sljedećim čvorom putem polja "sljedeći", osim zadnjeg čvora, čije polje "sljedeće" veze sadrži nulu referencu koja označava kraj popisa (u smjeru naprijed). Smjer unatrag djeluje slično. Referentna varijabla sadrži referencu na zadnji čvor smjera prema naprijed, što tumačite kao prvi čvor. Svaki čvor povezuje se s prethodnim čvorom putem polja "prethodni" link. "Prethodni" prvog čvorapolje veze sadrži nulu koja označava kraj popisa.

Pokušajte zamisliti dvostruko povezani popis kao par pojedinačno povezanih popisa, koji međusobno povezuju iste čvorove. Dijagram na slici 1. prikazuje topForward-referencirane i topBackward-referencirane pojedinačno povezane liste.

CRUD operacije na dvostruko povezanim popisima

Stvaranje, umetanje i brisanje čvorova sve su uobičajene operacije na dvostruko povezanom popisu. Slični su operacijama koje ste naučili za pojedinačno povezane popise. (Imajte na umu da je dvostruko povezan popis samo par pojedinačno povezanih popisa koji međusobno povezuju iste čvorove.) Sljedeći pseudokod pokazuje stvaranje i umetanje čvorova u dvostruko povezani popis prikazan na slici 1. Pseudokod također prikazuje čvor brisanje:

 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 

Primjer primjene: CRUD na dvostruko povezanom popisu

Primjer Java aplikacije DLLDemopokazuje kako stvoriti, umetnuti i izbrisati čvorove na dvostruko povezanom popisu. Izvorni kod aplikacije prikazan je u Popisu 1.

Popis 1. Java aplikacija koja pokazuje CRUD na dvostruko povezanom popisu

 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(); } } 

Sastavite popis 4 kako slijedi:

 javac DLLDemo.java 

Pokrenite rezultirajuću aplikaciju na sljedeći način:

 java DLLDemo 

Trebali biste promatrati sljedeći rezultat:

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

Premještanje dvostruko povezanih popisa

Okvir Java Collections uključuje Collectionsklasu korisnih metoda, koja je dio java.utilpaketa. Ova klasa uključuje void shuffle(List list)metodu koja " nasumično permitira navedeni popis koristeći zadani izvor slučajnosti ". Na primjer, ovu biste metodu mogli koristiti za miješanje špila karata izraženih kao dvostruko povezan popis (primjer je java.util.LinkedListklasa). U pseudokodu ispod možete vidjeti kako algoritam slučajnog miješanja može presložiti dvostruko povezan popis:

 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 

Nasumični algoritam dobiva izvor slučajnosti, a zatim prebacuje popis unatrag, od zadnjeg čvora do drugog. Nekoliko puta mijenja slučajno odabrani čvor (koji je zapravo samo polje imena) u "trenutni položaj". Čvorovi se nasumično biraju s dijela popisa koji se kreće od prvog čvora do uključivo trenutne pozicije. Imajte na umu da je ovaj algoritam grubo izvučen iz void shuffle(List list)izvornog koda.

Pseudokod algoritma slučajnog miješanja lijen je jer se usredotočuje samo na pojedinačno povezani popis koji se kreće unaprijed. To je razumna odluka o dizajnu, ali plaćamo cijenu zbog vremenske složenosti. Složenost vremena je O ( n 2). Prvo, imamo O ( n ) petlju koja poziva swap(). Drugo, unutar swap(), imamo dvije uzastopne O ( n ) petlje. Sjetite se sljedećeg pravila iz 1. dijela:

 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)). 

Dio (a) bavi se sekvencijalnim algoritmima. Ovdje imamo dvije O ( n ) petlje. Prema pravilu, rezultirajuća vremenska složenost bila bi O ( n ). Dio (b) bavi se ugniježđenim algoritmima. U ovom slučaju imamo O ( n ) pomnožen s O ( n ), što rezultira O ( n 2).

Note that Shuffle's space complexity is O(1), resulting from the helper variables that are declared.

Example application: Shuffling in a doubly-linked list

The Shuffle application in Listing 2 is a demonstration of the Shuffle algorithm.

Listing 2. The Shuffle algorithm 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; } } 

Compile Listing 5 as follows:

 javac Shuffle.java 

Run the resulting application as follows:

 java Shuffle 

You should observe the following output from one run:

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

Circular linked lists

The link field in the last node of a singly-linked list contains a null link. This is also true in a doubly-linked list, which contains the link fields in the last nodes of the forward and backward singly-linked lists. Suppose, instead, that the last nodes contained links to the first nodes. In this situation, you would end up with a circular-linked list, which is shown in Figure 2.

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.)
  • Oni nude brže umetanje / brisanje čvora od ekvivalentnih operacija temeljenih na nizu. Samo veze treba ažurirati nakon identificiranja položaja za umetanje / brisanje. Iz perspektive niza, umetanje stavke podataka zahtijeva pomicanje svih ostalih podataka kako bi se stvorio prazan element. Slično tome, brisanje postojeće stavke podataka zahtijeva kretanje svih ostalih stavki podataka kako bi se uklonio prazan element. Sve kretanje stavke podataka zahtijeva vrijeme.

Suprotno tome, nizovi nude sljedeće prednosti u odnosu na povezane popise:

  • Elementi niza zauzimaju manje memorije od čvorova jer elementi ne zahtijevaju polja veze.
  • Nizovi nude brži pristup stavkama podataka putem indeksa koji se temelje na cijelim brojevima.