Nors atskirai susieti sąrašai gali būti naudojami daugeliu atvejų, jie taip pat nustato tam tikrus apribojimus. Viena vertus, atskirai susieti sąrašai apriboja mazgų judėjimą viena kryptimi: jūs negalite pereiti atskirai susieto sąrašo atgal, nebent pirmiausia pakeisite jo mazgo nuorodas, o tai užtrunka. Jei atliksite atvirkštinį važiavimą ir jums reikės atstatyti mazgų perėjimą į pradinę kryptį, turėsite pakartoti inversiją, o tai užtruks daugiau laiko. Atskirai susieti sąrašai taip pat riboja mazgų ištrynimą. Šio tipo sąraše negalite ištrinti savavališko mazgo be prieigos prie mazgo pirmtako.
Laimei, „Java“ siūlo keletą tipų sąrašų, kuriuos galite naudoti ieškodami ir rūšiuodami „Java“ programų saugomus duomenis. Ši baigiamoji pamoka Duomenų struktūros ir algoritmai serijoje pristatoma paieška ir rūšiavimas naudojant dvigubai susietus sąrašus ir žiedinius susietus sąrašus. Kaip pamatysite, šios dvi duomenų struktūros kategorijos remiasi atskirai susietais sąrašais, kad jūsų „Java“ programose būtų siūlomas didesnis paieškos ir rūšiavimo elgesio spektras.
Dvigubai susieti sąrašai
A dvigubai susietas sąrašas yra susietas mazgų sąrašas, kuriame kiekvienas mazgas turi porą nuorodų laukų. Vienas nuorodos laukas leidžia jums pereiti sąrašą į priekį, o kitas mazgas - sąrašą atgal. Kreipiantis į priekį, atskaitos kintamasis turi nuorodą į pirmąjį mazgą. Kiekvienas mazgas susieja su kitu mazgu per „kito“ nuorodos lauką, išskyrus paskutinį mazgą, kurio „kito“ saito lauke yra nulinė nuoroda, nurodanti sąrašo pabaigą (pirmyn kryptimi). Panašiai veikia ir atgalinė kryptis. Nuorodos kintamasis turi nuorodą į priekinės krypties paskutinį mazgą, kurį interpretuojate kaip pirmąjį mazgą. Kiekvienas mazgas susieja su ankstesniu mazgu per „ankstesnio“ saito lauką. Pirmojo mazgo „ankstesnio“ saito lauke yra nulis, nurodantis sąrašo pabaigą.
Pabandykite galvoti apie dvigubai susietą sąrašą kaip atskirai susietų sąrašų porą, kurių kiekviena sujungia tuos pačius mazgus. 1 paveiksle pavaizduota schema rodo į priekį- nurodoma ir viršujeGrįžtinurodomi atskirai susieti sąrašai.
CRUD operacijos dvigubai susietuose sąrašuose
Mazgų kūrimas, įterpimas ir ištrynimas yra visos įprastos operacijos dvigubai susietame sąraše. Jie panašūs į operacijas, kurias išmokote naudodami atskirai susietus sąrašus. (Atminkite, kad dvigubai susietas sąrašas yra tik pora atskirai susietų sąrašų, jungiančių tuos pačius mazgus.) Šis pseudokodas parodo mazgų sukūrimą ir įterpimą į dvigubai susietą sąrašą, parodytą 1 paveiksle. Pseudokodas taip pat parodo mazgą išbraukimas:
DECLARE CLASS mazgas DECLARE STRING vardas DECLARE mazgas kitas DECLARE mazgas prev END DECLARE DECLARE mazgas topForward DECLARE mazgo temp DECLARE mazgas topBackward topForward = NAUJAS mazgas topForward.name = "A" temp = NEW Node mazgas temp.name = "B" topBackward .name = "C" // Sukurkite pirmyn susietą sąrašą topForward.next = temp temp.next = topBackward topBackward.next = NULL // Sukurkite atgalinį atskirai susietą sąrašą topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Ištrinti mazgą B. temp.prev.next = temp.next; // Apeiti mazgą B tiesioginiame susietame sąraše. temp.next.prev = temp.prev; // Apeiti B mazgą atgaliniame atskirai susietame sąraše. GALAS Programos pavyzdys: CRUD dvigubai susietame sąraše
„Java“ programos pavyzdys „DLLDemo“ parodo, kaip sukurti, įterpti ir ištrinti mazgus dvigubai susietame sąraše. Programos šaltinio kodas rodomas 1 sąraše.
Sąrašas 1. Java programa, demonstruojanti CRUD dvigubai susietame sąraše
public final class DLLDemo {private static class Node {String name; Kitas mazgas; Mazgo prev; } public static void main (String [] args) {// Sukurkite dvigubai susietą sąrašą. Mazgas topForward = naujas mazgas (); topForward.name = "A"; Mazgo temp = naujas mazgas (); temp.pavadinimas = "B"; Mazgas topBackward = naujas mazgas (); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Persiųsti pirmyn susietą sąrašą. System.out.print ("Persiųsti atskirai susietą sąrašą:"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp. kitas; } System.out.println (); // Išmeskite atgalinį atskirai susietą sąrašą. System.out.print ("Atskirai susietas sąrašas:"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); // Pamatinis mazgas B. temp = topForward.next; // Ištrinti mazgą B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Persiųsti pirmyn susietą sąrašą. System.out.print ("Persiųsti atskirai susietą sąrašą (po ištrynimo):"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp. kitas; } System.out.println (); // Išmeskite atgalinį atskirai susietą sąrašą. System.out.print ("Atskirai susietas sąrašas (po ištrynimo):"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); }} Sudarykite 4 sąrašą taip:
javac DLLDemo.java Paleiskite gautą programą taip:
java DLLDemo Turėtumėte stebėti šį rezultatą:
Pirmyn susieti sąrašas: ABC atgalinis atskirai susietas sąrašas: CBA persiųsti vienas susietas sąrašas (po ištrynimo): AC atgalinis atskirai susietas sąrašas (po ištrynimo): CA Maišymas dvigubai susietuose sąrašuose
„Java Collections Framework“ apima: Kolekcijos klasė naudingumo metodų, kurie yra java.util pakuotė. Į šią klasę įeina a void shuffle (sąrašų sąrašas) metodas, kad "atsitiktinai perduoda nurodytą sąrašą naudodamas numatytąjį atsitiktinumo šaltinį"Pavyzdžiui, galite naudoti šį metodą, jei norite sumaišyti kortų paketą, išreikštą kaip dvigubai susietą sąrašą ( java.util.LinkedList klasė yra pavyzdys). Žemiau esančiame pseudokode galite pamatyti, kaip Maišymo algoritmas gali sumaišyti dvigubai susietą sąrašą:
PAREIŠKKITE NETINKAMĄ rnd = naują NETINKAMĄ DEKLARUOKITE INTEGERĮ i FOR i = 3 DOWNTO 2 swap (topForward, i - 1, rnd.nextInt (i)) END FUNCTION swap (Node top, int i, int j) DECLARE Node nodei, nodej DECLARE INTEGER k // Raskite i-ąjį mazgą. Mazgas nodei = top for k = 0 TO i - 1 nodei = nodei.next END FOR // Raskite j-ąjį mazgą. Mazgas nodej = top FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Atlikite apsikeitimą. DECLARE STRING namei = nodei.name DECLARE STRING namej = mazgasj.name mazgasj.name = namei nodei.name = namej PABAIGOTI FUNKCIJOS PABAIGA „Shuffle“ algoritmas gauna atsitiktinumo šaltinį ir tada pereina sąrašą atgal, nuo paskutinio mazgo iki antrojo. Jis pakartotinai keičia atsitiktinai pasirinktą mazgą (kuris iš tikrųjų yra tik pavadinimo laukas) į „dabartinę padėtį“. Mazgai yra atsitiktinai parinkti iš sąrašo dalies, einančios nuo pirmo mazgo iki esamos padėties imtinai. Atkreipkite dėmesį, kad šis algoritmas yra apytiksliai ištrauktas void shuffle (sąrašų sąrašas)šaltinio kodas.
„Shuffle“ algoritmo pseudokodas yra tingus, nes jis sutelkia dėmesį tik į pirmyn einantį atskirai susietą sąrašą. Tai pagrįstas dizaino sprendimas, tačiau mes mokame kainą už jį sudėtingai. Laiko sudėtingumas yra O (n2). Pirma, mes turime O (n) kilpa, kuri skambina sukeisti (). Antra, viduje sukeisti (), mes turime du nuoseklius O (n) kilpos. Prisiminkite šią 1 dalies taisyklę:
Jei f1(n) = O (g(n)) ir f2(n) = O (h(n)) tada) f1(n)+f2(n) = maks. (O (g(n)), O (h(n))) (b) f1(n)*f2(n) = O (g(n)*h(n)). A dalyje nagrinėjami nuoseklūs algoritmai. Čia mes turime du O (n) kilpos. Pagal taisyklę dėl to atsirandantis laiko sudėtingumas būtų O (n). B dalyje nagrinėjami įdėti algoritmai. Šiuo atveju turime O (n) padauginta iš O (n), gaunant O (n2).
Atkreipkite dėmesį, kad „Shuffle“ erdvės sudėtingumas yra O (1), atsirandantis dėl deklaruojamų pagalbinių kintamųjų.
Programos pavyzdys: Maišymas dvigubai susietame sąraše
Maišyti 2 sąrašo programa yra „Shuffle“ algoritmo demonstravimas.
Sąrašas 2. „Shuffle“ algoritmas „Java“
importuoti java.util.Random; public final class Shuffle {private static class Node {String name; Kitas mazgas; Mazgo prev; } public static void main (String [] args) {// Sukurkite dvigubai susietą sąrašą. Mazgas topForward = naujas mazgas (); topForward.name = "A"; Mazgo temp = naujas mazgas (); temp.pavadinimas = "B"; Mazgas topBackward = naujas mazgas (); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Persiųsti pirmyn susietą sąrašą. System.out.print ("Persiųsti atskirai susietą sąrašą:"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp. kitas; } System.out.println (); // Išmeskite atgalinį atskirai susietą sąrašą. System.out.print ("Atskirai susietas sąrašas atgal:"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); // Maišyti sąrašą. Atsitiktinis rnd = naujas Atsitiktinis (); už (int i = 3; i> 1; i--) sukeisti (topForward, i - 1, rnd.nextInt (i)); // Persiųsti pirmyn susietą sąrašą. System.out.print ("Pirmyn susieti sąrašas:"); temp = topForward; while (temp! = null) {System.out.print (temp.name); temp = temp. kitas; } System.out.println (); // Išmeskite atgalinį atskirai susietą sąrašą. System.out.print ("Atskirai susietas sąrašas:"); 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) {// Raskite i-ąjį mazgą. Mazgas nodei = viršuje; už (int k = 0; k <i; k ++) nodei = nodei.kitas; // Raskite j-ąjį mazgą. Mazgas nodej = viršuje; už (int k = 0; k <j; k ++) nodej = nodej. kitas; Eilutė namei = nodei.name; Eilutės pavadinimas j = mazgas.pavadinimas; nodej.name = namei; nodei.pavadinimas = vardasj; }} Sudarykite 5 sąrašą taip:
javac Shuffle.java Paleiskite gautą programą taip:
java Shuffle Turėtumėte stebėti šį vieno paleidimo rezultatą:
Pirmyn susietas sąrašas: ABC Atskirai susietas sąrašas: CBA Persiųsti atskirai susietas sąrašas: BAC Atskirai susietas sąrašas: CAB Žiediniai susieti sąrašai
Nuorodos lauke atskirai susieto sąrašo paskutiniame mazge yra nulinė nuoroda. Tai pasakytina ir apie dvigubai susietą sąrašą, kuriame yra nuorodų laukai paskutiniuose pirmyn ir atgal atskirai susietų sąrašų mazguose. Tarkime, kad paskutiniuose mazguose buvo nuorodų į pirmuosius mazgus. Šioje situacijoje jūs galų gale gautumėte a žiedinis susietas sąrašas, kuris parodytas 2 paveiksle.
Žiediniai susieti sąrašai, dar vadinami žiediniai buferiai arba žiedinės eilės, turi daugybę paskirčių. Pavyzdžiui, juos naudoja operacinės sistemos pertraukimo dorokliai, kad buferis galėtų paspausti klavišus. Daugialypės terpės programos naudoja sukamaisiais susietus sąrašus duomenims buferizuoti (pavyzdžiui, buferio duomenys įrašomi į garso plokštę). Šią techniką taip pat naudoja LZ77 duomenų praradimo be duomenų praradimo algoritmai.
Susieti sąrašai ir masyvai
Šioje duomenų struktūrų ir algoritmų serijoje mes apsvarstėme skirtingų duomenų struktūrų stipriąsias ir silpnąsias puses. Kadangi mes sutelkėme dėmesį į masyvus ir susietus sąrašus, jums gali kilti klausimų būtent apie šiuos tipus. Kokius privalumus ir trūkumus siūlo susieti sąrašai ir masyvai? Kada naudojate susietą sąrašą ir kada masyvą? Ar abiejų kategorijų duomenų struktūras galima integruoti į naudingą hibridinę duomenų struktūrą? Aš pabandysiu atsakyti į šiuos klausimus žemiau.
Susieti sąrašai siūlo šiuos privalumus, palyginti su masyvais:
- Norint palaikyti plėtrą, jiems nereikia papildomos atminties. Priešingai, masyvams reikia papildomos atminties, kai reikia išplėsti. (Kai visuose elementuose yra duomenų elementų, prie masyvo negalima pridėti naujų duomenų elementų.)
- Jie siūlo greitesnį mazgo įterpimą / ištrynimą nei lygiavertės masyvo operacijos. Nustačius įterpimo / ištrynimo poziciją, reikia atnaujinti tik nuorodas. Masyvo požiūriu, norint įterpti duomenų elementą, reikia judėti visus kitus duomenų elementus, kad būtų sukurtas tuščias elementas. Panašiai, norint ištrinti esamą duomenų elementą, reikia perkelti visus kitus duomenų elementus, kad būtų pašalintas tuščias elementas. Visam duomenų elemento judėjimui reikia laiko.
Priešingai, masyvai siūlo šiuos pranašumus, palyginti su susietais sąrašais:
- Masyvo elementai užima mažiau atminties nei mazgai, nes elementams nereikia susiejimo laukų.
- Masyvai suteikia greitesnę prieigą prie duomenų elementų per sveikaisiais rodikliais.
