Povezan seznam je linearna podatkovna struktura, v kateri elementi niso shranjeni na sosednji lokaciji, temveč so povezani s kazalci. Povezani seznam tvori vrsto povezanih vozlišč, kjer vsako vozlišče hrani podatke in naslov naslednjega vozlišča.
Struktura vozlišča: Vozlišče na povezanem seznamu je običajno sestavljeno iz dveh komponent:
podatki: Vsebuje dejansko vrednost ali podatke, povezane z vozliščem.
Naslednji kazalec: Shranjuje pomnilniški naslov (referenco) naslednjega vozlišča v zaporedju.
Glava in rep: Do povezanega seznama se dostopa prek glavnega vozlišča, ki kaže na prvo vozlišče na seznamu. Zadnje vozlišče na seznamu kaže na NULL ali nullptr, kar označuje konec seznama. To vozlišče je znano kot repno vozlišče.
Zakaj je potrebna podatkovna struktura povezanih seznamov?
Tukaj je nekaj prednosti povezanega seznama, ki je naveden spodaj. Pomagal vam bo razumeti, zakaj je to potrebno vedeti.
- Dinamična struktura podatkov: Velikost pomnilnika je mogoče dodeliti ali odstraniti med izvajanjem glede na operacijo vstavljanja ali brisanja.
- Enostavnost vstavljanja/brisanja: Vstavljanje in brisanje elementov sta enostavnejša kot nizi, saj po vstavljanju in brisanju ni treba premakniti nobenih elementov, samo naslov je treba posodobiti.
- Učinkovita uporaba pomnilnika: Kot vemo, je povezani seznam dinamična podatkovna struktura, katere velikost se poveča ali zmanjša glede na zahtevo, tako da se s tem izognemo izgubi pomnilnika.
- Izvedba: Različne napredne podatkovne strukture je mogoče implementirati z uporabo povezanega seznama, kot so sklad, čakalna vrsta, graf, zgoščeni zemljevidi itd.
primer:
V sistemu, če vzdržujemo razvrščen seznam ID-jev v matriki id[] = [1000, 1010, 1050, 2000, 2040].
Če želimo vstaviti nov ID 1005, moramo za ohranitev razvrščenega vrstnega reda premakniti vse elemente za 1000 (razen 1000).
Brisanje je drago tudi pri nizih, razen če se uporabijo kakšne posebne tehnike. Če želite na primer izbrisati 1010 v id[], je treba premakniti vse po 1010, ker je opravljenega toliko dela, kar vpliva na učinkovitost kode.
Vrste povezanih seznamov :
Obstajajo predvsem tri vrste povezanih seznamov:
- Enopovezan seznam
- Dvojno povezan seznam
- Krožni povezani seznam
1. Enopovezan seznam :
Na enojno povezanem seznamu vsako vozlišče vsebuje sklic na naslednje vozlišče v zaporedju. Prehod po enojno povezanem seznamu poteka v smeri naprej.
Enopovezan seznam
2. Dvopovezan seznam :
Na dvojno povezanem seznamu vsako vozlišče vsebuje sklice na naslednje in prejšnje vozlišče. To omogoča prečkanje tako v smeri naprej kot nazaj, vendar zahteva dodaten pomnilnik za referenco nazaj.
Dvopovezan seznam
3. Krožni povezani seznam :
Na krožnem povezanem seznamu zadnje vozlišče kaže nazaj na glavno vozlišče, kar ustvarja krožno strukturo. Lahko je enojno ali dvojno vezan.
kako centrirati sliko na css
Krožni povezani seznam
Operacije na povezanih seznamih
- Vstavljanje : Dodajanje novega vozlišča na povezani seznam vključuje prilagajanje kazalcev obstoječih vozlišč, da se ohrani pravilno zaporedje. Vstavljanje se lahko izvede na začetku, koncu ali katerem koli mestu znotraj seznama
- Izbris : Odstranjevanje vozlišča s povezanega seznama zahteva prilagajanje kazalcev sosednjih vozlišč, da se premosti vrzel, ki jo pusti izbrisano vozlišče. Brisanje lahko izvedete na začetku, koncu ali katerem koli mestu znotraj seznama.
- Iskanje : Iskanje določene vrednosti na povezanem seznamu vključuje prečkanje seznama od glavnega vozlišča, dokler vrednost ni najdena ali dokler ni dosežen konec seznama.
Analiza kompleksnosti povezanega seznama :
- Časovna zahtevnost: O(n)
- Pomožni prostor: O(n)
Prednosti povezanih seznamov
- Dinamična velikost: Povezani seznami se lahko dinamično povečajo ali zmanjšajo, saj se pomnilnik dodeljuje med izvajanjem.
- Vstavljanje in brisanje: Dodajanje ali odstranjevanje elementov s povezanega seznama je učinkovito, zlasti pri velikih seznamih.
- Prilagodljivost: Povezane sezname je mogoče preprosto reorganizirati in spreminjati, ne da bi potrebovali neprekinjen blok pomnilnika.
Slabosti povezanih seznamov
- Naključni dostop: Za razliko od nizov povezani seznami ne omogočajo neposrednega dostopa do elementov po indeksu. Za dosego določenega vozlišča je potrebno prečkanje.
- Dodatni pomnilnik: Povezani seznami zahtevajo dodaten pomnilnik za shranjevanje kazalcev v primerjavi z nizi.
Zaključek:
Povezani seznami so vsestranske podatkovne strukture, ki zagotavljajo dinamično dodeljevanje pomnilnika ter učinkovite operacije vstavljanja in brisanja. Razumevanje osnov povezanih seznamov je nujno za vsakega programerja ali navdušenca nad računalništvom. S tem znanjem lahko implementirate povezane sezname za reševanje različnih problemov in razširite svoje razumevanje podatkovnih struktur in algoritmov.