Dátové štruktúry poľa a list

Dnes si preberieme tie najzákladnejšie dátové štruktúry, pole a zoznam (list). Obe slúži k ukladaniu prvkov pomocou číselných indexov. V čom sa teda tieto 2 fundamentálnej štruktúry líši a na čo ich používať?

Poľa

Pole (anglicky array) je dátová štruktúra, s ktorou sa stretnete snáď vo všetkých programovacích jazykoch. Vzniklo z túžby mať okrem položiek aj možnosť reprezentovať vektory. Prvky polia môžu byť tiež polia. Majme napr. Kocku, ktorá má vrcholy v [0,0,0], [0,0,1], [0,1,0], [1,0,0], [1,0,1], [1,1,0] a [1,1,1]. V poli môže byť skrátka čokoľvek, čo dokážeme nejako reprezentovať. Napríklad String nie je nič iné, než pole znakov (char ov). Preto možno String tak dobre indexovať. Dokonca aj celý adresný priestor je jedno veľké pole s indexovaním pomocou adresy premennej.

Ako sa s poľom pracuje?

Pole je v podstate hromada krabíc poskladaných vedľa seba a na to očíslovaných prirodzenými číslami. Je dobrým zvykom číslovať od nuly. Síce sú v dnešných kapacitách pamäti nejaké 2 bajty ako úspora pamäte málo, ale sprehľadní to váš kód. Pole je statická dátová štruktúra, čo znamená, že má pevne danú dĺžku.

Na poli vykonávame tieto operácie:

• vypiše pole
• vlož prvok
• zmaž prvok
• vyhľadaj prvok
• zmeň prvok
• Spočítajte prvky

Inicializácia poľa

Tento krok sa líši jazyk od jazyka. Pole je statická dátová štruktúra, takže musíme vykonať jeho inicializácii, kedy pevne určíme počet prvkov a ich dátový typ.

Niektoré programovacie jazyky, napr. PHP alebo JavaScript, implementovali svoje polia ako zoznamy alebo dokonca slovníky. Týmto faktom sa nenecháme zmiasť a pojem polia budeme chápať z algoritmizačního hľadiska ako statickú štruktúru niekoľkých číselne indexovaných prvkov.

Ukážme si ako môže vyzerať inicializácia poľa:

int [] array_of_integers = new int [100];

Táto inicializácia by mala byť dostatočne široká, aby ste ju mohli použiť vo vašich jazykoch. Na začiatku je potrebné povedať, čoho je to vlastne pole. Teraz sme si zaviedli poľa Integer, mohli by sme si však vymyslieť svoju vlastnú triedu, treba class Teacher { ... } a mať pole učiteľov:

Teacher [] array_of_teachers = new Teacher [100];

Ak sa inicializuje pole hodnotových typov, tj. int, float atď ..., majú väčšinou implicitne tieto hodnoty:

• int = 0
• String = ""
• float = 0.0f
• boolean = false

Vypiše pole

Toto je klasické použitie pole ako štruktúry pre uchovávanie dát. Kód nižšie vypisuje všetky položky poľa pole pomocou cyklu for:

for (i = 0; i <  100; i++ ) {
    System.out.println("Na pozici [" + i + "] je " + pole[i]);
}

Čo sa týka zložitosti, je jasné, že musíme prejsť celé pole, aby sme vypísali každý prvok. Časová zložitosť operácie je teda O(n).

Vlož prvok / uprav prvok

Táto operácia môže byť vykonaná pomocou priameho indexovanie, alebo vloženie prvku na koniec priestoru poľa, ktorý práve využívame (pole si môžeme vytvoriť väčšie ako potrebujeme a nemusí byť vždy úplne plné). Ak budeme vkladať prvok na koniec takého poľa, je potrebné ho prejsť celé, prípadne mať vedľa uloženú premennú značiace kam až nám prvky momentálne siahajú. V prvom prípade je zložitosť O(n), pretože sa nám môže stať, že musíme prejsť celé pole.

Pokiaľ vieme koľko prvkov máme momentálne obsadených, vložíme prvok na koniec poľa v čase O(1), teda konštantným.

A ak chceme upraviť prvok na konkrétnom indexu, zvládneme to priamo v O(1):

array[i] = nejaky_prvek;

Vyhľadaj prvok

Pre pole dĺžky n musíme prehľadať najhoršie celé pole, tj. n prvkov. Preto je zložitosť tejto operácie O(n). Ukážme si opäť zdrojový kód:

int searched_item = nejaky_prvek;

for (int i = 0; i < n; i++) {
    if (array[i] == searched_item ) {
        System.out.println("Prvek " + searched_item + " nalezen na pozici ["+ i + "].");
        break;
    }
}
if (i == n)
    System.out.println(i + " nenalezen.");

Zmaž prvok

Ak by sme mali pole kladných čísel, mohli by sme prvok zmazať tak, že by sme jeho hodnotu nastavili na 0. To by trvalo v O(1). Ak by sme chceli pole aj zmenšiť, táto operácia by trvala v O(n), pretože sa prvky za zmazaným prvkom musí posunúť o jednu pozíciu doľava a zaplniť tak "dieru", ktorá v poli vznikla:

for( int i = index_smazaneho_prvku; i < n - 1; i++) {
    array[i] = array[i+1];
}

Zoraď prvky

Na zoradenie prvkov v poli môžeme použiť algoritmy v sekcii Radiaca algoritmy. Najčastejšie budeme pravdepodobne používať napr. Buď Selection sort pre pohodlné napísanie, alebo nejaký lepší sortovací algoritmus, treba haldové triedenie a pod. Výhoda je, že nepotrebujeme ďalšie pamäť a dokážeme s poľom triediť na mieste. Ale či je to výhoda v čase GB pamäťou ...

Rozdiel medzi listom a poľom

Pole má jednu veľkú výhodu aj nevýhodu, je statické. Často však nevieme, ako bude pole dlhé, alebo z neho chceme za behu programu odoberať prvky alebo ich do neho pridávať. Existuje na to taký malý trik.

Majme pole dĺžky n. Pokiaľ do neho chceme vložiť ďalší prvok, tzn. na index n + 1, založíme nové poľa veľkosti 2n a skopírujeme prvky pôvodného poľa do tohto nového. Takže pridanie prvku väčšinu času stojí O(1) a raz za čas O(n), keď dôjde kapacita poľa, čo nám dohromady dá O(1) (hovorí sa tomu amortizovaná časová zložitosť) .Potom, až toto pole zase naplníme, zdvojnásobíme kapacitu atď. Takto dostaneme dynamické pole, ktoré sa môže meniť. Nie je to však príliš elegantný pre bežné použitie, preto v mnohých jazykoch môžeme použiť dynamické pole - List, ktorý túto prácu robí za nás.

List

List je oproti poli dynamická dátová štruktúra, môžeme ho teda meniť za behu, pridávať, uberať, pýtať sa na jeho veľkosť atď.

Operácie, pre ktoré chceme pracovať s listom, sú:

• všetky ako s poľom
• toArray(), teda prevod zoznamu na obyčajné pole
• a hromada ďalších

Všetky operácie ako s poľom

List je múdrejší, dynamické pole, tzn. interne robí to, čo sme si popísali vyššie u polia a čo sme väčšinou leniví implementovať ručne. Všetky časové zložitosti, týkajúce sa vyhľadávania, vloženie, zmazanie atď. Sú rovnaké ako u poľa. Výhoda je však tá, že miesto zložité syntaxe, ktorú sme museli predtým popisovať správanie funkcie, môžeme jednoducho volať jednotlivé metódy priamo na liste: List.Add(), List.Delete(), List.Sort(), List.Contains()... List je vnútorne implementovaný pomocou poľa, pri pridaní nového záznamu sa teda pri vyčerpaní kapacity vytvorí interne pole nové a prvky sa doň skopírujú.

ToArray ()

List je síce tiež pole, ale niekedy je potrebné pracovať priamo s poľom a nie s listom. Sú prípady, keď potrebujeme, aby funkcia, ktorá dostane pole čísel, mohla pracovať s nemennou usporiadanú postupnosťou. Preto je v liste vždy zabudovaná funkcia toArray() (a pokiaľ nie je, je triviálne si ju napísať). Ide len o to, že list skopíruje všetky svoje prvky do nového poľa sa zhodnú veľkosťou ako má list.

Hromada ďalších

List je už pripravený v jazykoch ako C # a Java, čo sú objektovo orientované jazyky. List má preto mnoho ďalších pridaných metód, ktoré môžete ako programátori veselo používať (clear(), findAll(), ...). Je však pravdepodobné, že pre väčšinu operácií vám bude stačiť to, na čo sa používa i pole. Na záver je teda vhodná otázka - používať list alebo pole?

List vs. poľa

Veľmi často sa stane, že začnete s listom a skončíte kvôli funkcii toArray() s poľom či naopak. S listom sa veľmi dobre pracuje a keď si zvyknete na jeho na začiatok trochu zvláštne syntax, stane sa veľmi užitočným nástrojom. Zvlášť kvôli metódam na liste sa z neho stane pohodlný pomocník. Nezabudnite však, že je to len trochu múdrejší poľa a že si môžete vlastné list postaviť sami.