Lai gan atsevišķi saistītiem sarakstiem ir daudz lietojumu, tajos ir arī daži ierobežojumi. Pirmkārt, atsevišķi saistītie saraksti ierobežo mezglu šķērsošanu vienā virzienā: jūs nevarat šķērsot atsevišķi saistītu sarakstu atpakaļ, ja vien vispirms neesat mainījis tā mezglu saites, kas prasa laiku. Ja veicat reversu šķērsošanu un jums ir jāatjauno mezglu šķērsošana sākotnējā virzienā, jums būs jāatkārto inversija, kas prasa vairāk laika. Atsevišķi saistītie saraksti arī ierobežo mezglu dzēšanu. Šāda veida sarakstā nevar izdzēst patvaļīgu mezglu bez piekļuves mezgla priekšgājējam.
Par laimi Java piedāvā vairāku veidu sarakstus, kurus varat izmantot, lai meklētu un kārtotu saglabātos datus jūsu Java programmās. Šī pēdējā apmācība Datu struktūras un algoritmi sērija iepazīstina ar meklēšanu un kārtošanu, izmantojot divkārši saistītus sarakstus un apkārtrakstus. Kā redzēsit, šīs divas datu struktūras kategorijas balstās uz atsevišķi saistītiem sarakstiem, lai jūsu Java programmās piedāvātu plašāku meklēšanas un šķirošanas darbību klāstu.
Divkārši saistīti saraksti
A divkārši saistīts saraksts ir saistīts mezglu saraksts, kur katram mezglam ir pāris saišu lauku. Viens saites lauks ļauj pārvietoties sarakstā uz priekšu, bet otrs mezgls ļauj virzīties sarakstu atpakaļ. Virziena virzienam atsauces mainīgais satur atsauci uz pirmo mezglu. Katrs mezgls izveido saiti uz nākamo mezglu, izmantojot saites lauku “nākamais”, izņemot pēdējo mezglu, kura saites “nākamais” lauks satur nulles atsauci, lai apzīmētu saraksta beigas (virzienā uz priekšu). Atpakaļ virziens darbojas līdzīgi. Atsauces mainīgais satur atsauci uz virziena virziena pēdējo mezglu, kuru jūs interpretējat kā pirmo mezglu. Katrs mezgls izveido saiti uz iepriekšējo mezglu, izmantojot saites lauku “iepriekšējais”. Pirmā mezgla saites "iepriekšējais" lauks satur nulli, lai apzīmētu saraksta beigas.
Mēģiniet domāt par divkārši saistītu sarakstu kā atsevišķi saistītu sarakstu pāri, no kuriem katrs savieno vienus un tos pašus mezglus. 1. attēlā redzamā diagramma parāda topForward- atsaucas un topAtpakaļ- atsauci uz atsevišķi saistītiem sarakstiem.
CRUD operācijas divkārši saistītos sarakstos
Mezglu izveide, ievietošana un dzēšana ir visas parastās darbības divkārši saistītā sarakstā. Tās ir līdzīgas tām darbībām, kuras esat iemācījies, izmantojot sarakstus, kas saistīti ar atsevišķi. (Atcerieties, ka divkārši saistīts saraksts ir tikai pāris atsevišķi saistītu sarakstu, kas savstarpēji savieno vienus un tos pašus mezglus.) Šis pseidokods parāda mezglu izveidi un ievietošanu divkārši saistītā sarakstā, kas parādīts 1. attēlā. Pseidokods parāda arī mezglu dzēšana:
DECLARE CLASS mezgls DECLARE STRING nosaukums DECLARE mezgls nākamais DECLARE mezgls prev END DECLARE DECLARE mezgls topForward DECLARE mezgls temp DECLARE mezgls topBackward topForward = NEW Node topForward.name = "A" temp = NEW Mezgls temp.name = "B" topBackward .name = "C" // Izveidot uz priekšu atsevišķi saistītu sarakstu topForward.next = temp temp.next = topBackward topBackward.next = NULL // Izveidot atpakaļsavienotu sarakstu topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Dzēst mezglu B. temp.prev.next = temp.next; // Apiet mezglu B uz priekšu atsevišķi saistīto sarakstu. temp.next.prev = temp.prev; // Apiet Mezglu B atsevišķi saistīto sarakstu atpakaļ. BEIGT Lietojumprogrammas piemērs: CRUD divkārši saistītā sarakstā
Java lietojumprogrammas piemērs DLLDemo parāda, kā izveidot, ievietot un dzēst mezglus divkārši saistītā sarakstā. Lietojumprogrammas pirmkods ir redzams 1. sarakstā.
Saraksts 1. Java lietojumprogramma, kas demonstrē CRUD divkārši saistītā sarakstā
public final class DLLDemo {private static class Node {String name; Nākamais mezgls; Mezgls prev; } public static void main (String [] args) {// Izveidojiet divkārši saistītu sarakstu. Mezgls topForward = jauns Mezgls (); topForward.name = "A"; Mezgla temp = new Mezgls (); temp.nosaukums = "B"; Mezgls topBackward = jauns Mezgls (); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Pārvietot uz priekšu atsevišķi saistīto sarakstu. System.out.print ("Pārsūtīt atsevišķi saistītu sarakstu:"); temp = topPriekšu; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Iziet atpakaļ ar vienu saiti saistītu sarakstu. System.out.print ("Atpakaļ atsevišķi saistīts saraksts:"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); // Atsauces mezgls B. temp = topForward.next; // Dzēst mezglu B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Pārvietot uz priekšu atsevišķi saistīto sarakstu. System.out.print ("Pārsūtīt atsevišķi saistītu sarakstu (pēc dzēšanas):"); temp = topPriekšu; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Iziet atpakaļ ar vienu saiti saistītu sarakstu. System.out.print ("Atsevišķi saistīts saraksts (pēc dzēšanas):"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); }} Sastādiet 4. sarakstu šādi:
javac DLLDemo.java Palaidiet iegūto lietojumprogrammu šādi:
java DLLDemo Jums jāievēro šāda izeja:
Pārsūtīt atsevišķi saistītu sarakstu: ABC Atsevišķi saistītu sarakstu atpakaļ: CBA Pārsūtīt atsevišķi saistītu sarakstu (pēc dzēšanas): AC Atsevišķi saistītu sarakstu atpakaļ (pēc dzēšanas): CA Maiņošana divkārši saistītos sarakstos
Java kolekciju ietvars ietver a Kolekcijas klases lietderības metodes, kas ir daļa no java.util iepakojums. Šajā klasē ietilpst: void shuffle (sarakstu saraksts) metode, kas "nejauši nejaušina norādīto sarakstu, izmantojot noklusējuma nejaušības avotu"Piemēram, jūs varat izmantot šo metodi, lai sajauktu kāršu paku, kas izteikta kā divkārši saistīts saraksts ( java.util.LinkedList klase ir piemērs). Zemāk esošajā pseidokodā jūs varat redzēt, kā Jaukšanas algoritms var sajaukt divkārši saistītu sarakstu:
DECLARE RANDOM INTEGER k // Atrodiet i mezglu. Mezgls nodei = top FOR k = 0 TO i - 1 nodei = nodei.next END FOR // Atrodiet j-to mezglu. Mezgls nodej = top FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Veiciet mijmaiņu. DECLARE STRING namei = nodei.name DECLARE STRING namej = nodej.name nodej.name = namei nodei.name = namej END FUNCTION END Shuffle algoritms iegūst nejaušības avotu un pēc tam pārvietojas sarakstā atpakaļ, no pēdējā mezgla līdz otrajam. Tas atkārtoti nomaina nejauši izvēlētu mezglu (kas faktiski ir tikai nosaukuma lauks) "pašreizējā pozīcijā". Mezgli tiek nejauši izvēlēti no saraksta daļas, kas iet no pirmā mezgla līdz pašreizējai pozīcijai (ieskaitot). Ņemiet vērā, ka šis algoritms ir aptuveni izvilkts no void shuffle (sarakstu saraksts)avota kods.
Shuffle algoritma pseidokods ir slinks, jo tas koncentrējas tikai uz priekšu šķērsojošo atsevišķi saistīto sarakstu. Tas ir saprātīgs dizaina lēmums, taču mēs par to maksājam cenu sarežģītībā. Laika sarežģītība ir O (n2). Pirmkārt, mums ir O (n) cilpa, kas zvana apmainīt (). Otrkārt, iekšienē apmainīt (), mums ir divi secīgi O (n) cilpas. Atgādiniet šādu 1. daļas noteikumu:
Ja f1(n) = O (g(n)) un f2(n) = O (h(n)), tad (a) f1(n)+f2(n) = max (O (g(n)), O (h(n))) (b) f1(n)*f2(n) = O (g(n)*h(n)). (A) daļa attiecas uz secīgiem algoritmiem. Lūk, mums ir divi O (n) cilpas. Saskaņā ar noteikumu laika sarežģītība būtu O (n). B daļā aplūkoti ligzdoti algoritmi. Šajā gadījumā mums ir O (n) reizināts ar O (n), kā rezultātā rodas O (n2).
Ņemiet vērā, ka Shuffle telpas sarežģītība ir O (1), kas izriet no deklarētajiem palīgu mainīgajiem.
Lietojumprogrammas piemērs: sajaukšana divkārši saistītā sarakstā
The Jaukt 2. saraksta lietojumprogramma ir Shuffle algoritma demonstrācija.
Saraksts 2. Shuffle algoritms Java
importēt java.util.Random; public final class Shuffle {private static class Mezgls {Stīgas nosaukums; Nākamais mezgls; Mezgls prev; } public static void main (String [] args) {// Izveidojiet divkārši saistītu sarakstu. Mezgls topForward = jauns Mezgls (); topForward.name = "A"; Mezgla temp = new Mezgls (); temp.nosaukums = "B"; Mezgls topBackward = jauns Mezgls (); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Pārvietot uz priekšu atsevišķi saistīto sarakstu. System.out.print ("Pārsūtīt atsevišķi saistītu sarakstu:"); temp = topPriekšu; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Iziet atpakaļ ar vienu saiti saistītu sarakstu. System.out.print ("Atsevišķi saistītu sarakstu atpakaļ:"); temp = topBackward; while (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); // Jaukt sarakstu. Random rnd = jauns Random (); par (int i = 3; i> 1; i--) mijmaiņas (topForward, i - 1, rnd.nextInt (i)); // Pārvietot uz priekšu atsevišķi saistīto sarakstu. System.out.print ("Pārsūtīt atsevišķi saistītu sarakstu:"); temp = topPriekšu; while (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Dump atpakaļ atpakaļ atsevišķi saistītu sarakstu. System.out.print ("Atpakaļ atsevišķi saistīts saraksts:"); 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) {// Atrodiet i mezglu. Mezgls nodei = top; par (int k = 0; k <i; k ++) nodei = nodei.nākamais; // Atrodiet j-to mezglu. Mezgls nodej = augšdaļa; par (int k = 0; k <j; k ++) nodej = nodej.nākamais; Virkne namei = nodei.name; Virknes nosaukums j = mezgla nosaukums. nodej.name = namei; nodei.name = namej; }} Sastādiet 5. sarakstu šādi:
javac Shuffle.java Palaidiet iegūto lietojumprogrammu šādi:
java Shuffle Jums jāievēro šāda izlaide vienā braucienā:
Pārsūtīt uz priekšu atsevišķi saistīto sarakstu: ABC Atpakaļ atsevišķi saistīto sarakstu: CBA Pārsūtīt atsevišķi saistīto sarakstu: BAC Atsevišķi saistīto sarakstu atpakaļ: CAB Cirkulārie saistītie saraksti
Atsevišķi saistītā saraksta pēdējā mezgla saites laukā ir saite ar nulli. Tas attiecas arī uz divkārši saistītu sarakstu, kurā ir saites lauki uz priekšu un atpakaļ atsevišķi saistītu sarakstu pēdējos mezglos. Pieņemsim, ka tā vietā pēdējie mezgli saturēja saites uz pirmajiem mezgliem. Šajā situācijā jūs nonāktu pie cirkulāri saistīts saraksts, kas parādīts 2. attēlā.
Cirkulāri saistīti saraksti, kas pazīstami arī kā apļveida buferi vai apļveida rindas, ir daudz lietojumu. Piemēram, tos izmanto operētājsistēmas pārtraukumu apstrādātāji, lai buferētu taustiņsitienus. Multivides lietojumprogrammās tiek izmantoti apļveida saraksti, lai buferētu datus (piemēram, skaņas kartē tiek ierakstīti buferizācijas dati). Šo paņēmienu izmanto arī datu nesaspiešanas algoritmu LZ77 saime.
Saistītie saraksti pret masīviem
Šajā datu struktūru un algoritmu sērijā mēs esam apsvēruši dažādu datu struktūru stiprās un vājās puses. Tā kā mēs esam koncentrējušies uz masīviem un saistītajiem sarakstiem, jums varētu būt jautājumi tieši par šiem veidiem. Kādas priekšrocības un trūkumus piedāvā saistītie saraksti un masīvi? Kad jūs izmantojat saistīto sarakstu un kad jūs izmantojat masīvu? Vai abu kategoriju datu struktūras var integrēt noderīgā hibrīdā datu struktūrā? Es centīšos atbildēt uz šiem jautājumiem zemāk.
Saistītie saraksti piedāvā šādas priekšrocības salīdzinājumā ar masīviem:
- Lai atbalstītu paplašināšanu, tiem nav nepieciešama papildu atmiņa. Turpretī masīviem ir nepieciešama papildu atmiņa, ja ir nepieciešama paplašināšana. (Kad visi elementi satur datu vienumus, masīvam nevar pievienot jaunus datu vienumus.)
- Tie piedāvā ātrāku mezglu ievietošanu / dzēšanu nekā līdzvērtīgas ar masīvu saistītas darbības. Pēc ievietošanas / dzēšanas pozīcijas noteikšanas ir jāatjaunina tikai saites. No masīva viedokļa datu vienumu ievietošanai ir nepieciešama visu pārējo datu vienumu pārvietošana, lai izveidotu tukšu elementu. Līdzīgi, lai dzēstu esošu datu vienumu, ir jāpārvieto visi pārējie datu vienumi, lai noņemtu tukšu elementu. Visu datu vienumu pārvietošana prasa laiku.
Turpretī masīvi piedāvā šādas priekšrocības salīdzinājumā ar saistītajiem sarakstiem:
- Masīva elementi aizņem mazāk atmiņas nekā mezgli, jo elementiem nav nepieciešami saites lauki.
- Masīvi piedāvā ātrāku piekļuvi datu vienumiem, izmantojot uz veseliem skaitļiem balstītus indeksus.
