Spojový seznam je lineární datová struktura, ve které prvky nejsou uloženy na souvislém místě, ale jsou propojeny pomocí ukazatelů. Linked List tvoří řadu propojených uzlů, kde každý uzel ukládá data a adresu dalšího uzlu.
Struktura uzlu: Uzel v propojeném seznamu se obvykle skládá ze dvou součástí:
Data: Obsahuje skutečnou hodnotu nebo data spojená s uzlem.
Další ukazatel: Ukládá paměťovou adresu (odkaz) dalšího uzlu v pořadí.
Hlava a ocas: Propojený seznam je přístupný přes hlavní uzel, který ukazuje na první uzel v seznamu. Poslední uzel v seznamu ukazuje na NULL nebo nullptr, což označuje konec seznamu. Tento uzel je známý jako ocasní uzel.
Proč je potřeba datová struktura propojeného seznamu?
Zde je několik výhod propojeného seznamu, který je uveden níže, pomůže vám pochopit, proč je to nutné vědět.
- Dynamická datová struktura: Velikost paměti lze alokovat nebo zrušit za běhu na základě vložení nebo odstranění operace.
- Snadné vložení/vymazání: Vkládání a mazání prvků je jednodušší než pole, protože po vložení a mazání není třeba posouvat žádné prvky, pouze je třeba aktualizovat adresu.
- Efektivní využití paměti: Jak víme, Linked List je dynamická datová struktura, jejíž velikost se zvětšuje nebo zmenšuje podle požadavku, takže nedochází k plýtvání pamětí.
- Implementace: Pomocí propojeného seznamu lze implementovat různé pokročilé datové struktury, jako je zásobník, fronta, graf, hash mapy atd.
Příklad:
V systému, pokud udržujeme seřazený seznam ID v poli id[] = [1000, 1010, 1050, 2000, 2040].
Pokud chceme vložit nové ID 1005, pak pro zachování setříděného pořadí musíme přesunout všechny prvky po 1000 (kromě 1000).
Mazání je také drahé u polí, dokud nejsou použity nějaké speciální techniky. Chcete-li například odstranit 1010 v id[], vše po 1010 musí být přesunuto, protože se dělá tolik práce, která ovlivňuje efektivitu kódu.
Typy propojených seznamů :
Existují především tři typy propojených seznamů:
- Jeden propojený seznam
- Dvojitě propojený seznam
- Kruhový propojený seznam
1. Jeden propojený seznam :
V jednoduše propojeném seznamu obsahuje každý uzel odkaz na další uzel v pořadí. Procházení jednotlivě propojeného seznamu se provádí v dopředném směru.
Jeden propojený seznam
2. Dvojitě propojený seznam :
Ve dvojitě propojeném seznamu obsahuje každý uzel odkazy na další i předchozí uzel. To umožňuje procházení v obou směrech vpřed i vzad, ale vyžaduje to další paměť pro zpětnou referenci.
Dvojitě propojený seznam
3. Kruhový propojený seznam :
V kruhovém propojeném seznamu ukazuje poslední uzel zpět na hlavní uzel a vytváří kruhovou strukturu. Může být buď jednoduše, nebo dvojitě propojený.
co je regex java
Kruhový propojený seznam
Operace na propojených seznamech
- Vložení : Přidání nového uzlu do propojeného seznamu zahrnuje úpravu ukazatelů existujících uzlů, aby byla zachována správná sekvence. Vložení lze provést na začátek, konec nebo na kteroukoli pozici v seznamu
- Vymazání : Odebrání uzlu z propojeného seznamu vyžaduje úpravu ukazatelů sousedních uzlů, aby se překlenula mezera po odstraněném uzlu. Smazání lze provést na začátku, na konci nebo na libovolné pozici v seznamu.
- Hledání : Hledání konkrétní hodnoty v propojeném seznamu zahrnuje procházení seznamu od hlavního uzlu, dokud není hodnota nalezena nebo dokud není dosaženo konce seznamu.
Analýza komplexnosti propojeného seznamu :
- Časová složitost: O(n)
- Pomocný prostor: O(n)
Výhody propojených seznamů
- Dynamická velikost: Propojené seznamy se mohou dynamicky zvětšovat nebo zmenšovat, protože alokace paměti se provádí za běhu.
- Vkládání a mazání: Přidávání nebo odebírání prvků z propojeného seznamu je efektivní, zejména u velkých seznamů.
- Flexibilita: Propojené seznamy lze snadno reorganizovat a upravovat bez nutnosti souvislého bloku paměti.
Nevýhody propojených seznamů
- Náhodný přístup: Na rozdíl od polí propojené seznamy neumožňují přímý přístup k prvkům podle indexu. Pro dosažení konkrétního uzlu je vyžadováno procházení.
- Paměť navíc: Propojené seznamy vyžadují ve srovnání s poli další paměť pro ukládání ukazatelů.
Závěr:
Propojené seznamy jsou všestranné datové struktury, které poskytují dynamické přidělování paměti a efektivní operace vkládání a mazání. Pochopení základů propojených seznamů je nezbytné pro každého programátora nebo nadšence do informatiky. S těmito znalostmi můžete implementovat propojené seznamy k řešení různých problémů a rozšířit své znalosti datových struktur a algoritmů.