Susietas sąrašas yra linijinė duomenų struktūra, kurioje elementai nėra saugomi gretimoje vietoje, o yra susieti naudojant rodykles. Susietasis sąrašas sudaro sujungtų mazgų seriją, kur kiekvienas mazgas saugo duomenis ir kito mazgo adresą.
Mazgo struktūra: Mazgas susietame sąraše paprastai susideda iš dviejų komponentų:
Duomenys: Jame yra tikroji vertė arba duomenys, susieti su mazgu.
Kitas rodyklė: Jis išsaugo kito sekos mazgo atminties adresą (nuorodą).
Galva ir uodega: Susietas sąrašas pasiekiamas per pagrindinį mazgą, kuris nurodo pirmąjį sąrašo mazgą. Paskutinis sąrašo mazgas nurodo NULL arba nullptr, nurodant sąrašo pabaigą. Šis mazgas yra žinomas kaip uodegos mazgas.
Kodėl reikalinga susieto sąrašo duomenų struktūra?
Toliau pateikiami keli susieto sąrašo privalumai, kurie padės suprasti, kodėl tai būtina žinoti.
- Dinaminė duomenų struktūra: Atminties dydis gali būti paskirstytas arba panaikintas vykdymo metu, atsižvelgiant į operacijos įterpimą arba ištrynimą.
- Lengvas įterpimas / ištrynimas: Elementų įterpimas ir ištrynimas yra paprastesnis nei masyvų, nes po įterpimo ir ištrynimo elementų nereikia perkelti, reikia atnaujinti tik adresą.
- Efektyvus atminties naudojimas: Kaip žinome, susietasis sąrašas yra dinamiška duomenų struktūra, kurios dydis didėja arba mažėja pagal poreikį, todėl išvengiama atminties eikvojimo.
- Įgyvendinimas: Įvairios išplėstinės duomenų struktūros gali būti įdiegtos naudojant susietą sąrašą, pvz., krūvą, eilę, diagramą, maišos žemėlapius ir kt.
Pavyzdys:
Sistemoje, jei mes palaikome surūšiuotą ID sąrašą masyve id [] = [1000, 1010, 1050, 2000, 2040].
Jei norime įterpti naują ID 1005, tai norėdami išlaikyti rūšiavimo tvarką, turime perkelti visus elementus po 1000 (išskyrus 1000).
Ištrynimas taip pat yra brangus naudojant masyvus, kol nebus naudojami specialūs metodai. Pavyzdžiui, norint ištrinti 1010 id[], viskas po 1010 turi būti perkelta, nes atliekama tiek daug darbo, o tai turi įtakos kodo efektyvumui.
Susietų sąrašų tipai :
Iš esmės yra trijų tipų susieti sąrašai:
- Sąrašas su viena nuoroda
- Dvigubai susietas sąrašas
- Aplinkinis susietas sąrašas
1. Sąrašas su viena nuoroda :
Atskirai susietame sąraše kiekviename mazge yra nuoroda į kitą sekos mazgą. Atskirai susietu sąrašu einama pirmyn.
Sąrašas su viena nuoroda
2. Dvigubai susietas sąrašas :
Dvigubai susietame sąraše kiekviename mazge yra nuorodos ir į kitą, ir į ankstesnį mazgus. Tai leidžia važiuoti tiek pirmyn, tiek atgal, tačiau reikia papildomos atminties atskaitai atgal.
Dvigubai susietas sąrašas
3. Aplinkinis susietas sąrašas :
Apskritame susietame sąraše paskutinis mazgas nukreipiamas atgal į pagrindinį mazgą, sukuriant apskritą struktūrą. Jis gali būti susietas atskirai arba dvigubai.
apibrėžti kompiuterį
Aplinkinis susietas sąrašas
Operacijos susietuose sąrašuose
- Įdėjimas : Naujo mazgo įtraukimas į susietą sąrašą apima esamų mazgų rodyklių koregavimą, kad būtų išlaikyta tinkama seka. Įterpimas gali būti atliekamas pradžioje, pabaigoje arba bet kurioje sąrašo vietoje
- Ištrynimas : Norint pašalinti mazgą iš susieto sąrašo, reikia pakoreguoti gretimų mazgų rodykles, kad būtų užpildytas ištrinto mazgo paliktas tarpas. Ištrinti galima pradžioje, pabaigoje arba bet kurioje sąrašo vietoje.
- Ieškoma : Konkrečios reikšmės paieška susietame sąraše apima sąrašo judėjimą nuo pagrindinio mazgo, kol randama reikšmė arba pasiekiama sąrašo pabaiga.
Susieto sąrašo sudėtingumo analizė :
- Laiko sudėtingumas: O(n)
- Pagalbinė erdvė: O(n)
Susietų sąrašų pranašumai
- Dinaminis dydis: Susieti sąrašai gali dinamiškai augti arba mažėti, nes atmintis paskirstoma vykdymo metu.
- Įterpimas ir ištrynimas: Elementų pridėjimas arba pašalinimas iš susieto sąrašo yra efektyvus, ypač dideliems sąrašams.
- Lankstumas: Susietus sąrašus galima lengvai pertvarkyti ir modifikuoti nereikalaujant gretimo atminties bloko.
Susietų sąrašų trūkumai
- Atsitiktinė prieiga: Skirtingai nuo masyvų, susieti sąrašai neleidžia tiesiogiai pasiekti elementų pagal indeksą. Norint pasiekti konkretų mazgą, reikia pereiti.
- Papildoma atmintis: Susietiems sąrašams, palyginti su masyvais, reikia papildomos atminties rodyklėms saugoti.
Išvada:
Susieti sąrašai yra universalios duomenų struktūros, užtikrinančios dinamišką atminties paskirstymą ir efektyvias įterpimo bei ištrynimo operacijas. Bet kuriam programuotojui ar informatikos entuziastui būtina suprasti susietų sąrašų pagrindus. Turėdami šias žinias, galite įdiegti susietus sąrašus, kad išspręstumėte įvairias problemas ir praplėstumėte supratimą apie duomenų struktūras ir algoritmus.