Black Friday je tu! Využij jedinečnou příležitost a získej až 80 % znalostí navíc zdarma! Více zde
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í.
BF extended 2022

3. diel - Spojový zoznam v Kotlin Nové

Dnes sa v Kotline tutoriále zameriame na druhý typ zoznamu, ktorým je spojový zoznam. Ide o iný typ kolekcie, ktorý funguje na úplne odlišnom princípe, než pole. Jeho štruktúru si popíšeme a povieme si, kedy je dobré ho využiť.

Spojové zoznamy

Druhou možnosťou vytvorenia zoznamu s premenným počtom prvkov sú tzv. spojové zoznamy. Tie už s poľom vôbec nepracujú a sú založené na odlišnom princípe. Jednotlivé prvky v liste sú v pamäti rôzne rozhádzané (už teda nie sú uložené za sebou) a po sebe idúce prvky na seba odkazujú. Môžeme si to predstaviť ako taký reťazec, keď prvý prvok ukazuje na druhý, druhý na tretí a tak ďalej. Prvky z minulého príkladu by sme si v spojovom zozname mohli predstaviť napr. takto:

Jednosmerný spojový zoznam v Kotlin

Takému spojovému zoznamu sa hovorí jednosmerný (Singly Linked List). Pokiaľ nemáme nejaký vážny dôvod šetriť pamäťou, obvykle na seba dva po sebe idúce prvky ukazujú navzájom (teda aj druhý na prvý a tak ďalej). Hovoríme o obojsmernom spojovom zozname (Doubly Linked List). Ten by v našom prípade vyzeral nejako takto:

Obojsmerný spojový zoznam v Jave

Pri spojových zoznamoch sme prišli o možnosť rýchlo pristúpiť k prvku podľa jeho indexu a to kvôli tomu, že prvky už nie sú v pamäti za sebou. Neexistuje spôsob, ako efektívne preskočiť rovno napr. na 100. prvok a prečítať jeho hodnotu. Keď chceme k 100. prvku pristúpiť, musíme z prvého prvku na druhý, z druhého na tretí a tak ďalej až do stovky. Časová zložitosť čítania a zápisu na index teda záleží na počte prvkov v liste.

Niekedy však nepotrebujeme prvky indexovať av tej chvíli sa táto kolekcia stáva veľmi výhodnou. Už na začiatku sme si povedali, že s poľom vôbec nepracujeme. Nie sme teda nijako obmedzení dĺžkou zoznamu a položky môžeme za behu programu pridávať a mazať tak dlho, kým nám bude stačiť pamäť. Pomerne dobre môžeme aj mazať prvky uprostred zoznamu alebo vkladať nové prvky medzi existujúce. Pri pole bolo vloženie prvku možné iba tak, že sme všetky prvky napravo posunuli a vytvorili tak miesto pre nový prvok. To nás stálo nemalý výpočtový čas, ktorý bol závislý od počtu prvkov. V spojovom zozname iba prvok naodkazujeme medzi 2 existujúce, ostatných prvkov sa zmena nedotkne.

Máme teda efektívne vkladanie a mazanie prvkov na úkor neefektívneho prístupu na indexy. Tak už to u dátových štruktúr a algoritmov vôbec býva, niečo za niečo:)

Vidíme, že spojový zoznam a zoznam cez pole sa veľmi líšia. Pokiaľ budeme často pristupovať k prvkom pomocou indexu, bol by spojový zoznam katastrofou. Pokiaľ budeme naopak prvky často vkladať alebo mazať uprostred kolekcie, spojový zoznam si s tým hravo poradí a list s poľom by bol extrémne pomalý.

LinkedList

Spojový zoznam, rovnako ako aj ďalšie kolekcie v Kotline, používa triedy Javy. V tomto prípade je reprezentovaný generickou kolekciou LinkedList. Jedná sa o spojový zoznam obojsmerný, jednosmerný spojový zoznam ani v Jave nenájdeme. Mohli by sme si ho naprogramovať, ale nemá to príliš význam, pretože sa s ním horšie pracuje a úspora pamäte je mizivá. Na obrázku nižšie je opäť vidieť kompletnú hierarchiu tried spojového zoznamu:

Hierarchia tried spojového zoznamu

LinkedList neobsahuje rovno naše prvky, ako tomu bolo pri kolekcii ArrayList, ale sú v ňom uložené položky typu Node. Sú to uzly, ktoré na seba navzájom ukazujú (odkazujú sa, ak chcete) a disponujú vlastnosťou item. Práve v tej je ešte len uložený náš prvok, ktorý uzol obaľuje. Dodáva tak nášmu prvku ony väzby na prvky okolité. Ukážme si metódy, ktoré má LinkedList oproti klasickému zoznamu ArrayList navyše:

  • addFirst() - Pridá nový prvok na začiatok zoznamu.
  • addLast() - Pridá nový prvok na koniec zoznamu.
  • first() - Vráti prvý prvok.
  • last() - Vráti posledný prvok.
  • removeFirst() - Odstráni prvý prvok.
  • removeLast() - Odstráni posledný prvok.
Príklad

Vyskúšajme si opäť jednoduchý prí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

Vytvoríme nový spojový zoznam typu Int. Prvý prvok pridáme štandardnou metódou add(). Číslo 6 pridáme metódou addFirst(), čím sa dostane na začiatok zoznamu. Metódou addLast() pridáme tretí prvok. Nakoniec vypíšeme prvý a posledný prvok.

Skúsme si ešte ono rýchle vkladanie a mazanie prvkov:

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" siahneme hlavne v prípade, keď chceme často vkladať a mazať prvky doprostred zoznamu, čo by pri zozname typu ArrayList bolo veľmi pomalé.


 

Mal si s čímkoľvek problém? Stiahni si vzorovú aplikáciu nižšie a porovnaj ju so svojím projektom, chybu tak ľahko nájdeš.

Stiahnuť

Stiahnutím nasledujúceho súboru súhlasíš s licenčnými podmienkami

Stiahnuté 1x (6.9 MB)
Aplikácia je vrátane zdrojových kódov v jazyku Kotlin

 

Predchádzajúci článok
Zoznam (List) pomocou poľa v Kotlin
Všetky články v sekcii
Kolekcia v Kotlin
Preskočiť článok
(neodporúčame)
Slovníky a množiny v Kotlin
Článok pre vás napísal Filip Studený
Avatar
Užívateľské hodnotenie:
Ešte nikto nehodnotil, buď prvý!
Vývoj s využitím MERN stacku, pentesting, herní vývoj v Unity a Bevy
Aktivity

 

 

Komentáre

Avatar
Monika Havlíčková:26. septembra 12:11

Takže napríklad pri závode sa dá využiť LinkedList?

Máme 5 športovcov so štartovným číslom 1-5. V priebehu závodu sa ich poradie mení. Do ciela sa moze poradie x-krát pomeniť.

Cenu získajú prvý traja športovci. - v tomto prípade by ale bolo potrebne mať ArrayList

Alebo aky je najbeznejsí priklad z praxe na LinkedList?

 
Odpovedať
26. septembra 12:11
Avatar
DarkCoder
Člen
Avatar
Odpovedá na Monika Havlíčková
DarkCoder:26. septembra 12:58

Použití spojového seznamu pro závod samozřejmě možné je, má to své pro a proti. Nevýhodou je pomalý přístup k závodníkovi na konkrétní pozici. K němu se dostaneme po projetí všech předchozích závodníků. Lze si ale indexovat konkrétní pozice. Výhodou je snadné vymazání závodníka pokud ze závodu odstoupí a rychlý získání aktuálního pořadí.

Nejčastější využití spojového seznamu je pro implementaci datových struktur jako je fronta a zásobník. Ideální kde neznáme předem stanovený počet prvků, pro vkládání a odebírání prvků z listu.

Odpovedať
26. septembra 12:58
"Chceš-li předávat své znalosti, měj kvalitní podklady."
Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zobrazené 2 správy z 2.