Python týden Letní akce
Pouze tento týden sleva až 80 % na kurzy Python. Lze kombinovat s akcí Letní slevy na prémiový obsah!
Brno? Vypsali jsme pro vás nové termíny školení Základů programování a OOP v Brně!

Lekce 4 - Spojový seznam v Javě

Unicorn College Tento obsah je dostupný zdarma v rámci projektu IT lidem.
Vydávání, hosting a aktualizace umožňují jeho sponzoři.

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:

Jednosměrný spojový seznam v Javě

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:

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

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 příští lekci, Vícerozměrná pole v Javě, se podíváme na vícerozměrná pole.


 

Stáhnout

Staženo 10x (836 B)
Aplikace je včetně zdrojových kódů v jazyce Java

 

 

Článek pro vás napsal Petr Štechmüller
Avatar
Jak se ti líbí článek?
3 hlasů
Autor se věnuje primárně programování v Jave, ale nebojí se ani webových technologií.
Předchozí článek
Seznam (List) pomocí pole v Javě
Všechny články v sekci
Kolekce a proudy v Javě
Miniatura
Následující článek
Vícerozměrná pole v Javě
Aktivity (3)

 

 

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í!