Lekce 2 - Seznam (List) pomocí pole v Kotlin

V minulé lekci, Úvod do kolekcí a genericita v Kotlin, jsme si udělali úvod do kolekcí a ukázali jsme si, co je to genericita.

Dnes se budeme v Kotlin tutoriálu věnovat seznamům (listům).

Pole

Udělejme si na začátku malou odbočku zpět k poli, které bylo první kolekcí, kterou jsme v kurzu poznali. Pole se vyznačuje tím, že má pevně daný počet prvků, který nemůžeme nikdy změnit. Pokud do již existujícího pole chceme něco přidat, musíme vytvořit nové. Z tohoto důvodu pole někdy dokonce nebývá považováno ani za kolekci. Ukažme si příklad:

val pole = arrayOf(1, 2, 3)
val pole2 = pole + 4 // pole2 je již nová instance a nemá vůbec nic společného s proměnnou pole
println(pole.size) // velikost původního pole je stále 3, protože nemůžeme změnit velikost aktuální instance

Jak si můžeme všimnout, Kotlin omezení způsobené neměnnou délkou pole chytře obchazí přes imutabilní třídu, která obaluje pole z JVM. Prvky v poli jsou číselně indexovány a to od nuly.

Jelikož data jsou stejného typu (ať již úplně stejného, nebo společného předka), zabírají v paměti stejně místa. Jednotlivé prvky pole jsou v paměti uložené za sebou, jako v řadě, která je nepřerušená. Pole celých čísel si můžeme představit např. takto:

Pokud tedy chceme např. přistoupit na 5. prvek, jen vstoupíme tam, kde pole začíná a poté odskočíme 4 násobky velikosti typu (zde Intu) dále. Jsme na 5. prvku. Čtení a zápis na indexy v poli má tedy konstantní časovou složitost. Pokud vás tento termín zmátl, můžete to chápat tak, že do pole zapisujeme okamžitě a stejně tak z něj i čteme.

Hlavní nevýhodou pole tedy je, že do něj nemůžeme za běhu aplikace prvky přidávat nebo je mazat. To, bohužel, často potřebujeme. Představme si vyrábět pořád nové instance pole (tedy jeho kopie) o více než 1000 prvcích, program by se nám mohl radikálně zpomalit.

Seznamy (listy)

Seznamy (anglicky a často i česky listy) jsou kolekce, které umožňují prvky za běhu programu přidávat a mazat. Mohou být číselně indexované jako pole, ale také nemusí. Jsou v zásadě 2 typy seznamů: Seznamy s polem a spojové seznamy. Spojové seznamy Kotlin nepodporuje a v případě potřeby bychom se museli obrátit na standardní javovské kolekce.

Seznamy s polem

Seznam nejčastěji využívá toho, že ačkoli velikost pole nemůžeme za běhu programu měnit, můžeme za běhu vytvořit pole nové.

Seznam je poté třída, která obsahuje na rozdíl od pole metody pro přidání a navíc odstranění prvků (a mnoho dalších, pro nás nyní nepodstatných metod). Třída v podstatě obaluje pole a obsahuje navíc proměnnou, kde si uchovává počet prvků. Při vytvoření instance se vytvoří pole např. o 12ti prvcích a proměnná s počtem prvků se nastaví na 0. Při přidání prvního prvku se prvek vloží na 1. index v poli a počet prvků se inkrementuje. Takto můžeme přidat až 12 prvků, než pole naplníme. Ve chvíli, kdy vyčerpáme kapacitu pole, jednoduše vytvoříme nové, třeba 2x větší. Prvky ze starého pole do něj zkopírujeme a staré pole zahodíme. Až se toto nové pole opět naplní, budeme situaci opakovat. Takovýmto způsobem opravdu interně funguje Kotlin kolekce ArrayList, se kterou jsme se doteď nesetkali. ArrayList s polem si můžeme představit asi takto:

ArrayList na obrázku má 8 prvků. Prvky jsou uloženy v interním poli, které má prvků 12. Poslední 4 prvky se nevyužívají a ArrayList se zvenku tváří jako že tam nejsou.

Výhodou je rychlost přístupu k prvkům pomocí indexů díky využití pole. Nevýhodou je samozřejmě časová prodleva nutná k vytvoření nového pole a překopírování prvků, i když nastává jen občas na rozdíl od klasického pole v Kotlinu. Další, i když méně bolestivou nevýhodou, je, že kolekce zabírá v paměti více prostoru, než je nutné. Tento typ seznamu je přesto nejpoužívanější kolekcí v Javě a je poměrně dobře optimalizován.

List s polem je tedy v Kotlinu zastoupen třídou ArrayList. Ukažme si jak založit ArrayList a následně si popišme důležité metody na třídě ArrayList:

Inicializaci kolekce můžeme provést následovně:

val array = arrayListOf(1, 2, 3)

Nebo můžeme také použít:

val array = mutableListOf(1, 2, 3)

Kolekce ArrayList v Kotlinu je totožná s tou v Javě. Kotlin ji využívá.

Metody a další prvky na třídě ArrayList

Javovský ArrayList implementuje interface List. Kotlin sice používá javovský ArrayList, ale přidává si i vlastní metody, které se wrapují okolo toho javovského ArrayListu, aby více připomínal kolekci v Kotlinu. Základní metody tedy jsou:

• clear() - Odstraní všechny prvky.
• contains() - Vrátí true, pokud list obsahuje daný prvek.
• size - Vrátí počet prvků v listu.
• get() nebo [] - Vrátí prvek na dané pozici.
• add() nebo += - Přidá nový prvek na konec listu nebo na daný index vloží nový prvek (a další prvky posune).
• remove() nebo -= - Odstraní daný prvek. Tato funkce je velmi užitečná v případě, že máme v ArrayListu instance nějaké třídy (např. uživatele), nemusíme si držet jejich číselné indexy, jen zavoláme např. list.remove(karel).
• removeAt() - Odstraní prvek na daném indexu.

Ačkoli to může být matoucí, tak -= a += nevrací novou instanci ArrayListu.

List

Můžeme také použít listOf(), který je imutabilní a v Kotlinu se často používá. Po každém přidání nebo odebrání vrátí novou instanci. Protože by metody jako add(), které vracejí Unit (nic), nedávaly příliš smysl na kolekci, která je neměnná, již je tu nenalezneme. Přetížené operátory ovšem dostupné máme (+=, -=) a vracejí vždy novou instanci.

Kdy použít List a kdy ArrayList?

ArrayList a List jsou tedy oba seznamy a můžeme použít oba k tomu samému účelu. Čím se tedy liší? Jak jsem již zmiňoval, proměnná typu List je immutabilní (neměnná) a jakákoli operace s ní vytvoří vždy novou instanci seznamu. Na druhou stranu ArrayList měnit lze. Představme si, že máme nějakou 2d hru, která má hrací pole reprezentováno 2d polem (např. nějaké šachy nebo piškvorky). Pro tento případ je výhodnější použít ArrayList, protože je zbytečné vytvářet stále nové instance naší kolekce, když např. změníme pouze jeden objekt v ní. Kdybychom posunuli pěšce o políčko dopředu a kvůli tomu bychom vytvořili úplně nové "pole", není to zbytečné?

ArrayList má ale také své nevýhody, například z něj nemůžeme nijak jednoduše mazat, když jím iterujeme. To je proto, že mažeme rovnou na té instanci, kterou iterujeme.

Většinou se používá List, pokud jej potřebujete však často měnit, je dobré zvážit užití ArrayListu. Kvůli chybějící immutabilitě můžete však narazit na problémy, pokud pracujete s vlákny.

Příklad

Ačkoli jsme si práci s metodami na Arrayi vyzkoušeli již 1000krát a práce s ArrayListem není v podstatě nijak odlišná, pro úplnost si přeci jen ukažme několik řádků kódu:

val array = arrayListOf<Int>(1)
array += 2
array -= 1 // Můžeme mazat!
println(array)

Výstup programu:

[2]

Kód výše vytvoří ArrayList typu Int s prvkem 1, přidá do něj prvek 2 a následně prvek 1 odstraní. Výsledný seznam se vypíše do konzole. S indexy pracujeme jako bychom pracovali s polem, ale můžeme do něj za běhu programu přidávat prvky a také je mazat na stejné instanci.

Samotný ArrayList ještě dodává další metody, popišme si i ty:

• addAll() nebo += - Přidá do listu prvky z předaného pole. Podobně můžeme volat i metody removeRange() nebo -=. Je dobrý nápad metodu využívat, jelikož nám ušetří cyklus.
• toTypedArray() - Vrátí instanci Array, ze kterého lze prvky pouze číst. Vhodné pro zapouzdření prvků kolekce.
• size - Vlastnost nesoucí počet prvků v listu.
• lastIndexOf() - Obdoba metody indexOf(), vrací index posledního výskytu daného prvku v listu.
• removeAll() - Odstraní všechny prvky, které se předaly v argumentu v poli.
• reverse() - Převrátí list tak, aby byl 1. prvek jako poslední a naopak poslední jako první.
• sort() - Setřídí list. Je důležité, aby jeho prvky obsahovaly rozhraní Comparable, jinak metoda vyvolá výjimku. Základní třídy a struktury z Kotlinu Comparable implementují, u svých tříd ho umíme dodat.

Přidávat rozsah můžeme i operátorem +=:

array += (1..5)

Toto nám zatím bude stačit. Až si vysvětlíme lambda funkce, tak si ukážeme další metody jako filter() nebo map().

Vyzkoušejte si další metody jako sort(), vyhledávání a podobně. Detailnější práci s kolekcemi se budeme ještě věnovat.

V příští lekci, Spojový seznam v Kotlin, se podíváme na spojové seznamy. Popíšeme si, jak fungují a jaké metody jejich implementace nabízí.

 

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