Lekce 2 - Datové struktury pole a list

V minulé lekci, Úvod do datových struktur, jsme si uvedli datové struktury a udělali jejich rychlé porovnání.

Dnes si probereme ty nejzákladnější datové struktury, pole a seznam (list). Obě slouží k ukládání prvků pomocí číselných indexů. V čem se tedy tyto 2 fundamentální struktury liší a k čemu je používat?

Pole

Pole (anglicky array) je datová struktura, se kterou se setkáme snad ve všech programovacích jazycích. Vzniklo z touhy mít kromě čísel i možnost reprezentovat vektory. Prvky pole mohou být také pole. Mějme např. krychli, která 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 být zkrátka cokoliv, co dokážeme nějak reprezentovat. Například String není nic jiného, než pole znaků (charů). Proto lze String tak dobře indexovat. Dokonce i celý adresový prostor je jedno velké pole s indexováním pomocí adresy proměnné.

Jak se s polem pracuje?

Pole je v podstatě hromada krabic poskládaných vedle sebe a k tomu očíslovaných přirozenými čísly. Je dobrým zvykem číslovat od nuly. Sice jsou v dnešních kapacitách paměti nějaké 2 bajty jako úspora paměti málo, ale zpřehlední to váš kód. Pole je statická datová struktura, což znamená, že má pevně danou délku.

Na poli provádíme tyto operace:

• vypiš pole
• vlož prvek
• smaž prvek
• vyhledej prvek
• změň prvek
• setřiď prvky

Inicializace pole

Tento krok se liší jazyk od jazyka. Pole je statická datová struktura, takže musíme provést jeho inicializaci, kdy pevně určíme počet prvků a jejich datový typ.

Některé programovací jazyky, např. PHP nebo JavaScript, implementovaly svá pole jako seznamy nebo dokonce slovníky. Tímto faktem se nenecháme zmást a pojem pole budeme chápat z algoritmizačního hlediska jako statickou strukturu několika číselně indexovaných prvků.

Ukažme si, jak může vypadat inicializace pole:

int [] array_of_integers = new int [100];

Tato inicializace by měla být dostatečně obecná, abyste ji mohli použít ve vašich jazycích. Na začátku je potřeba říct, čeho je to vlastně pole. Teď jsme si zavedli pole integerů, mohli bychom si však vymyslet svoji vlastní třídu, třeba class Teacher { ... } a mít pole učitelů:

Teacher [] array_of_teachers = new Teacher [100];

Pokud se inicializuje pole hodnotových typů, tj. int, float atd..., mají většinou implicitně tyto hodnoty:

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

Vypiš pole

Toto je klasické použití pole jako struktury pro uchovávání dat. Kód níže vypisuje všechny položky pole pole pomocí cyklu for:

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

Co se týká složitosti, je jasné, že musíme projít celé pole, abychom vypsali každý prvek. Časová složitost operace je tedy O(n).

Vlož prvek / uprav prvek

Tato operace může být provedena pomocí přímého indexování, nebo vložení prvku na konec prostoru pole, který právě využíváme (pole si můžeme vytvořit větší než potřebujeme a nemusí být vždy úplně plné). Pokud budeme vkládat prvek na konec takového pole, je potřeba jej projít celé, popřípadě mít vedle uloženou proměnnou značící kam až nám prvky momentálně sahají. V prvním případě je složitost O(n), neboť se nám může stát, že musíme projít celé pole.

Pokud víme kolik prvků máme momentálně obsazených, vložíme prvek na konec pole v čase O(1), tedy konstantním.

A pokud chceme upravit prvek na konkrétním indexu, zvládneme to přímo v O(1):

array[i] = nejaky_prvek;

Vyhledej prvek

Pro pole délky n musíme prohledat nejhůře celé pole, tj. n prvků. Proto je složitost této operace O(n). Ukažme si opět 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.");

Odstraň prvek

Pokud bychom měli pole kladných čísel, mohli bychom prvek smazat tak, že bychom jeho hodnotu nastavili na 0. To by trvalo v O(1). Pokud bychom chtěli pole i zmenšit, tato operace by trvala v O(n), protože se prvky za smazaným prvkem musí posunout o jednu pozici doleva a zaplnit tak "díru", která v poli vznikla:

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

Seřaď prvky

Na seřazení prvků v poli můžeme použít algoritmy v sekci Řadící algoritmy. Nejčastěji budeme pravděpodobně používat např. buď Selection sort pro pohodlné napsání, nebo nějaký lepší sortovací algoritmus, třeba haldové třídění apod. Výhoda je, že nepotřebujeme další paměť a dokážeme s polem třídit na místě. Ale jestli je to výhoda v době GB pamětí...

Rozdíl mezi listem a polem

Pole má jednu velkou výhodu i nevýhodu, je statické. Často však nevíme, jak bude pole dlouhé, nebo z něj chceme za běhu programu odebírat prvky nebo je do něj přidávat. Existuje na to takový malý trik.

Mějme pole délky n. Pokud do něj chceme vložit další prvek, tzn. na index n + 1, založíme nové pole o velikosti 2n a zkopírujeme prvky původního pole do tohoto nového. Takže přidání prvku většinu času stojí O(1) a jednou za čas O(n), když dojde kapacita pole, což nám dohromady dá O(1) (říká se tomu amortizovaná časová složitost). Potom, až toto pole zase naplníme, zdvojnásobíme kapacitu atd. Takto dostaneme dynamické pole, které se může měnit.

Není to však příliš elegantní pro běžné použití, proto v mnoha jazycích můžeme použít dynamické pole – List, který tuto práci dělá za nás.

List

List je oproti poli dynamická datová struktura, můžeme ho tedy měnit za běhu, přidávat, ubírat, ptát se na jeho velikost atd.

Operace, pro které chceme pracovat s listem, jsou:

• všechny jako s polem
• toArray(), tedy převod seznamu na obyčejné pole
• a hromada dalších

Všechny operace jako s polem

List je chytřejší, dynamické pole, tzn. interně dělá to, co jsme si popsali výše u pole a co jsme většinou líní implementovat ručně. Všechny časové složitosti, týkající se vyhledávání, vložení, smazání atd. jsou stejné jako u pole. Výhoda je však ta, že místo složité syntaxe, kterou jsme museli dříve popisovat chování funkce, můžeme jednoduše volat jednotlivé metody přímo na listu: List.Add(), List.Delete(), List.Sort(), List.Contains()... List je vnitřně implementován pomocí pole, při přidání nového záznamu se tedy při vyčerpání kapacity vytvoří interně pole nové a prvky se do něj zkopírují.

toArray()

List je sice také pole, ale někdy je třeba pracovat přímo s polem a ne s listem. Jsou případy, kdy potřebujeme, aby funkce, která dostane pole čísel, mohla pracovat s neměnnou uspořádanou posloupností. Proto je v listu vždy zabudována funkce toArray() (a pokud není, je triviální si ji napsat). Jde jen o to, že list zkopíruje všechny své prvky do nového pole se shodnou velikostí jako má list.

Hromada dalších

List je již připravený v jazycích jako C# a Java, což jsou objektově orientované jazyky. List má proto mnoho dalších přidaných metod, které můžete jako programátoři vesele používat (clear(), findAll(),...). Je však pravděpodobné, že pro většinu operací vám bude stačit to, na co se používá i pole. Na závěr je tedy vhodná otázka – používat list nebo pole?

List vs. pole

Velmi často se stane, že začnete s listem a skončíte kvůli funkci toArray() s polem či naopak. S listem se velmi dobře pracuje a pokud si zvyknete na jeho poněkud zvláštní syntax na začátku, stane se velmi užitečným nástrojem. Zvlášť kvůli metodám na listu se z něj stane pohodlný pomocník. Nezapomeňte však, že je to pouze trochu chytřejší pole a že si můžete vlastní list postavit sami.

V další lekci, Spojový seznam, si ukážeme, jak vypadá spojový seznam, jak se liší od pole, a jaké jsou časové složitosti jednotlivých operací.