Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
Pouze tento týden sleva až 80 % na e-learning týkající se Pythonu. Zároveň využij slevovou akci až 30 % zdarma při nákupu e-learningu - Více informací.
discount 30 + hiring

Lekce 3 - Spojový seznam v Kotlin Nové

V minulé lekci, Seznam (List) pomocí pole v Kotlin, jsme se věnovali seznamům.

Dnes se v Kotlin tutoriálu zaměříme na druhý typ seznamu, kterým je spojový seznam. Jedná se o jiný typ kolekce, který funguje na zcela odlišném principu, než pole. Jeho strukturu si popíšeme a řekneme si, kdy je dobré jej využít.

Spojové seznamy

Druhou možností vytvoření seznamu s proměnným počtem prvků jsou tzv. spojové seznamy. Ty již s polem vůbec nepracují a jsou založené na odlišném principu. Jednotlivé prvky v listu jsou v paměti různě rozházené (již tedy nejsou uložené za sebou) a po sobě jdoucí prvky na sebe odkazují. Můžeme si to představit jako takový řetězec, kdy první prvek ukazuje na druhý, druhý na třetí a tak dále. Prvky z minulého příkladu bychom si ve spojovém seznamu mohli představit např. takto:

Jednosměrný spojový seznam v Kotlin

Takovému spojovému seznamu se říká jednosměrný (Singly Linked List). Pokud nemáme nějaký vážný důvod šetřit pamětí, obvykle na sebe dva po sobě jdoucí prvky ukazují navzájem (tedy i druhý na první a tak dále). Hovoříme o obousměrném spojovém seznamu (Doubly Linked List). Ten by v našem případě vypadal nějak takto:

Obousměrný spojový seznam v Javě

U spojových seznamů jsme přišli o možnost rychle přistoupit k prvku podle jeho indexu a to kvůli tomu, že prvky již nejsou v paměti za sebou. Neexistuje způsob, jak efektivně přeskočit rovnou např. na 100. prvek a přečíst jeho hodnotu. Když chceme k 100. prvku přistoupit, musíme z prvního prvku na druhý, z druhého na třetí a tak dále až do stovky. Časová složitost čtení a zápisu na index tedy záleží na počtu prvků v listu.

Někdy však nepotřebujeme prvky indexovat a v tu chvíli se tato kolekce stává velmi výhodnou. Již na začátku jsme si řekli, že s polem vůbec nepracujeme. Nejsme tedy nijak omezeni délkou seznamu a položky můžeme za běhu programu přidávat a mazat tak dlouho, dokud nám bude stačit paměť. Poměrně dobře můžeme i mazat prvky uprostřed seznamu nebo vkládat nové prvky mezi existující. U pole bylo vložení prvku možné pouze tak, že jsme všechny prvky napravo posunuli a vytvořili tak místo pro nový prvek. To nás stálo nemalý výpočetní čas, který byl závislý na počtu prvků. Ve spojovém seznamu pouze prvek naodkazujeme mezi 2 existující, ostatních prvků se změna nedotkne.

Máme tedy efektivní vkládání a mazání prvků na úkor neefektivního přístupu na indexy. Tak už to u datových struktur a algoritmů vůbec bývá, něco za něco :)

Vidíme, že spojový seznam a seznam přes pole se velmi liší. Pokud budeme často přistupovat k prvkům pomocí indexu, byl by spojový seznam katastrofou. Pokud budeme naopak prvky často vkládat nebo mazat uprostřed kolekce, spojový seznam si s tím hravě poradí a list s polem by byl extrémně pomalý.

LinkedList

Spojový seznam, stejně jako i další kolekce v Kotlinu, používá třídy Javy. V tomto případě je reprezentovaný generickou kolekcí LinkedList. Jedná se o spojový seznam obousměrný, jednosměrný spojový seznam ani v Javě nenajdeme. Mohli bychom si ho naprogramovat, ale nemá to příliš význam, jelikož se s ním hůře pracuje a úspora paměti je mizivá. Na obrázku níže je opět vidět kompletní hierarchie tříd spojového seznamu:

Hierarchie tříd spojového seznamu

LinkedList neobsahuje rovnou naše prvky, jako tomu bylo u kolekce ArrayList, ale jsou v něm uloženy položky typu Node. Jsou to uzly, které na sebe navzájem ukazují (odkazují se, chcete-li) a disponují vlastností item. Právě v té je teprve uložen náš prvek, který uzel obaluje. Dodává tak našemu prvku ony vazby na prvky okolní. Ukažme si metody, které má LinkedList oproti klasickému seznamu ArrayList navíc:

  • addFirst() - Přidá nový prvek na začátek seznamu.
  • addLast() - Přidá nový prvek na konec seznamu.
  • first() - Vrátí první prvek.
  • last() - Vrátí poslední prvek.
  • removeFirst() - Odstraní první prvek.
  • removeLast() - Odstraní poslední prvek.

Příklad

Vyzkoušejme si opět jednoduchý příklad:

val seznam = LinkedList<Int>()
seznam.add(5)
seznam.addFirst(6)
seznam.addLast(10)
println("${seznam.first()}")
println("${seznam.last()}")

Výstup programu:

6
10

Vytvoříme nový spojový seznam typu Int. První prvek přidáme standardní metodou add(). Číslo 6 přidáme metodou addFirst(), čímž se dostane na začátek seznamu. Metodou addLast() přidáme třetí prvek. Nakonec vypíšeme první a poslední prvek.

Zkusme si ještě ono rychlé vkládání a mazání prvků:

val seznam = LinkedList<Int>()
    // inicializace a naplnění spojového seznamu
    seznam.addLast(1)
    seznam.addLast(2)
    seznam.addLast(3)
    seznam.addLast(4)
    seznam.addLast(5)

    // přidávání a mazání v prostředku seznamu
    seznam.add(3, 32)
    seznam.add(3, 31)
    seznam.remove(2)

    // výpis seznamu
    for (i in seznam) {
        print("${i}, ")
    }

Výstup:

1, 2, 31, 32, 4, 5,

Po "spojáku" sáhneme hlavně v případě, kdy chceme často vkládat a mazat prvky doprostřed seznamu, což by u seznamu typu ArrayList bylo velmi pomalé.

V příští lekci, Vícerozměrná pole v Kotlin, si uděláme odbočku k vícerozměrným polím, pokud jste je náhodou při výuce přeskočili, a pak se podíváme na slovníky a množiny v Kotlin.


 

Měl jsi s čímkoli problém? Stáhni si vzorovou aplikaci níže a porovnej ji se svým projektem, chybu tak snadno najdeš.

Stáhnout

Stažením následujícího souboru souhlasíš s licenčními podmínkami

Staženo 1x (6.9 MB)
Aplikace je včetně zdrojových kódů v jazyce Kotlin

 

Předchozí článek
Seznam (List) pomocí pole v Kotlin
Všechny články v sekci
Kolekce v Kotlin
Přeskočit článek
(nedoporučujeme)
Vícerozměrná pole v Kotlin
Článek pro vás napsal Filip Studený
Avatar
Uživatelské hodnocení:
Ještě nikdo nehodnotil, buď první!
Vývoj s využitím MERN stacku, pentesting, herní vývoj v Unity a Bevy
Aktivity

 

 

Komentáře

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zatím nikdo nevložil komentář - buď první!