6 datových struktur, které by měl znát každý programátor

Cesta k tomu stát se zdatným a úspěšným programátorem je obtížná, ale určitě dosažitelná. Datové struktury jsou základní složkou, kterou musí zvládnout každý student programování, a je pravděpodobné, že jste se již naučili nebo pracovali s některými základními datovými strukturami, jako jsou pole nebo seznamy.

Tazatelé dávají přednost kladení otázek souvisejících s datovými strukturami, takže pokud se připravujete na pracovní pohovor, budete si muset oprášit své znalosti datových struktur. Čtěte dále, protože uvádíme nejdůležitější datové struktury pro programátory a pracovní pohovory.

Propojené seznamy jsou jednou z nejzákladnějších datových struktur a často jsou výchozím bodem pro studenty většiny kurzů datových struktur. Propojené seznamy jsou lineární datové struktury, které umožňují sekvenční přístup k datům.

Prvky v rámci propojeného seznamu jsou uloženy v jednotlivých uzlech, které jsou propojeny (propojeny) pomocí ukazatelů. Propojený seznam si můžete představit jako řetězec uzlů, které jsou vzájemně propojeny pomocí různých ukazatelů.

Příbuzný: Úvod do používání propojených seznamů v Javě

Než se dostaneme ke specifikům různých typů propojených seznamů, je zásadní porozumět struktuře a implementaci jednotlivého uzlu. Každý uzel v propojeném seznamu má alespoň jeden ukazatel (uzly dvojitě propojeného seznamu mají dva ukazatele), který jej spojuje s dalším uzlem v seznamu a samotnou datovou položkou.

Každý propojený seznam má hlavní a koncový uzel. Uzly jednoduše propojeného seznamu mají pouze jeden ukazatel, který ukazuje na další uzel v řetězci. Kromě dalšího ukazatele mají uzly dvojitě propojeného seznamu další ukazatel, který ukazuje na předchozí uzel v řetězci.

Otázky k pohovoru související s propojenými seznamy se obvykle točí kolem vkládání, vyhledávání nebo mazání konkrétního prvku. Vložení do propojeného seznamu trvá O(1) čas, ale mazání a vyhledávání může v nejhorším případě trvat O(n). Propojené seznamy tedy nejsou ideální.

2. Binární strom

Binární stromy jsou nejoblíbenější podmnožinou datové struktury rodiny stromů; prvky v binárním stromu jsou uspořádány v hierarchii. Mezi další typy stromů patří AVL, červeno-černé, B stromy atd. Uzly binárního stromu obsahují datový prvek a dva ukazatele na každý podřízený uzel.

Každý nadřazený uzel v binárním stromě může mít maximálně dva podřízené uzly a každý podřízený uzel zase může být rodičem dvou uzlů.

Příbuzný: Průvodce pro začátečníky binárními stromy

Binární vyhledávací strom (BST) ukládá data v seřazeném pořadí, kde prvky s párem klíč–hodnota menším než nadřazený uzel jsou uloženy vlevo a prvky s párem klíč–hodnota větším než nadřazený uzel jsou uloženy na že jo.

Binární stromy jsou běžně dotazovány v rozhovorech, takže pokud se připravujete na rozhovor, měli byste vědět, jak zploštit binární strom, vyhledat konkrétní prvek a další.

3. Tabulka hash

Hashovací tabulky nebo hash mapy jsou vysoce efektivní datovou strukturou, která ukládá data ve formátu pole. Každému datovému prvku je v hashovací tabulce přiřazena jedinečná hodnota indexu, což umožňuje efektivní vyhledávání a mazání.

Proces přiřazování nebo mapování klíčů v hash mapě se nazývá hash. Čím efektivnější je hashovací funkce, tím lepší je účinnost samotné hashovací tabulky.

Každá hashovací tabulka ukládá datové prvky v páru hodnota-index.

Kde hodnota je data, která mají být uložena, a index je jedinečné celé číslo použité pro mapování prvku do tabulky. Hashovací funkce mohou být velmi složité nebo velmi jednoduché v závislosti na požadované efektivitě hashovací tabulky a na tom, jak budete řešit kolize.

Kolize často vznikají, když hashovací funkce vytváří stejné mapování pro různé prvky; kolize hash map lze řešit různými způsoby, pomocí otevřeného adresování nebo řetězení.

Hash tabulky nebo hash mapy mají řadu různých aplikací, včetně kryptografie. Jsou to datové struktury první volby, když je vyžadováno vkládání nebo vyhledávání v konstantním čase O(1).

4. Hromady

Zásobníky jsou jednou z jednodušších datových struktur a lze je celkem snadno zvládnout. Datová struktura zásobníku je v podstatě jakýkoli zásobník ze skutečného života (vzpomeňte si na stoh krabic nebo talířů) a funguje způsobem LIFO (Last In First Out).

Vlastnost LIFO zásobníku znamená, že prvek, který jste vložili jako poslední, bude přístupný jako první. Nemůžete přistupovat k prvkům pod horním prvkem v zásobníku, aniž byste prvky nad ním vysunuli.

Hromady mají dvě primární operace – push a pop. Zatlačení se používá k vložení prvku do stohu a pop odebere ze stohu nejvyšší prvek.

Mají také spoustu užitečných aplikací, takže je velmi běžné, že tazatelé pokládají otázky týkající se zásobníků. Vědět, jak obrátit zásobník a vyhodnotit výrazy, je zcela zásadní.

5. Fronty

Fronty jsou podobné zásobníkům, ale fungují způsobem FIFO (First In First Out), což znamená, že máte přístup k prvkům, které jste vložili dříve. Strukturu dat fronty lze vizualizovat jako libovolnou reálnou frontu, kde jsou lidé rozmístěni na základě pořadí příjezdu.

Operace vložení fronty se nazývá enqueue a odstranění/odstranění prvku ze začátku fronty se nazývá dequeuing.

Příbuzný: Příručka pro začátečníky k porozumění frontám a prioritním frontám

Prioritní fronty jsou integrální aplikací front v mnoha důležitých aplikacích, jako je plánování CPU. V prioritní frontě jsou prvky seřazeny podle priority, nikoli podle pořadí příchodu.

6. Hromady

Haldy jsou typem binárního stromu, kde jsou uzly uspořádány vzestupně nebo sestupně. V minimální haldě je klíčová hodnota nadřazeného prvku stejná nebo menší než hodnota jeho potomků a kořenový uzel obsahuje minimální hodnotu celé haldy.

Podobně kořenový uzel maximální haldy obsahuje maximální hodnotu klíče haldy; musíte zachovat vlastnost min/max haldy v celé haldě.

Příbuzný: Hromady vs. Stacks: Co je odlišuje?

Hromady mají spoustu aplikací díky své velmi efektivní povaze; primárně jsou prioritní fronty často implementovány prostřednictvím hromad. Jsou také základní součástí algoritmů heapsort.

Naučte se datové struktury

Datové struktury se mohou na první pohled zdát trýznivé, ale věnujte jim dostatek času a zjistíte, že jsou snadné.

Jsou důležitou součástí programování a téměř každý projekt bude vyžadovat, abyste je používali. Vědět, jaká datová struktura je pro daný scénář ideální, je zásadní.

7 algoritmů, které by měl znát každý programátor

Tyto algoritmy jsou nezbytné pro pracovní postup každého programátora.

Přečtěte si další

O autorovi