Pole vs propojené seznamy
Pole jsou nejběžněji používanou datovou strukturou pro ukládání kolekce prvků. Většina programovacích jazyků poskytuje metody pro snadnou deklaraci polí a přístup k prvkům v polích. Linked list, přesněji single-linked list, je také datová struktura, kterou lze použít k uložení kolekce prvků. Je tvořen posloupností uzlů a každý uzel má odkaz na další uzel v posloupnosti.
Na obrázku 1 je znázorněn kus 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 z důležitých vlastností pole je, že celé pole je alokováno jako jeden blok paměti a každý prvek má svůj vlastní prostor v poli. Jakmile je pole definováno, jeho velikost je pevná. Pokud si tedy nejste jisti velikostí pole v době kompilace, museli byste definovat dostatečně velké pole, abyste byli na bezpečné straně. Ale většinu času skutečně použijeme menší počet prvků, než jsme alokovali. Značné množství paměti je tedy ve skutečnosti promarněno. Na druhou stranu, pokud „dostatečně velké pole“není ve skutečnosti dostatečně velké, program se zhroutí.
Propojený seznam přiděluje paměť svým prvkům samostatně ve svém vlastním bloku paměti a celková struktura je získána propojením těchto prvků jako článků 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 aktuální 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.
| data | další |
Obrázek 3: Prvek propojeného seznamu
Obrázek 4 znázorňuje 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 hodnotu null. K jakémukoli prvku v seznamu lze přistupovat tak, že začnete od začátku a budete následovat další ukazatel, dokud nenajdete požadovaný prvek.
I když jsou pole a propojené seznamy podobné v tom smyslu, že se oba používají k ukládání kolekce prvků, dochází u nich k rozdílům v důsledku strategií, které používají k alokaci paměti jejich prvkům. Pole přiděluje paměť všem svým prvkům jako jeden blok a velikost pole musí být určena za běhu. To by způsobilo, že pole by byla neefektivní v situacích, kdy neznáte velikost pole v době kompilace. Vzhledem k tomu, že propojený seznam přiděluje paměť svým prvkům samostatně, byl by mnohem efektivní v situacích, kdy neznáte velikost seznamu v době kompilace. Deklarace a přístup k prvkům v propojeném seznamu by nebyl přímočarý ve srovnání s tím, jak přímo přistupujete k prvkům v poli pomocí jeho indexů.
