„Bad programmers worry about the code. Good programmers worry about data structures and their relationships." - Linus Torvalds, 2006
Datová struktura určuje konkrétní způsob organizace dat v paměti počítače. Abstraktní datový typ (ADT) specifikuje množinu hodnot a množinu operací nezávisle na konkrétní implementaci. Slovo abstraktní vyjadřuje tuto nezávislost na implementaci (a na programovacím jazyku), abstrahujeme od konkrétní reprezentace dat a implementace operací na těmito daty. Cílem ADT je zejména efektivní manipulace s daty, což vede ke zjednodušení a zpřehlednění programů.
ADT byl představen v roce 1974 Barbarou Liskov a Stephenem Zilles v práci Programming with Abstract Data Types. Snahou bylo pochopit, jak by mohl programátor izolovat části programu a jak jej udělat více modulární.
Definice ADT:
- formální definice pomocí signatur a axiomů,
- neformální definice implementace (vlastní implementace, knihovní funkce). Např.
- Java: Balík tříd java.util
- C++: STL (StandardTemplateLibrary) kontainery
Mnohé klasické abstraktní datové struktury jsou implementovány ve standardních knihovnách programovacích jazyků nebo jsou vestavěné přímo v programovacích jazycích. Například datová struktura hashovací tabulka je vestavěna v běžně známých skriptovacích jazyků (PHP, JS).
Lineární datové struktury
Jednotlivé prvky množiny dat jsou v nich uloženy postupně za sebou, každý prvek, kromě prvního má právě jednoho předchůdce.
Asociativní datové struktury
Stromové datové struktury
Algoritmům pro stromové uspořádání dat se věnuje celá sekce o stromech
K zamyšlení
- Kdy použijeme pole a kdy seznam?
- Jaký je hlavní rozdíl mezi zásobníkem a frontou?