I když mají jednotlivě propojené seznamy mnoho využití, představují také určitá omezení. Za prvé, jednotlivě propojené seznamy omezují procházení uzlů do jediného směru: nemůžete procházet jednotlivě propojeným seznamem zpět, pokud nejprve nezrušíte jeho odkazy na uzly, což vyžaduje čas. Pokud provedete reverzní traverz a potřebujete obnovit traverz uzlu do původního směru, budete muset inverzi opakovat, což zabere více času. Jednotlivé seznamy také omezují mazání uzlů. V tomto typu seznamu nemůžete odstranit libovolný uzel bez přístupu k předchůdci uzlu.
Naštěstí Java nabízí několik typů seznamů, které můžete použít k vyhledávání a třídění uložených dat ve vašich programech Java. Tento závěrečný tutoriál v Datové struktury a algoritmy série zavádí vyhledávání a třídění pomocí seznamů s dvojitým a kruhovým propojením. Jak uvidíte, tyto dvě kategorie datových struktur staví na seznamech, které jsou jednotlivě propojeny, a nabízejí širší škálu chování při vyhledávání a řazení ve vašich programech Java.
Zdvojnásobené seznamy
A dvojnásobně propojený seznam je propojený seznam uzlů, kde každý uzel má dvojici polí odkazů. Jedno pole odkazu umožňuje procházet seznamem dopředu, zatímco druhé uzel umožňuje procházet seznamem dozadu. Pro směr vpřed obsahuje referenční proměnná odkaz na první uzel. Každý uzel se připojuje k dalšímu uzlu prostřednictvím pole odkazu „další“, s výjimkou posledního uzlu, jehož pole odkazu „další“ obsahuje nulový odkaz, který označuje konec seznamu (ve směru dopředu). Zpětný směr funguje podobně. Referenční proměnná obsahuje odkaz na poslední uzel dopředného směru, který interpretujete jako první uzel. Každý uzel odkazuje na předchozí uzel prostřednictvím pole odkazu „předchozí“. Pole odkazu „předchozí“ prvního uzlu obsahuje hodnotu null, která označuje konec seznamu.
Pokuste se uvažovat o dvojnásobně propojeném seznamu jako o dvojici samostatně propojených seznamů, z nichž každý propojuje stejné uzly. Schéma na obrázku 1 ukazuje nahoruVpřed- odkazováno a nahoru Zpět- odkazované jednotlivě propojené seznamy.
Operace CRUD v seznamech s dvojnásobným propojením
Vytváření, vkládání a mazání uzlů jsou všechny běžné operace v seznamu s dvojitým propojením. Jsou podobné operacím, které jste se naučili u seznamů s jednoduchým propojením. (Nezapomeňte, že seznam s dvojitým propojením je pouze dvojice seznamů s jednoduchým propojením, které propojují stejné uzly.) Následující pseudokód demonstruje vytvoření a vložení uzlů do seznamu s dvojitým propojením, který je znázorněn na obrázku 1. Pseudokód také ukazuje uzel vymazání:
DECLARE CLASS Uzel DECLARE STRING jméno DECLARE Uzel další DECLARE Uzel předchozí KONEC DECLARE DECLARE Uzel topForward DECLARE Uzel temp DECLARE Uzel topBackward topForward = NOVÝ Uzel topForward.name = "A" temp = NOVÝ Uzel temp.name = "B" topBackack = NOVÝ .name = "C" // Vytvořit dopředu jednotlivě propojený seznam topForward.next = temp temp.next = topBackward topBackward.next = NULL // Vytvořit zpět jednotlivě propojený seznam topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Odstranit uzel 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. KONEC Příklad aplikace: CRUD v seznamu s dvojím propojením
Ukázková aplikace Java DLLDemo ukazuje, jak vytvořit, vložit a odstranit uzly v seznamu s dvojitým propojením. Zdrojový kód aplikace je uveden v seznamu 1.
Výpis 1. Aplikace Java demonstrující CRUD v seznamu, který je dvojnásobně propojen
public final class DLLDemo {private static class Node {String name; Uzel další; Uzel předchozí; } public static void main (String [] args) {// Sestavte seznam propojený dvakrát. Uzel topForward = nový uzel (); topForward.name = "A"; Teplota uzlu = nový uzel (); temp.name = "B"; Uzel topBackward = nový uzel (); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Vypíše dopředu jednotlivě propojený seznam. System.out.print ("Přeposlat jednotlivě propojený seznam:"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Dump backly singly-linked list. System.out.print ("Zpětně jednotlivě propojený seznam:"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); // Referenční uzel B. temp = topForward.next; // Odstranit uzel B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Vypíše dopředu jednotlivě propojený seznam. System.out.print ("Přeposlat jednotlivě propojený seznam (po odstranění):"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Dump backly singly-linked list. System.out.print ("Zpětně jednotlivě propojený seznam (po odstranění):"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); }} Sestavte výpis 4 takto:
javac DLLDemo.java Výslednou aplikaci spusťte následovně:
java DLLDemo Měli byste dodržovat následující výstup:
Předat jednotlivě propojený seznam: ABC Zpět zpět jednotlivě propojený seznam: CBA Předat jednotlivě propojený seznam (po odstranění): AC Zpětně jednotlivě propojený seznam (po odstranění): CA Zamíchání do seznamů s dvojitým propojením
Rámec kolekce Java obsahuje a Sbírky třída užitkových metod, která je součástí java.util balík. Tato třída zahrnuje a void shuffle (seznam) metoda, která "náhodně permutuje zadaný seznam pomocí výchozího zdroje náhodnosti. "Tuto metodu můžete například použít k zamíchání balíčku karet, který je vyjádřen jako dvojnásobně propojený seznam ( java.util.LinkedList třída je příkladem). V níže uvedeném pseudokódu můžete vidět, jak Náhodný algoritmus může zamíchat dvojnásobně propojený seznam:
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 // Vyhledejte ten uzel. Uzel nodei = top FOR k = 0 TO i - 1 nodei = nodei.next END FOR // Vyhledejte j-tý uzel. Uzel nodej = top FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Proveďte swap. DECLARE STRING namei = nodei.name DECLARE STRING namej = nodej.name nodej.name = namei nodei.name = namej KONEC FUNKCE KONEC Algoritmus Shuffle získá zdroj náhodnosti a poté prochází seznam zpět, od posledního uzlu až po druhý. Opakovaně zamění náhodně vybraný uzel (což je ve skutečnosti pouze pole názvu) do „aktuální polohy“. Uzly jsou náhodně vybírány z části seznamu, která běží od prvního uzlu po aktuální pozici včetně. Všimněte si, že tento algoritmus je zhruba vyňat z void shuffle (seznam)zdrojový kód.
Pseudokód algoritmu Shuffle je líný, protože se zaměřuje pouze na dopředu procházející jednotlivě propojený seznam. Je to rozumné konstrukční rozhodnutí, ale za časovou složitost za něj platíme cenu. Časová složitost je O (n2). Nejprve máme O (n) smyčka, která volá vyměnit (). Zadruhé, uvnitř vyměnit (), máme dvě postupná O (n) smyčky. Připomeňme si následující pravidlo z části 1:
Li f1(n) = O (G(n)) a f2(n) = O (h(n)) pak) f1(n)+f2(n) = max (O (G(n)), O (h(n))) (b) f1(n)*f2(n) = O (G(n)*h(n)). Část (a) se zabývá sekvenčními algoritmy. Tady máme dvě O (n) smyčky. Podle pravidla by výsledná časová složitost byla O (n). Část (b) se zabývá vnořenými algoritmy. V tomto případě máme O (n) vynásobeno O (n), což má za následek O (n2).
Všimněte si, že Shufflova prostorová složitost je O (1), vyplývající z pomocných proměnných, které jsou deklarovány.
Příklad aplikace: Náhodné přehrávání v seznamu s dvojitým propojením
The Zamíchat aplikace ve Výpisu 2 je ukázkou algoritmu Shuffle.
Výpis 2. Algoritmus Shuffle v Javě
import java.util.Random; public final class Shuffle {private static class Node {String name; Uzel další; Uzel předchozí; } public static void main (String [] args) {// Sestavte seznam propojený dvakrát. Uzel topForward = nový uzel (); topForward.name = "A"; Teplota uzlu = nový uzel (); temp.name = "B"; Uzel topBackward = nový uzel (); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Vypíše dopředu jednotlivě propojený seznam. System.out.print ("Přeposlat jednotlivě propojený seznam:"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Dump backly singly-linked list. System.out.print ("Zpětně jednotlivě propojený seznam:"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); // Náhodný seznam. Random rnd = new Random (); for (int i = 3; i> 1; i--) swap (topForward, i - 1, rnd.nextInt (i)); // Vypíše dopředu jednotlivě propojený seznam. System.out.print ("Přeposlat jednotlivě propojený seznam:"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Dump backly singly-linked list. System.out.print ("Zpětně jednotlivě propojený seznam:"); 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) {// Vyhledejte ten uzel. Uzel nodei = nahoře; pro (int k = 0; k <i; k ++) nodei = nodei.next; // Najděte j-tý uzel. Uzel nodej = top; for (int k = 0; k <j; k ++) nodej = nodej.next; Řetězec namei = nodei.name; Řetězec namej = nodej.name; nodej.name = namei; nodei.name = namej; }} Sestavte výpis 5 následujícím způsobem:
javac Shuffle.java Výslednou aplikaci spusťte následovně:
Java Shuffle Měli byste sledovat následující výstup z jednoho běhu:
Dopředu jednotlivě propojený seznam: ABC Zpět dopředu jednotlivě propojený seznam: CBA Dopředu jednotlivě propojený seznam: BAC Zpětně jednotlivě spojený seznam: CAB Kruhové propojené seznamy
Pole odkazu v posledním uzlu jednotlivě propojeného seznamu obsahuje nulový odkaz. To platí také pro seznam s dvojitým propojením, který obsahuje pole odkazů v posledních uzlech seznamů s přímým spojením vpřed a vzad. Předpokládejme, že poslední uzly obsahovaly odkazy na první uzly. V této situaci byste skončili s kruhový seznam, který je znázorněn na obrázku 2.
Seznamy kruhového propojení, známé také jako kruhové nárazníky nebo kruhové fronty, mají mnoho využití. Používají se například obslužnými rutinami přerušení operačního systému k vyrovnávání stisknutí kláves. Multimediální aplikace používají kruhové seznamy k ukládání dat do vyrovnávací paměti (například ukládání dat do vyrovnávací paměti při zápisu na zvukovou kartu). Tuto techniku také používá rodina bezztrátových algoritmů komprese dat LZ77.
Propojené seznamy versus pole
V celé této sérii o datových strukturách a algoritmech jsme zvažovali silné a slabé stránky různých datových struktur. Protože jsme se zaměřili na pole a propojené seznamy, můžete mít ohledně těchto typů konkrétně otázky. Jaké výhody a nevýhody nabízejí propojené seznamy a pole? Kdy použijete propojený seznam a kdy použijete pole? Lze datové struktury z obou kategorií integrovat do užitečné hybridní datové struktury? Pokusím se odpovědět na tyto otázky níže.
Propojené seznamy nabízejí oproti polím následující výhody:
- Na podporu expanze nevyžadují další paměť. Naproti tomu pole vyžadují další paměť, když je nutné rozšíření. (Jakmile všechny prvky obsahují datové položky, nelze k poli přidat žádné nové datové položky.)
- Nabízejí rychlejší vkládání / mazání uzlů než ekvivalentní operace založené na poli. Po identifikaci pozice vložení / odstranění je třeba aktualizovat pouze odkazy. Z pohledu pole vyžaduje vložení datové položky pohyb všech ostatních datových položek k vytvoření prázdného prvku. Podobně odstranění existující datové položky vyžaduje přesun všech ostatních datových položek k odstranění prázdného prvku. Pohyb všech datových položek nějakou dobu trvá.
Naproti tomu pole nabízejí oproti propojeným seznamům následující výhody:
- Prvky pole zabírají méně paměti než uzly, protože prvky nevyžadují pole odkazů.
- Pole nabízejí rychlejší přístup k datovým položkám prostřednictvím celočíselných indexů.
