Aj keď majú jednotlivo prepojené zoznamy mnoho použití, predstavujú aj určité obmedzenia. Pre jednu vec, jednotlivo prepojené zoznamy obmedzujú prechod uzlov do jedného smeru: nemôžete samostatne prechádzať jednotlivo prepojený zoznam dozadu, pokiaľ najskôr nezvrátite jeho prepojenia uzlov, čo si vyžaduje čas. Ak urobíte reverzný traverz a potrebujete obnoviť traverz uzla do pôvodného smeru, budete musieť inverziu opakovať, čo trvá dlhšie. Samostatne spojené zoznamy tiež obmedzujú mazanie uzlov. V tomto type zoznamu nemôžete odstrániť ľubovoľný uzol bez prístupu k predchodcovi uzla.
Našťastie Java ponúka niekoľko typov zoznamov, ktoré môžete použiť na vyhľadávanie a triedenie uložených údajov vo vašich programoch Java. Tento záverečný návod v Dátové štruktúry a algoritmy séria predstavuje vyhľadávanie a triedenie pomocou zoznamov s dvojnásobným a kruhovým odkazom. Ako uvidíte, tieto dve kategórie dátových štruktúr vychádzajú z jednotlivo prepojených zoznamov a ponúkajú širšie spektrum správania pri prehľadávaní a triedení vo vašich programoch Java.
Zdvojnásobené zoznamy
A dvojnásobne prepojený zoznam je prepojený zoznam uzlov, kde každý uzol má dvojicu polí odkazov. Jedno pole odkazu vám umožní prechádzať zoznamom vpred, zatiaľ čo druhé uzol vám umožní prechádzať zoznamom dozadu. Pre smer vpred má referenčná premenná odkaz na prvý uzol. Každý uzol odkazuje na ďalší uzol prostredníctvom poľa „nasledujúceho“ odkazu, okrem posledného uzla, ktorého pole „ďalšieho“ odkazu obsahuje nulový odkaz, ktorý označuje koniec zoznamu (v smere dopredu). Spätný smer funguje podobne. Referenčná premenná obsahuje odkaz na posledný uzol smerom dopredu, ktorý interpretujete ako prvý uzol. Každý uzol odkazuje na predchádzajúci uzol prostredníctvom poľa „predchádzajúci“. Pole „predchádzajúci“ odkaz prvého uzla obsahuje nulu, ktorá označuje koniec zoznamu.
Pokúste sa uvažovať o dvojnásobne prepojenom zozname ako o dvojici samostatne prepojených zoznamov, z ktorých každý prepája rovnaké uzly. Schéma na obrázku 1 ukazuje topForward-zmienené a topBackward-referencované jednotlivo prepojené zoznamy.
Operácie CRUD na dvojnásobne prepojených zoznamoch
Vytváranie, vkladanie a mazanie uzlov sú všetky bežné operácie v zozname, ktorý je dvojnásobne prepojený. Sú podobné operáciám, ktoré ste sa naučili pri zoznamoch, ktoré sú navzájom spojené. (Pamätajte, že zoznam s dvojnásobným prepojením je iba dvojica zoznamov s jednoduchým prepojením, ktoré vzájomne prepájajú rovnaké uzly.) Nasledujúci pseudokód demonštruje vytvorenie a vloženie uzlov do zoznamu s dvojnásobným prepojením, ktorý je znázornený na obrázku 1. Pseudokód tiež demonštruje uzol vypustenie:
VYHLASOVAŤ TRIEDU Uzol VYHLASOVAŤ STRING názov VYHLASOVAŤ Uzol ďalší VYHLASOVAŤ Uzol predchádzajúci UKONČIŤ VYHLASOVAŤ VYHLASOVAŤ Uzol hore Vpred VYHLASOVAŤ Uzol temp VYHLASOVAŤ Uzol horeBackward topForward = NOVÝ Uzol topForward.name = "A" temp = NOVÝ Uzol temp.name = "B" topBackback = NOVÝ .name = "C" // Vytvoriť dopredu jednotlivo prepojený zoznam topForward.next = temp temp.next = topBackward topBackward.next = NULL // Vytvoriť spätne jednotlivo prepojený zoznam topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Odstrániť uzol B. temp.prev.next = temp.next; // Obíďte uzol B v samostatnom prepojenom zozname. temp.next.prev = temp.prev; // Obíďte uzol B v spätne jednotlivo prepojenom zozname. KONIEC Príklad aplikácie: CRUD v zozname, ktorý je prepojený dvakrát
Ukážka aplikácie Java DLLDemo demonštruje, ako vytvárať, vkladať a mazať uzly v zozname, ktorý je dvojnásobne prepojený. Zdrojový kód aplikácie je uvedený v zozname 1.
Zoznam 1. Aplikácia Java demonštrujúca CRUD v zozname, ktorý je dvojnásobne prepojený
verejná konečná trieda DLLDemo {súkromná statická trieda Uzol {názov reťazca; Uzol ďalej; Uzol prev; } public static void main (String [] args) {// Vytvorenie dvojnásobne prepojeného zoznamu. Uzol topForward = nový Uzol (); topForward.name = "A"; Teplota uzla = nový Uzol (); temp.name = "B"; Uzol topBackward = nový Uzol (); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Vypíše dopredu prepojený zoznam. System.out.print ("Preposlať jednotlivo prepojený zoznam:"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Dump backly singly-linked list. System.out.print ("Spätne prepojený zoznam:"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); // Referenčný uzol B. temp = topForward.next; // Vymazať uzol B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Vypíše dopredu prepojený zoznam. System.out.print ("Preposlať jednotlivo prepojený zoznam (po odstránení):"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Dump backly singly-linked list. System.out.print ("Spätne prepojený zoznam (po odstránení):"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); }} Zostavte zoznam 4 nasledovne:
javac DLLDemo.java Výslednú aplikáciu spustite nasledujúcim spôsobom:
java DLLDemo Mali by ste dodržiavať nasledujúci výstup:
Preposlať jednotlivo prepojený zoznam: ABC Spätne prepojený zoznam: CBA Preposlať jednotlivo prepojený zoznam (po odstránení): AC Spätne prepojený zoznam (po odstránení): CA Zamiešanie do zoznamov s dvojnásobným prepojením
Rámec kolekcií Java obsahuje a Zbierky trieda úžitkových metód, ktorá je súčasťou java.util balíček. Táto trieda obsahuje a void shuffle (zoznam) metóda, ktorá "náhodne permutuje zadaný zoznam pomocou predvoleného zdroja náhodnosti. "Túto metódu môžete použiť napríklad na to, aby ste zamiešali balíček kariet vyjadrený ako dvojnásobne prepojený zoznam ( java.util.LinkedList triedy je príkladom). V pseudokóde nižšie vidíte, ako Algoritmus náhodného výberu môže zameniť dvojnásobne prepojený zoznam:
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 // Nájdite i-tý uzol. Uzol nodei = top FOR k = 0 TO i - 1 nodei = nodei.ďalší KONIEC FOR // Vyhľadajte j-tý uzol. Uzol nodej = top FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Vykonať swap. DECLARE STRING namei = nodei.name DECLARE STRING namej = nodej.name nodej.name = namei nodei.name = namej UKONČIŤ FUNKCIU KONIEC Algoritmus Shuffle získa zdroj náhodnosti a potom prechádza zoznamom dozadu, od posledného uzla po druhý. Opakovane zamieňa náhodne vybraný uzol (čo je vlastne iba pole s menom) do „aktuálnej polohy“. Uzly sa vyberajú náhodne z časti zoznamu, ktorá vedie od prvého uzla po aktuálnu pozíciu vrátane. Upozorňujeme, že tento algoritmus je zhruba vyňatý z void shuffle (zoznam)zdrojový kód.
Pseudokód algoritmu Shuffle je lenivý, pretože sa zameriava iba na dopredu prepojený jednotlivo prepojený zoznam. Je to rozumné konštrukčné rozhodnutie, ale za časovú zložitosť zaň platíme. Časová zložitosť je O (n2). Najprv máme O (n) slučka, ktorá volá vymeniť (). Po druhé, vo vnútri vymeniť (), máme dve postupné O (n) slučky. Pripomeňme si toto pravidlo z časti 1:
Ak f1(n) = O (g(n)) a f2(n) = O (h(n)) potom) f1(n)+f2(n) = max (O (g(n)), O (h(n))) (b) f1(n)*f2(n) = O (g(n)*h(n)). Časť (a) sa zaoberá sekvenčnými algoritmami. Tu máme dve O (n) slučky. Podľa pravidla by výsledná časová zložitosť bola O (n). Časť (b) sa zaoberá vnorenými algoritmami. V tomto prípade máme O (n) vynásobené O (n), ktorého výsledkom je O (n2).
Všimnite si, že Shuffleho priestorová zložitosť je O (1), ktorá je výsledkom deklarovaných pomocných premenných.
Príklad aplikácie: Miešanie v zozname, ktorý je dvakrát prepojený
The Zamiešať Aplikácia v zozname 2 predstavuje ukážku algoritmu Shuffle.
Výpis 2. Algoritmus Shuffle v Jave
import java.util.Random; verejná finálna trieda Náhodne {súkromná statická trieda Uzol {Názov reťazca; Uzol ďalej; Uzol prev; } public static void main (String [] args) {// Vytvorenie dvojnásobne prepojeného zoznamu. Uzol topForward = nový Uzol (); topForward.name = "A"; Teplota uzla = nový Uzol (); temp.name = "B"; Uzol topBackward = nový Uzol (); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Vypíše dopredu prepojený zoznam. System.out.print ("Preposlať jednotlivo prepojený zoznam:"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Dump backly singly-linked list. System.out.print ("Spätne prepojený zoznam:"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); // Náhodný zoznam. Random rnd = new Random (); for (int i = 3; i> 1; i--) swap (topForward, i - 1, rnd.nextInt (i)); // Vypíše dopredu prepojený zoznam. System.out.print ("Preposlať jednotlivo prepojený zoznam:"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Dump backly singly-linked list. System.out.print ("Spätne prepojený zoznam:"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); } public static void swap (Uzol top, int i, int j) {// Vyhľadajte ten uzol. Uzol nodei = top; pre (int k = 0; k <i; k ++) nodei = nodei.next; // Vyhľadajte j-tý uzol. Uzol nodej = top; pre (int k = 0; k <j; k ++) nodej = nodej.next; Reťazec namei = nodei.name; Reťazec namej = nodej.name; nodej.name = namei; nodei.name = namej; }} Zostavte zoznam 5 takto:
javac Shuffle.java Výslednú aplikáciu spustite nasledujúcim spôsobom:
java Shuffle Mali by ste sledovať nasledujúci výstup z jedného behu:
Dopredu singel-prepojený zoznam: ABC Spätne do singel-prepojeného zoznamu: CBA Dopredu singel-prepojený zoznam: BAC Spätne singly-prepojený zoznam: CAB Kruhové prepojené zoznamy
Pole odkazu v poslednom uzle jednotlivo prepojeného zoznamu obsahuje nulový odkaz. To platí aj pre zoznam s dvojnásobným prepojením, ktorý obsahuje polia s odkazmi v posledných uzloch dopredu a dozadu jednotlivo prepojených zoznamov. Namiesto toho predpokladajme, že posledné uzly obsahovali odkazy na prvé uzly. V tejto situácii by ste skončili s a zoznam s cyklickým odkazom, ktorý je znázornený na obrázku 2.
Zoznamy kruhového prepojenia, známe tiež ako kruhové nárazníky alebo kruhové fronty, majú veľa využití. Používajú ich napríklad obslužné programy prerušenia operačného systému na vyrovnanie stlačenia klávesov. Multimediálne aplikácie používajú na vyrovnanie údajov údaje v kruhovom zozname (napríklad ukladanie údajov do zvukovej karty do vyrovnávacej pamäte). Túto techniku používa aj rodina bezstratových algoritmov kompresie dát LZ77.
Prepojené zoznamy verzus polia
V celom tomto seriáli o dátových štruktúrach a algoritmoch sme uvažovali o silných a slabých stránkach rôznych dátových štruktúr. Pretože sme sa zamerali na polia a prepojené zoznamy, mohli by ste mať konkrétne otázky týkajúce sa týchto typov. Aké výhody a nevýhody ponúkajú prepojené zoznamy a polia? Kedy použijete prepojený zoznam a kedy pole? Je možné dátové štruktúry z oboch kategórií integrovať do užitočnej hybridnej dátovej štruktúry? Pokúsim sa na tieto otázky odpovedať nižšie.
Prepojené zoznamy ponúkajú oproti poliam nasledujúce výhody:
- Na podporu rozšírenia nevyžadujú dodatočnú pamäť. Na rozdiel od toho polia vyžadujú v prípade potreby rozšírenia pamäť navyše. (Len čo všetky prvky obsahujú dátové položky, k poľu nemožno pridať žiadne nové dátové položky.)
- Ponúkajú rýchlejšie vkladanie / mazanie uzlov ako ekvivalentné operácie založené na poli. Po identifikácii polohy vloženia / odstránenia je potrebné aktualizovať iba odkazy. Z pohľadu poľa vyžaduje vloženie dátovej položky presun všetkých ostatných dátových položiek, aby sa vytvoril prázdny prvok. Podobne vymazanie existujúcej dátovej položky vyžaduje presun všetkých ostatných dátových položiek, aby sa odstránil prázdny prvok. Pohyb všetkých dátových položiek chvíľu trvá.
Na rozdiel od toho polia poskytujú oproti prepojeným zoznamom tieto výhody:
- Prvky poľa zaberajú menej pamäte ako uzly, pretože prvky nevyžadujú polia odkazov.
- Polia ponúkajú rýchlejší prístup k dátovým položkám prostredníctvom celočíselných indexov.
