Divkārši saistītie saraksti un to ieviešana 3. Python

Saistītie saraksti ir lineārs datu glabāšanas veids. Tas sastāv no mezgliem, kas satur datus, kā arī norādēm, kā nokļūt līdz nākamajam datu gabalam. Padomājiet par mezgliem kā ķēdes locekļiem. Katra ķēde ir atkarīga no cita, lai saglabātu stipru saiti. Ja, piemēram, vidējā saitē trūkst visa, pēc tam neizdodas. Tā vairs nav pilnīga ķēde! Kā tas tiek tulkots saistītos sarakstos? Ja trūkst kāda no norādēm vai tā ir nepareiza, pārējos datus vairs nevar nolasīt.

Nav derīga ķēde! Tas sagrautu saistīto sarakstu!

Tomēr šī raksta tēma ir saistīto sarakstu daudzpusīgākā versija - divkārši saistītais saraksts. Salīdzinot ar parasto (vai atsevišķi sasaistīto) sarakstu, divkārt saistītajā sarakstā ir vēl viens rādītājs, kuru sauc par iepriekšējo. Kā jūs varētu uzminēt, tas ļauj mezglam zināt, kur atrodas iepriekšējais mezgls. Salīdzinājumam - atsevišķi sasaistītam sarakstam atkal būtu jāpāriet viss saraksts līdz punktam, kas bija pirms tā, lai nonāktu tajā pašā punktā.

Lai iegūtu informāciju par atsevišķi savienotiem sarakstiem, lūdzu, apmeklējiet mana klasesbiedra rakstu:

Kā jau minēts iepriekš, mezgli norāda uz citām atmiņas vietām. Ko tas nozīmē? Nu atšķirībā no masīviem, kas tiek glabāti blakus esošajās vietās, saistītajiem sarakstiem vienkārši ir norādes. Zemāk redzamajā diagrammā katram atmiņas blokam (sarkans) ir divi rādītāji, kas uz to norāda. Tas piekļūst šai informācijai, aplūkojot nākamo rādītāju (melns). Ja tas vēlas atrast bloku iepriekš, tas apskatīs iepriekšējo rādītāju (balts).

Tātad, kā var ieviest divkārši saistītu sarakstu? Lūk, kā ir Python 3

Vienkārši pievienojiet .prev savai Node klasei. Tagad jūs esat gatavs sākt ieviešanu!

Priekšrocības With - ar Python 3 kodu!

Kādas ir divkārši saistīta saraksta priekšrocības salīdzinājumā ar atsevišķi savienotu sarakstu? Ar divkārt saistītu sarakstu jūs varat pārvietoties uz priekšu un atpakaļ starp mezgliem. Tas padara tādas lietas kā ievietošana patiešām vienkāršas. Izmantojot divkārt saistītus sarakstus, jūs vienkārši pārvietojaties saistītajā sarakstā uz vēlamo mezglu un pēc tam piezvanīsit uz iepriekšējo mezglu.

Trūkumi

Lai gan saistītajos sarakstos ir daudz lietu, tas nav risinājums, kas visiem beidzas. Tam, tāpat kā daudzām datu struktūrām un algoritmiem, jābūt arsenāla rīkam. Viens no trūkumiem salīdzinājumā ar atsevišķi savienotu sarakstu ir tas, ka ir vairāk atmiņas, jo katrai saitei, kas ir divkārt saistīta, ir jāseko līdzi iepriekšējam rādītājam. Turklāt ir grūti izsekot minētajam rādītājam.

Es faktiski joprojām strādāju pie to ieviešanas. Pēc šī raksta rakstīšanas (2019. gada aprīlis) šī būs mana otrā veiksmīgā ieviešana. Katra reize kļūst nedaudz vieglāka, bet man joprojām ir jāizveido diagrammas, kā iepriekšējais rādītājs mijiedarbojas ar visām citām manām funkcijām.

Bet kam tas tiks izmantots?

Es dzirdu, kā jūs jautājat. Padomājiet par jebkuru reizi, kad esat redzējis iepriekšējo un nākamo. Ir daži acīmredzami un smalki veidi, kā tos var īstenot.

Avots: https://pbs.twimg.com/media/DxzXvUKXgAAvmxx.jpg

Kā būtu ar mūzikas atskaņotāju? Tam ir ļoti skaidra nākamā un iepriekšējā poga. Divkārši saistītu sarakstu varētu izmantot, lai pārvietotos starp šīm divām dziesmām.

Vai kā ar pārlūku? Tajos ir arī skaidri norādīti veidi, kā atgriezties un pārsūtīt starp jūsu apmeklētajām Web lapām.

Tagad padomājiet par izvēlēto teksta apstrādes programmatūru vai fotoattēlu redaktoru. Ikreiz, kad pieļaujat kļūdu, varat nospiest taustiņu kombināciju CTRL (CMD operētājsistēmai Mac) + Z, lai atsauktu šo pēdējo darbību. Tāpat jūs varat pārtaisīt visu, ko esat atteicies, izmantojot CTRL (CMD operētājsistēmai Mac) + Y. Kāpēc tagad tas izklausās pazīstams? To varētu arī ieviest ar divkārši saistītu sarakstu! Iepriekšējais rādītājs norāda uz darbībām, kas tika veiktas, vienlaikus spējot arī pārtaisīt darbības, ja atsaucat pārāk daudz.

Avots: https://gfycat.com/brilliantbeautifuldassieAvots: https://www.solitairecardgames.com/how-to-play-solitaire

Ne tik acīmredzama ieviešana, par kuru domāju, bija spēle Solitaire. Uz sāniem ir pasjansa terminoloģijas attēls, lai palīdzētu parādīt manu viedokli.

Spēle ir spīdošs piemērs, kurā jums pastāvīgi jāspēj apskatīt iepriekšējās un nākamās kārtis neatkarīgi no tā, vai tās atrodas tabulā vai atkritumu kaudzē. Spēlējot karti no atkritumu kaudzes līdz tabulā, atkritumu kaudze tiek atjaunināta ar karti, kas tai bijusi pirms tam.

Dzīvākai diskusijai par divkārši saistīto sarakstu lietojumiem es ieteiktu aplūkot šo diskusiju par kaudzes plūsmu:

Tātad, nākamreiz, kad ieviešat saistīto sarakstu, kāpēc neizmēģināt divkārši saistīto sarakstu? Saistītā saraksta augšpusē nav tik daudz citu kodu, un tam ir pamatīgas priekšrocības!

Papildu resursi

Pilnu saiti uz manu divreiz saistītā saraksta Python 3 ieviešanu var atrast manā Github repo.

Ja vēlaties 3D formātā izdrukājamu divkārši saistītu sarakstu ķēdi, esmu to augšupielādējis vietnē Thingiverse.

https://www.geeksforgeeks.org/doubly-linked-list/

https://www.tutorialspoint.com/data_structures_algorithms/doubly_linked_list_algorithm.htm

https://www.youtube.com/watch?v=JdQeNxWCguQ