Lekce 3 - Spojový seznam v Kotlin

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:

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:

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. 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:

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 následujícím kvízu, Kvíz - Genericita, seznam a spojový seznam v Kotlin, si vyzkoušíme nabyté zkušenosti z předchozích lekcí.

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š.