Skirtumas tarp atskirai susietų ir dvigubai susietų sąrašų

„Singly Linked List“ vs „dvigubai susietų sąrašas“

Susietas sąrašas yra linijinė duomenų struktūra, naudojama duomenų rinkiniui saugoti. Susietas sąrašas atmintį atskiriems elementams skiria atskirai savo atminties bloke, o bendra struktūra gaunama susiejant šiuos elementus kaip grandinės grandis. Atskirai susietas sąrašas yra sudarytas iš mazgų sekos ir kiekvienas mazgas turi nuorodą į seką kitą mazgą. Dvigubai susietame sąraše yra mazgų seka, kurioje kiekviename mazge yra nuoroda į kitą mazgą, taip pat į ankstesnį mazgą.

Susietų sąrašas

Kiekvienas atskirai susieto sąrašo elementas turi du laukus, kaip parodyta 1 paveiksle. Duomenų lauke pateikiami faktiniai saugomi duomenys, o kitame lauke yra nuoroda į kitą elementą grandinėje. Pirmasis susieto sąrašo elementas saugomas kaip susieto sąrašo galva.

2 paveiksle pavaizduotas atskirai susietas sąrašas su trimis elementais. Kiekvienas elementas saugo savo duomenis ir visus elementus, išskyrus paskutinįjį, saugo nuorodą į kitą elementą. Paskutinis elementas kitame lauke turi nulinę vertę. Bet kurį sąrašo elementą galima pasiekti pradedant nuo galvos ir sekant kitu žymekliu, kol pasieksite reikiamą elementą.

Dvigubai susijęs sąrašas

Kiekvienas elementas dvigubai susietame sąraše turi tris laukus, kaip parodyta 3 paveiksle. Panašiai kaip atskirai susietas sąrašas, duomenų lauke yra faktiniai saugomi duomenys, o kitame lauke yra nuoroda į kitą elementą grandinėje. Be to, ankstesniame lauke yra nuoroda į ankstesnį grandinės elementą. Pirmasis susieto sąrašo elementas saugomas kaip susieto sąrašo galva.

4 paveiksle pavaizduotas dvigubai susietas sąrašas su trimis elementais. Visi tarpiniai elementai saugo nuorodas į pirmą ir ankstesnius elementus. Paskutinis sąrašo elementas kitame lauke turi nulinę vertę, o pirmasis sąrašo elementas ankstesniame lauke turi nulinę vertę. Dvigubai susietas sąrašas gali būti perkeltas į priekį, sekant sekančias kiekvieno elemento nuorodas, ir panašiai gali būti pereinamas atgal, naudojant ankstesnes kiekvieno elemento nuorodas.

Kuo skiriasi „Singly Linked List“ ir „Doublely Linked List“?

Kiekviename atskirai susieto sąrašo elemente yra nuoroda į kitą sąrašo elementą, tuo tarpu kiekviename dvigubai susieto sąrašo elemente yra nuorodos į kitą ir ankstesnį sąrašo elementą. Dvigubai susietiems sąrašams reikia daugiau vietos kiekvienam sąrašo elementui, o elementarios operacijos, tokios kaip įterpimas ir ištrynimas, yra sudėtingesnės, nes jos turi būti susijusios su dviem nuorodomis. Bet dvigubai susieti sąrašai leidžia lengviau manipuliuoti, nes tai leidžia judėti sąrašu pirmyn ir atgal.