Propojená datová struktura - Linked data structure
Ve vědě o počítačích , je spojena datová struktura je datová struktura, která se skládá ze sady datových záznamů ( uzly ), spojených dohromady a organizované odkazy ( odkazy nebo ukazatele ). Spojení mezi daty lze také nazvat konektorem .
V propojených datových strukturách se s odkazy obvykle zachází jako se speciálními datovými typy, které lze dereferencovat nebo porovnávat pouze pro rovnost. Propojené datové struktury jsou tedy v kontrastu s poli a jinými datovými strukturami, které vyžadují provádění aritmetických operací s ukazateli. Tento rozdíl platí, i když jsou uzly ve skutečnosti implementovány jako prvky jednoho pole a odkazy jsou ve skutečnosti indexy pole : pokud se na těchto indexech nedělá žádná aritmetika, datová struktura je v zásadě propojená.
Propojení lze provést dvěma způsoby - pomocí dynamické alokace a pomocí propojení indexů matic.
Propojené datové struktury zahrnují propojené seznamy , vyhledávací stromy , expresní stromy a mnoho dalších široce používaných datových struktur. Jsou také klíčovými stavebními kameny pro mnoho efektivních algoritmů, jako je topologické třídění a nastavení sjednocovacího hledání .
Běžné typy propojených datových struktur
Propojené seznamy
Propojený seznam je kolekce struktur seřazených nikoli podle jejich fyzického umístění v paměti, ale podle logických odkazů, které jsou uloženy jako součást dat v samotné struktuře. Není nutné, aby byl uložen na sousedních paměťových místech. Každá struktura má datové pole a pole adresy. Pole Adresa obsahuje adresu jeho nástupce .
Propojený seznam může být propojen jednotlivě, dvakrát nebo vícekrát a může být lineární nebo kruhový.
- Základní vlastnosti
- Objekty, nazývané uzly , jsou spojeny v lineární posloupnosti.
- Odkaz na první uzel seznamu je vždy zachován. Toto se nazývá „hlava“ nebo „přední“.
Propojený seznam se třemi uzly obsahuje každé dvě pole: celočíselnou hodnotu a odkaz na další uzel
Příklad v Javě
Toto je příklad třídy uzlu, která se používá k ukládání celých čísel v implementaci Java propojeného seznamu:
public class IntNode {
public int value;
public IntNode link;
public IntNode(int v) { value = v; }
}
Příklad v C
Toto je příklad struktury použité pro implementaci propojeného seznamu v C:
struct node
{
int val;
struct node *next;
};
Toto je příklad použití typedefs :
typedef struct node node;
struct node
{
int val;
node *next;
};
Poznámka: Taková struktura, která obsahuje prvek, který ukazuje na stejnou strukturu, se nazývá struktura s vlastním odkazem.
Příklad v C ++
Toto je příklad struktury třídy uzlu používané pro implementaci propojeného seznamu v C ++:
class Node
{
int val;
Node *next;
};
Prohledejte stromy
Vyhledávací strom je stromová datová struktura, do jejíž uzlů lze ukládat datové hodnoty z nějaké uspořádané sady , což je takové, že při procházení stromu v pořadí jsou uzly navštěvovány ve vzestupném pořadí uložených hodnot.
- Základní vlastnosti
- Objekty, nazývané uzly, jsou uloženy v uspořádané sadě.
- Traversal v pořadí poskytuje vzestupný odečet dat ve stromu.
Výhody a nevýhody
Propojený seznam versus pole
Ve srovnání s poli umožňují propojené datové struktury větší flexibilitu při organizaci dat a při přidělování prostoru pro ně. V polích musí být na začátku přesně specifikována velikost pole, což může být potenciální ztráta paměti nebo libovolné omezení, které by později nějakým způsobem bránilo funkčnosti. Propojená datová struktura je vytvářena dynamicky a nikdy nemusí být větší, než program vyžaduje. To také nevyžaduje žádné hádání v době vytvoření, pokud jde o to, kolik místa musí být přiděleno. Toto je funkce, která je klíčem k zabránění plýtvání pamětí.
V poli musí být prvky pole v souvislé (připojené a postupné) části paměti. Ale v propojené datové struktuře poskytuje odkaz na každý uzel uživatelům informace potřebné k nalezení dalšího. Uzly propojené datové struktury lze na rozdíl od polí také individuálně přesunout na různá místa ve fyzické paměti, aniž by to ovlivnilo logická spojení mezi nimi. S náležitou péčí může určitý proces nebo vlákno přidat nebo odstranit uzly v jedné části datové struktury, i když jiné procesy nebo vlákna pracují na jiných částech.
Na druhou stranu přístup k jakémukoli konkrétnímu uzlu v propojené datové struktuře vyžaduje sledování řetězce odkazů, které jsou uloženy v každém uzlu. V případě, že struktura má n uzly, a každý uzel obsahuje nanejvýš b odkazy, bude některé uzly, které nemohou být dosaženo za méně než log b n stupňů, čímž se zpomaluje proces přístupu těchto uzlů - to někdy představuje značné zpomalení, zejména v případě struktur obsahujících velké množství uzlů. U mnoha struktur mohou některé uzly vyžadovat nejhorší případ až do n −1 kroků. Naproti tomu mnoho datových struktur pole umožňuje přístup k jakémukoli prvku se stálým počtem operací, nezávisle na počtu položek.
Implementace těchto propojených datových struktur se obecně provádí prostřednictvím dynamických datových struktur . Dává nám šanci znovu použít konkrétní prostor. Paměť lze efektivněji využívat pomocí těchto datových struktur. Paměť je alokována podle potřeby, a pokud již paměť není potřeba, provede se deallocation.
Obecné nevýhody
Propojené datové struktury se také mohou vyskytnout ve značné režii alokace paměti (pokud jsou uzly přidělovány jednotlivě) a zmařit algoritmy stránkování paměti a ukládání do mezipaměti procesoru (protože mají obecně špatnou referenční lokalitu ). V některých případech mohou propojené datové struktury také využívat více paměti (pro pole odkazů) než konkurenční maticové struktury. Důvodem je, že propojené datové struktury nejsou souvislé. Instance dat lze na rozdíl od polí najít všude v paměti.
V polích lze k n-tému prvku přistupovat okamžitě, zatímco v propojené datové struktuře musíme sledovat více ukazatelů, takže doba přístupu k prvku se liší podle toho, kde ve struktuře je prvek.
V některých teoretických modelech výpočtu, které vynucují omezení propojených struktur, jako je například ukazatel , mnoho problémů vyžaduje více kroků než v neomezeném modelu stroje s náhodným přístupem .
