Pole vs. propojené seznamy
Pole jsou nejčastěji používanou datovou strukturou k ukládání kolekce prvků. Většina programovacích jazyků poskytuje metody pro snadné deklarace polí a přístup k prvkům v polích. Propojený seznam, přesněji jednotlivě propojený seznam, je také datovou strukturou, kterou lze použít k uložení kolekce prvků. Skládá se ze sekvence uzlů a každý uzel má odkaz na další uzel v sekvenci.
Na obrázku 1 je ukázka kódu, která se obvykle používá k deklaraci a přiřazení hodnot k poli. Obrázek 2 ukazuje, jak by pole vypadalo v paměti.
Výše uvedený kód definuje pole, do kterého lze uložit 5 celých čísel, a jsou přístupné pomocí indexů 0 až 4. Jednou důležitou vlastností pole je to, že celé pole je přiděleno jako jeden blok paměti a každý prvek v něm získá svůj vlastní prostor. Jakmile je pole definováno, jeho velikost je pevná. Takže pokud si nejste jisti velikostí pole v době kompilace, budete muset definovat dostatečně velké pole, abyste byli na bezpečné straně. Většinu času ale ve skutečnosti použijeme menší počet prvků, než kolik jsme přidělili. Značná část paměti je tedy skutečně zbytečná. Na druhou stranu, pokud „dostatečně velké pole“není ve skutečnosti dostatečně velké, program by selhal.
Propojený seznam přiděluje paměť svým prvkům samostatně ve svém vlastním bloku paměti a celková struktura se získá propojením těchto prvků jako odkazů v řetězci. Každý prvek v propojeném seznamu má dvě pole, jak je znázorněno na obrázku 3. Datové pole obsahuje skutečná uložená data a další pole obsahuje odkaz na další prvek v řetězci. První prvek propojeného seznamu je uložen jako hlava propojeného seznamu.
Obrázek 3: Prvek propojeného seznamu
Obrázek 4 zobrazuje propojený seznam se třemi prvky. Každý prvek ukládá svá data a všechny prvky kromě posledního ukládají odkaz na další prvek. Poslední prvek má ve svém dalším poli nulovou hodnotu. K libovolnému prvku v seznamu lze přistupovat spuštěním v záhlaví a sledováním dalšího ukazatele, dokud nesplníte požadovaný prvek.
I když jsou pole a propojené seznamy podobné v tom smyslu, že se obě používají k ukládání kolekce prvků, vznikají rozdíly kvůli strategiím, které používají k přidělení paměti jeho prvkům. Pole přidělují paměť všem jeho prvkům jako jeden blok a velikost pole je třeba určit za běhu. Tím by se pole stala neúčinnou v situacích, kdy neznáte velikost pole v době kompilace. Vzhledem k tomu, že propojený seznam přiděluje paměť jednotlivě svým prvkům, bylo by mnohem efektivnější v situacích, kdy neznáte velikost seznamu v době kompilace. Deklarace a přístup k prvkům v propojeném seznamu by nebyly přímočaré ve srovnání s tím, jak přímo přistupujete k prvkům v poli pomocí jeho indexů.
