Prepojený zoznam je lineárna dátová štruktúra, v ktorej prvky nie sú uložené na súvislom mieste, ale sú prepojené pomocou ukazovateľov. Linked List tvorí sériu prepojených uzlov, kde každý uzol ukladá údaje a adresu nasledujúceho uzla.

Štruktúra uzla: Uzol v prepojenom zozname sa zvyčajne skladá z dvoch komponentov:
údaje: Obsahuje skutočnú hodnotu alebo údaje súvisiace s uzlom.
Ďalší ukazovateľ: Ukladá pamäťovú adresu (odkaz) ďalšieho uzla v poradí.
Hlava a chvost: Prepojený zoznam je prístupný cez hlavný uzol, ktorý ukazuje na prvý uzol v zozname. Posledný uzol v zozname ukazuje na NULL alebo nullptr, čo označuje koniec zoznamu. Tento uzol je známy ako chvostový uzol.

Prečo je potrebná dátová štruktúra prepojeného zoznamu?

Tu je niekoľko výhod prepojeného zoznamu, ktorý je uvedený nižšie, pomôže vám pochopiť, prečo je potrebné vedieť.

• Dynamická dátová štruktúra: Veľkosť pamäte môže byť pridelená alebo zrušená v čase spustenia na základe vloženia alebo vymazania operácie.
• Jednoduchosť vloženia/vymazania: Vkladanie a odstraňovanie prvkov je jednoduchšie ako polia, pretože po vložení a vymazaní nie je potrebné posúvať žiadne prvky, iba je potrebné aktualizovať adresu.
• Efektívne využitie pamäte: Ako vieme, Linked List je dynamická dátová štruktúra, ktorej veľkosť sa zvyšuje alebo zmenšuje podľa požiadavky, aby sa predišlo plytvaniu pamäťou.
• Implementácia: Rôzne pokročilé dátové štruktúry môžu byť implementované pomocou prepojeného zoznamu, ako je zásobník, front, graf, hash mapy atď.

Príklad:

Ak v systéme udržiavame zoradený zoznam ID v poli id[] = [1000, 1010, 1050, 2000, 2040].

Ak chceme vložiť nové ID 1005, tak na zachovanie zoradeného poradia musíme presunúť všetky prvky po 1000 (okrem 1000).

Odstránenie je tiež drahé s poliami, kým sa nepoužijú nejaké špeciálne techniky. Napríklad, ak chcete odstrániť 1010 v id[], všetko po 1010 sa musí presunúť, pretože sa robí toľko práce, ktorá ovplyvňuje efektivitu kódu.

Typy prepojených zoznamov :

Existujú hlavne tri typy prepojených zoznamov:

1. Jeden prepojený zoznam
2. Dvojitý prepojený zoznam
3. Kruhový prepojený zoznam

1. Jeden prepojený zoznam :

V jednoducho prepojenom zozname každý uzol obsahuje odkaz na nasledujúci uzol v poradí. Prechádzanie jednotlivo prepojeného zoznamu sa vykonáva v smere dopredu.

Jeden prepojený zoznam

2. Dvojitý zoznam :

V dvojito prepojenom zozname každý uzol obsahuje odkazy na nasledujúci aj predchádzajúci uzol. To umožňuje prechod v smere dopredu aj dozadu, ale vyžaduje si to dodatočnú pamäť pre spätnú referenciu.

Dvojitý zoznam

3. Kruhový prepojený zoznam :

V kruhovom prepojenom zozname posledný uzol ukazuje späť na hlavný uzol, čím vytvára kruhovú štruktúru. Môže byť buď jednoducho alebo dvojito prepojená.

ukážkový java kód

Kruhový prepojený zoznam

Operácie na prepojených zoznamoch

1. Vkladanie : Pridanie nového uzla do prepojeného zoznamu zahŕňa úpravu ukazovateľov existujúcich uzlov, aby sa zachovala správna postupnosť. Vloženie možno vykonať na začiatku, konci alebo na ľubovoľnej pozícii v zozname
2. Vymazanie : Odstránenie uzla z prepojeného zoznamu si vyžaduje úpravu ukazovateľov susedných uzlov, aby sa preklenula medzera po vymazanom uzle. Odstránenie je možné vykonať na začiatku, na konci alebo na ľubovoľnej pozícii v zozname.
3. Hľadá sa : Vyhľadávanie konkrétnej hodnoty v prepojenom zozname zahŕňa prechádzanie zoznamom od hlavného uzla, kým sa nenájde hodnota alebo kým sa nedosiahne koniec zoznamu.

Analýza zložitosti prepojeného zoznamu :

• Časová zložitosť: O(n)
• Pomocný priestor: O(n)

Výhody prepojených zoznamov

• Dynamická veľkosť: Prepojené zoznamy sa môžu dynamicky zväčšovať alebo zmenšovať, pretože prideľovanie pamäte sa vykonáva za behu.
• Vkladanie a mazanie: Pridávanie alebo odstraňovanie prvkov z prepojeného zoznamu je efektívne, najmä pri veľkých zoznamoch.
• Flexibilita: Prepojené zoznamy možno jednoducho reorganizovať a upravovať bez potreby súvislého bloku pamäte.

Nevýhody prepojených zoznamov

• Náhodný prístup: Na rozdiel od polí prepojené zoznamy neumožňujú priamy prístup k prvkom podľa indexu. Na dosiahnutie konkrétneho uzla je potrebný prechod.
• Prídavná pamäť: Prepojené zoznamy vyžadujú v porovnaní s poliami dodatočnú pamäť na ukladanie ukazovateľov.

Záver:

Prepojené zoznamy sú všestranné dátové štruktúry, ktoré poskytujú dynamické prideľovanie pamäte a efektívne operácie vkladania a vymazávania. Pochopenie základov prepojených zoznamov je nevyhnutné pre každého programátora alebo nadšenca informatiky. S týmito znalosťami môžete implementovať prepojené zoznamy na riešenie rôznych problémov a rozšíriť svoje chápanie dátových štruktúr a algoritmov.