Array, List, Dictionary – jaký je v tom rozdíl? (Level 100)

Dotaz studenta:

Na learnCS.org jsem narazil na tři skoro stejné kapitoly: arrays, lists, dictionaries. Nevidím v nich prakticky žádný rozdíl. Mám se učit všechny tři, nebo stačí pole(arrays)?

Moje odpověď (Level 100):

Array (pole) je primitivní datová struktura, která je prazákladem všeho. Je to prostě souvislý kus paměti předem určené velikosti (počet prvků se určuje při zakládání pole), do kterého se dají uložit jednotlivé prvky stejného typu, a to každý zásadně na konkrétní pozici určenou indexem (např pole[3] = hodnota). Pole je základ všeho, většina složitějších množinových datových struktur interně pole používá.
List (seznam) je datová struktura vyšší úrovně, která je určená pro ukládání libovolného počtu prvků stejného typu. Na rozdíl od čistého pole:
- není nutné určovat předem velikost, List se sám přizpůsobuje podle počtu prvků v něm uložených,
- není nutné pracovat jen s pozicemi (indexy) prvků, ale je možné použít připravené pomocné metody
  - Add(prvek) – přidá prvek na konec seznamu
  - Remove(prvek) – odebere prvek ze seznamu
  - Insert(pozice, prvek) – přidá prvek na konkrétní pozici
  - Contains(prvek) – ověří, zdali určitý prvek v Listu existuje
  - Find(predikát) – vyhledá prvek
  - …je tam spousta dalších metod, které ti práci usnadní
- Interně List používá Array, jenom tě odstíní od nutnosti řešit detaily. Na začátku si sám vytvoří pole určité základní velikosti, které když se zaplní, tak vytvoří nové pole dvojnásobné velikosti, prvky do něj přesune a původní pole uvolní. Naopak Remove() umí přesouvat do menšího pole, Insert/Remove se stará o posouvání prvků v podkladovém poli, Contains/Find umí pole sekvenčně projít, atp.
- List je prostě pohodlnější pro běžnou práci, pokud se nechceš zaobírat detaily pole a nepotřebuje optimalizovat výkon na krev.
- Pro snadné použití List podporuje i podobnou syntaxi jako array, tj. přístup přes indexer, např. list[3] = hodnota.
Dictionary (slovník) je datová struktura vyšší úrovně, kde hlavním rozdílem je uložení prvků pod klíčem.
- - Klíč se pak používá v podstatě místo indexu jako způsob přístupu na prvky (dict[klíč] = hodnota). Cokoliv do Dictionary dávám, musí mít určený klíč – do slovníku se ve skutečnosti ukládají dvojice klíč-hodnota.
  - Interně je to uspořádáno do hashovací tabulky (podrobnosti někdy později), díky čemuž je přístup prostřednictvím klíče extrémně rychlý.
  - Slovník má podobné metody jako List, jen se tam pracuje s tou dvojící klíč-hodnota:
    - Add(klíč, hodnota) – přidá do slovníku
    - Remove(klíč) – odebere ze slovníku (hodnotu nepotřebuji znát)
    - Contains(klíč)
    - atd.
  - Slovník se používá všude tam, kde si potřebuješ uspořádat data v pojetí klíč-hodnota, např. pokud chceš spočítat četnost něčeho ve velké vstupní sadě, potom si jako klíč použiješ identifikátor a jako hodnotu ten aktuální počet. Když ti budou přicházet slova a ty je máš spočítat v celé knížce, tak třeba pro každé slovo děláš dict[slovo] = dict[slovo] + 1. Hodnota samozřejmě nemusí být jen číslo, ale i něco složitějšího (v podstatě jakýkoliv typ).
  - I slovník podporuje podobnou syntaxi jako pole/seznam, tj. přístup přes indexer, jen se tam používá klíč, např. dict[klíč] =hodnota