6 dátových štruktúr, ktoré by mal poznať každý programátor

Cesta stať sa zdatným a úspešným programátorom je náročná, no určite dosiahnuteľná. Dátové štruktúry sú základnou súčasťou, ktorú musí ovládať každý študent programovania, a je pravdepodobné, že ste sa už naučili alebo ste pracovali s niektorými základnými dátovými štruktúrami, ako sú polia alebo zoznamy.

Anketári majú tendenciu uprednostňovať otázky týkajúce sa dátových štruktúr, takže ak sa pripravujete na pracovný pohovor, budete si musieť oprášiť svoje znalosti dátových štruktúr. Čítajte ďalej, pretože uvádzame najdôležitejšie dátové štruktúry pre programátorov a pracovné pohovory.

Prepojené zoznamy sú jednou z najzákladnejších dátových štruktúr a často sú východiskovým bodom pre študentov vo väčšine kurzov dátových štruktúr. Prepojené zoznamy sú lineárne dátové štruktúry, ktoré umožňujú sekvenčný prístup k dátam.

Prvky v rámci prepojeného zoznamu sú uložené v jednotlivých uzloch, ktoré sú spojené (prepojené) pomocou ukazovateľov. Prepojený zoznam si môžete predstaviť ako reťazec uzlov, ktoré sú navzájom spojené pomocou rôznych ukazovateľov.

Súvisiace: Úvod do používania prepojených zoznamov v jazyku Java

Než sa dostaneme k špecifikám rôznych typov prepojených zoznamov, je dôležité pochopiť štruktúru a implementáciu jednotlivých uzlov. Každý uzol v prepojenom zozname má aspoň jeden ukazovateľ (uzly dvojito prepojeného zoznamu majú dva ukazovatele), ktorý ho spája s ďalším uzlom v zozname a samotnou údajovou položkou.

Každý prepojený zoznam má hlavný a koncový uzol. Uzly jednosmerného zoznamu majú iba jeden ukazovateľ, ktorý ukazuje na ďalší uzol v reťazci. Okrem ďalšieho ukazovateľa majú uzly dvojito prepojeného zoznamu ďalší ukazovateľ, ktorý ukazuje na predchádzajúci uzol v reťazci.

Otázky v rozhovoroch súvisiace s prepojenými zoznamami sa zvyčajne točia okolo vloženia, vyhľadávania alebo vymazania konkrétneho prvku. Vloženie do prepojeného zoznamu trvá O(1) čas, ale vymazanie a vyhľadávanie môže v najhoršom prípade trvať O(n). Prepojené zoznamy teda nie sú ideálne.

2. Binárny strom

Binárne stromy sú najobľúbenejšou podmnožinou dátovej štruktúry rodiny stromov; prvky v binárnom strome sú usporiadané v hierarchii. Medzi ďalšie druhy stromov patria AVL, červeno-čierne, B stromy atď. Uzly binárneho stromu obsahujú dátový prvok a dva ukazovatele na každý podriadený uzol.

Každý nadradený uzol v binárnom strome môže mať maximálne dva podriadené uzly a každý podriadený uzol môže byť zase rodičom dvoch uzlov.

Súvisiace: Sprievodca binárnymi stromami pre začiatočníkov

Binárny vyhľadávací strom (BST) ukladá údaje v zoradenom poradí, kde prvky s párom kľúč – hodnota menším ako nadradený uzol sú uložené vľavo a prvky s kľúčom – hodnotou väčšou ako nadradený uzol sú uložené na správny.

Binárne stromy sa bežne pýtajú na pohovoroch, takže ak sa pripravujete na pohovor, mali by ste vedieť, ako vyrovnať binárny strom, vyhľadať konkrétny prvok a podobne.

3. Tabuľka hash

Hashovacie tabuľky alebo hash mapy sú vysoko efektívnou dátovou štruktúrou, ktorá ukladá dáta vo formáte poľa. Každému dátovému prvku je v hašovacej tabuľke priradená jedinečná hodnota indexu, čo umožňuje efektívne vyhľadávanie a odstraňovanie.

Proces priraďovania alebo mapovania kľúčov v hašovacej mape sa nazýva hašovanie. Čím efektívnejšia je hašovacia funkcia, tým lepšia je účinnosť samotnej hašovacej tabuľky.

Každá hašovacia tabuľka ukladá dátové prvky do páru hodnota-index.

Kde hodnota sú údaje, ktoré sa majú uložiť, a index je jedinečné celé číslo používané na mapovanie prvku do tabuľky. Hashovacie funkcie môžu byť veľmi zložité alebo veľmi jednoduché, v závislosti od požadovanej účinnosti hashovacej tabuľky a od toho, ako budete riešiť kolízie.

Kolízie často vznikajú, keď hašovacia funkcia vytvára rovnaké mapovanie pre rôzne prvky; kolízie hash mapy možno vyriešiť rôznymi spôsobmi, pomocou otvoreného adresovania alebo reťazenia.

Hašovacie tabuľky alebo hašovacie mapy majú množstvo rôznych aplikácií vrátane kryptografie. Sú to dátové štruktúry prvej voľby, keď sa vyžaduje vkladanie alebo vyhľadávanie v konštantnom čase O(1).

4. Hromady

Zásobníky sú jednou z jednoduchších dátových štruktúr a dajú sa celkom ľahko zvládnuť. Dátová štruktúra zásobníka je v podstate akýkoľvek zásobník v reálnom živote (spomeňte si na stoh krabíc alebo tanierov) a funguje spôsobom LIFO (Last In First Out).

Vlastnosť LIFO zásobníkov znamená, že prvok, ktorý ste vložili ako posledný, bude prístupný ako prvý. K prvkom pod horným prvkom v stohu nemôžete pristupovať bez toho, aby ste prvky nad ním nevysunuli.

Stohy majú dve hlavné operácie – zatlačenie a vysunutie. Stlačenie sa používa na vloženie prvku do stohu a pop odstráni najvrchnejší prvok zo stohu.

Majú tiež veľa užitočných aplikácií, takže je veľmi bežné, že anketári kladú otázky súvisiace so zásobníkmi. Vedieť, ako obrátiť zásobník a vyhodnotiť výrazy, je celkom nevyhnutné.

5. Fronty

Fronty sú podobné ako zásobníky, ale fungujú spôsobom FIFO (First In First Out), čo znamená, že máte prístup k prvkom, ktoré ste vložili skôr. Dátová štruktúra frontu môže byť vizualizovaná ako akýkoľvek skutočný front, kde sú ľudia umiestnení na základe poradia príchodu.

Operácia vloženia frontu sa nazýva radenie a vymazanie/odstránenie prvku zo začiatku radu sa označuje ako vyradenie z radu.

Súvisiace: Príručka pre začiatočníkov k pochopeniu frontov a prioritných frontov

Prioritné fronty sú integrálnou aplikáciou frontov v mnohých životne dôležitých aplikáciách, ako je plánovanie CPU. V prioritnom rade sú prvky zoradené podľa priority a nie podľa poradia príchodu.

6. Hromady

Haldy sú typom binárneho stromu, kde sú uzly usporiadané vo vzostupnom alebo zostupnom poradí. V min. halde je kľúčová hodnota rodiča rovnaká alebo menšia ako hodnota jeho potomkov a koreňový uzol obsahuje minimálnu hodnotu celej haldy.

Podobne koreňový uzol maximálnej haldy obsahuje maximálnu hodnotu kľúča haldy; musíte zachovať vlastnosť min/max haldy v celej halde.

Súvisiace: Hromady vs. Hromady: Čo ich odlišuje?

Hromady majú množstvo aplikácií vďaka svojej veľmi efektívnej povahe; primárne sú prioritné fronty často implementované prostredníctvom hromady. Sú tiež základným komponentom v algoritmoch heapsort.

Naučte sa dátové štruktúry

Dátové štruktúry sa môžu na prvý pohľad zdať trýznivé, ale venujte im dostatok času a zistíte, že sú jednoduché.

Sú dôležitou súčasťou programovania a takmer každý projekt bude vyžadovať, aby ste ich používali. Je dôležité vedieť, aká dátová štruktúra je ideálna pre daný scenár.

7 algoritmov, ktoré by mal poznať každý programátor

Tieto algoritmy sú nevyhnutné pre pracovný postup každého programátora.

Prečítajte si ďalej

O autorovi