Programiranje

Podatkovne strukture in algoritmi v Javi, 5. del: Dvojno povezani seznami

Čeprav imajo posamezno povezani seznami več uporab, pa imajo tudi nekatere omejitve. Nekaj, enojno povezani seznami omejujejo prehod vozlišča v eno smer: enojno povezanega seznama ni mogoče premakniti nazaj, razen če najprej obrnete njegove vozliščne povezave, kar zahteva čas. Če izvedete obratno preusmeritev in želite obnoviti prehod vozlišča v prvotno smer, boste morali ponoviti pretvorbo, kar traja več časa. Enotno povezani seznami prav tako omejujejo brisanje vozlišč. Na tej vrsti seznama ne morete izbrisati poljubnega vozlišča brez dostopa do predhodnika vozlišča.

Na srečo Java ponuja več vrst seznamov, s katerimi lahko iščete in razvrščate shranjene podatke v svojih programih Java. Ta zadnja vadnica v Podatkovne strukture in algoritmi serija uvaja iskanje in razvrščanje z dvojno povezanimi seznami in krožno povezanimi seznami. Kot boste videli, se ti dve kategoriji podatkovne strukture nadgradita na posamezno povezanih seznamih in nudita širši nabor vedenja iskanja in razvrščanja v vaših programih Java.

Dvojno povezani seznami

A dvojno povezan seznam je povezan seznam vozlišč, kjer ima vsako vozlišče par polj povezav. Eno polje s povezavo vam omogoča, da prečkate seznam v smeri naprej, drugo vozlišče pa po seznamu v smeri nazaj. Za smer naprej ima referenčna spremenljivka referenco na prvo vozlišče. Vsako vozlišče se poveže z naslednjim vozliščem prek polja "naslednje", razen zadnjega vozlišča, katerega polje "naslednje" vsebuje ničelno referenco, ki označuje konec seznama (v smeri naprej). Vzvratna smer deluje podobno. Referenčna spremenljivka vsebuje sklic na zadnje vozlišče smeri naprej, ki ga interpretirate kot prvo vozlišče. Vsako vozlišče se poveže s prejšnjim vozliščem prek polja "prejšnje". Polje "prejšnje" povezave prvega vozlišča vsebuje nulo, kar pomeni konec seznama.

Poskusite si predstavljati dvojno povezan seznam kot par posamezno povezanih seznamov, ki medsebojno povezujejo ista vozlišča. Diagram na sliki 1 prikazuje topForward-referencirano in vrhNazaj-navedeni enojno povezani seznami.

CRUD operacije na dvojno povezanih seznamih

Ustvarjanje, vstavljanje in brisanje vozlišč so vse pogoste operacije na dvojno povezanem seznamu. Podobne so operacijam, ki ste se jih naučili za posamezno povezane sezname. (Ne pozabite, da je dvojno povezan seznam le par posamezno povezanih seznamov, ki medsebojno povezujejo ista vozlišča.) Naslednja psevdokoda prikazuje ustvarjanje in vstavljanje vozlišč v dvojno povezan seznam, prikazan na sliki 1. Psevkodo prikazuje tudi vozlišče izbris:

 DECLARE CLASS Vozlišče DECLARE STRING name DECLARE Node next DECLARE Node prev END END DECLARE DECLARE Vozlišče topForward DECLARE Node temp DECLARE Node topBackward topForward = NEW Node topForward.name = "A" temp = NEW Node temp.odeaB .name = "C" // Ustvari posamično povezan seznam topForward.next = temp temp.next = topBackward topBackward.next = NULL // Ustvari nazaj enojno povezan seznam topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Izbriši vozlišče B. temp.prev.next = temp.next; // Obvozimo vozlišče B na posamično povezanem seznamu. temp.next.prev = temp.prev; // Obvozimo vozlišče B na za nazaj povezanem seznamu. KONEC 

Primer uporabe: CRUD na dvojno povezanem seznamu

Primer aplikacije Java DLLDemo prikazuje, kako ustvariti, vstaviti in izbrisati vozlišča na dvojno povezanem seznamu. Izvorna koda aplikacije je prikazana v seznamu 1.

Seznam 1. Aplikacija Java, ki prikazuje CRUD na dvojno povezanem seznamu

 javni končni razred DLLDemo {zasebni statični razred vozlišče {ime niza; Vozlišče naslednje; Vozlišče prev; } public static void main (String [] args) {// Sestavite dvojno povezan seznam. Vozlišče topForward = novo vozlišče (); topForward.name = "A"; Temp vozlišča = novo vozlišče (); temp.name = "B"; Node topBackward = novo Node (); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump naprej posamično povezan seznam. System.out.print ("Posreduj posamezno povezan seznam:"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Odvržemo nazaj posamično povezan seznam. System.out.print ("Enostavno povezan seznam:"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); // Referenčno vozlišče B. temp = topForward.next; // Izbriši vozlišče B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Dump naprej posamično povezan seznam. System.out.print ("Posreduj posamezno povezan seznam (po izbrisu):"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Odvržemo nazaj posamično povezan seznam. System.out.print ("Enostavno povezan seznam (po izbrisu):"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); }} 

Sestavite seznam 4, kot sledi:

 javac DLLDemo.java 

Nastalo aplikacijo zaženite na naslednji način:

 java DLLDemo 

Upoštevati morate naslednje rezultate:

 Posreduj posamično povezan seznam: ABC Povratno posamično povezan seznam: CBA Posreduj posamično povezan seznam (po izbrisu): AC Povratno posamično povezan seznam (po izbrisu): CA 

Premeščanje dvojno povezanih seznamov

Okvir Java Collections vključuje a Zbirke razred uporabnostnih metod, ki je del java.util paket. Ta razred vključuje naključno mešanje (seznam seznamov) metoda, ki "naključno permutira navedeni seznam z uporabo privzetega vira naključnosti. "Na primer s to metodo lahko premešate špil kart, izražen kot dvojno povezan seznam ( java.util.LinkedList razred je primer). V spodnjem psevdokodu lahko vidite, kako Naključni algoritem lahko premeša dvojno povezan seznam:

 IZGLASI RANDOM rnd = novo 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 Nodei vozlišča, nodej DECLARE INTEGER k // Poiščite i vozlišče. Vozlišče nodei = top FOR k = 0 TO i - 1 nodei = nodei.next END FOR // Poiščite jth vozlišče. Vozlišče nodej = vrh FOR k = 0 DO i - 1 nodej = nodej.next END FOR // Izvedite zamenjavo. NAVEDI STRAN namei = nodei.name NAVEDI STRING namej = nodej.name nodej.name = namei nodei.name = namej KONEC FUNKCIJA KONEC 

Algoritem naključnega iskanja pridobi vir naključnosti in nato preusmeri seznam nazaj, od zadnjega vozlišča do drugega. Naključno izbrano vozlišče (ki je pravzaprav samo ime) večkrat zamenja v "trenutni položaj". Vozlišča so naključno izbrana z dela seznama, ki poteka od prvega vozlišča do vključno s trenutnim položajem. Upoštevajte, da je ta algoritem približno izvlečen iz naključno mešanje (seznam seznamov)izvorna koda.

Psevkodo naključnega algoritma je leno, ker se osredotoča le na posamično povezan seznam za naprej. To je razumna oblikovalska odločitev, vendar jo plačamo v časovni zapletenosti. Zapletenost časa je O (n2). Najprej imamo O (n) zanka, ki kliče zamenjaj (). Drugič, znotraj zamenjaj (), imamo dva zaporedna O (n) zanke. Spomnite se naslednjega pravila iz 1. dela:

 Če f1(n) = O (g(n)) in f2(n) = O (h(n)) nato (a) f1(n)+f2(n) = največ (O (g(n)), O (h(n))) (b) f1(n)*f2(n) = O (g(n)*h(n)). 

Del (a) obravnava zaporedne algoritme. Tu imamo dva O (n) zanke. V skladu s pravilom bi bila posledična zapletenost časa O (n). Del (b) obravnava ugnezdene algoritme. V tem primeru imamo O (n) pomnoženo z O (n), kar ima za posledico O (n2).

Upoštevajte, da je zapletenost prostora Shuffle O (1), ki je posledica deklariranih pomožnih spremenljivk.

Primer uporabe: Naključno premeščanje na dvojno povezanem seznamu

The Naključno aplikacija iz seznama 2 je prikaz algoritma naključnega predvajanja.

Seznam 2. Algoritem naključnega predvajanja v Javi

 uvoz java.util.Random; javni končni razred Shuffle {private static class Node {String name; Vozlišče naslednje; Vozlišče prev; } public static void main (String [] args) {// Sestavite dvojno povezan seznam. Vozlišče topForward = novo vozlišče (); topForward.name = "A"; Temp vozlišča = novo vozlišče (); temp.name = "B"; Node topBackward = novo Node (); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump naprej posamično povezan seznam. System.out.print ("Posreduj posamezno povezan seznam:"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Odvržemo nazaj posamično povezan seznam. System.out.print ("Nazaj na enojno povezan seznam:"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); // Naključni seznam. Naključno rnd = novo naključno (); za (int i = 3; i> 1; i--) zamenjavo (topForward, i - 1, rnd.nextInt (i)); // Dump naprej posamično povezan seznam. System.out.print ("Posreduj posamezno povezan seznam:"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Odvržemo nazaj posamično povezan seznam. System.out.print ("Nazaj na enojno povezan seznam:"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); } javna statična void zamenjava (Node top, int i, int j) {// Poiščite i vozlišče. Vozlišče nodei = vrh; za (int k = 0; k <i; k ++) nodei = nodei.next; // Poiščite jth vozlišče. Vozlišče nodej = vrh; za (int k = 0; k <j; k ++) nodej = nodej.next; Niz imenai = nodei.name; Niz imenaj = nodej.name; nodej.name = namei; nodei.name = namej; }} 

Sestavite seznam 5, kot sledi:

 javac Naključno.java 

Nastalo aplikacijo zaženite na naslednji način:

 java Naključno 

Upoštevati morate naslednji izhod iz enega poteka:

 Posreduj posamično povezan seznam: ABC Povratek posamično povezan seznam: CBA Posreduj posamično povezan seznam: BAC Zadaj posamično povezan seznam: CAB 

Krožno povezani seznami

Polje povezave v zadnjem vozlišču posamezno povezanega seznama vsebuje nično povezavo. To velja tudi za dvojno povezan seznam, ki vsebuje polja povezav v zadnjih vozliščih posamično povezanih seznamov naprej in nazaj. Recimo, da so zadnja vozlišča vsebovala povezave do prvih vozlišč. V tej situaciji bi končali z krožno povezan seznam, ki je prikazan na sliki 2.

Krožno povezani seznami, znani tudi kot krožni odbojniki ali krožne čakalne vrste, imajo veliko uporab. Na primer, uporabljajo jih upravljavci prekinitev operacijskega sistema za medpomnjenje tipk. Multimedijske aplikacije uporabljajo krožno povezane sezname za medpomnjenje podatkov (na primer medpomnjenje podatkov, ki se zapisujejo na zvočno kartico). To tehniko uporablja tudi družina LZ77 algoritmov za stiskanje podatkov brez izgub.

Povezani seznami v primerjavi z nizi

V tej seriji podatkovnih struktur in algoritmov smo upoštevali prednosti in slabosti različnih podatkovnih struktur. Ker smo se osredotočili na polja in povezane sezname, imate morda vprašanja o teh vrstah. Katere prednosti in slabosti ponujajo povezani seznami in nizi? Kdaj uporabljate povezan seznam in kdaj matriko? Ali je mogoče podatkovne strukture iz obeh kategorij vključiti v uporabno hibridno podatkovno strukturo? Na ta vprašanja bom poskušal odgovoriti spodaj.

Povezani seznami ponujajo naslednje prednosti pred nizi:

  • Za podporo širitvi ne potrebujejo dodatnega pomnilnika. Nasprotno pa nizi potrebujejo dodaten pomnilnik, kadar je razširitev potrebna. (Ko vsi elementi vsebujejo podatkovne postavke, v matriko ni mogoče dodati novih podatkovnih elementov.)
  • Ponujajo hitrejše vstavljanje / brisanje vozlišč kot enakovredne operacije na osnovi matrike. Posodobiti je treba le povezave po določitvi položaja za vstavljanje / brisanje. Z vidika polja vstavljanje podatkovnih elementov zahteva premikanje vseh drugih podatkovnih elementov, da se ustvari prazen element. Podobno tudi brisanje obstoječega podatkovnega elementa zahteva premikanje vseh drugih podatkovnih elementov, da odstranite prazen element. Vse premikanje podatkovnega elementa zahteva čas.

Nasprotno pa polja ponujajo naslednje prednosti pred povezanimi seznami:

  • Elementi polja zavzamejo manj pomnilnika kot vozlišča, ker elementi ne zahtevajo polj povezav.
  • Polja ponujajo hitrejši dostop do podatkovnih postavk prek indeksov, ki temeljijo na številu.
$config[zx-auto] not found$config[zx-overlay] not found