Lekce 4 - Spojový seznam v Javě

V minulé lekci, Seznam (List) pomocí pole v Javě, jsme si představili seznamy (listy), detailně popsali seznam pomocí pole a třídu ArrayList.

Dnes se v Java tutoriálu zaměříme na druhý typ seznamu, kterým je spojový seznam.

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 1. 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 2 po sobě jdoucí prvky ukazují navzájem (tedy i 2. 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. Již nejsme 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 je v Javě reprezentovaný generickou kolekcí LinkedList. Jedná se o spojový seznam obousměrný, jednosměrný spojový seznam 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 ArrayListu, 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 ArrayListu navíc:

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

Příklad

Vyzkoušejme si podobný příklad jako u ArrayListu:

LinkedList<Integer> seznam = new LinkedList<>();
seznam.add(5);
seznam.addFirst(6);
seznam.addLast(10);
System.out.println(seznam.getFirst());
System.out.println(seznam.getLast());

Výstup programu:

6
10

Vytvoříme nový spojový seznam typu Integer. 1. 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 3. prvek. Nakonec vypíšeme první a poslední prvek.

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

// inicializace a naplnění spojového seznamu
LinkedList<Integer> seznam = new LinkedList<>();
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 (Integer i : seznam) {
    System.out.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 ArrayListu bylo velmi pomalé.

Dnes to bylo trochu kratší, ale nechtěl jsem začínat na konci nové téma.

V následujícím kvízu, Kvíz - Genericita, seznam a spojový seznam v Javě, 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š.