Rozdíl mezi poli a propojenými seznamy

Pole vs propojené seznamy

Pole jsou nejčastěji používanou datovou strukturou pro ukládání kolekce prvků. Většina programovacích jazyků poskytuje metody pro snadné deklarování polí a přístupových prvků v polích. Propojený seznam, přesněji samostatně propojený seznam, je také datovou strukturou, kterou lze použít k ukládání kolekce prvků. Skládá se ze sekvence uzlů a každý uzel má odkaz na další uzel v sekvenci.

Na obrázku 1 je znázorněn kus kódu, který se obvykle používá k deklarování a přiřazování hodnot matici. 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 k nim přistupovány pomocí indexů 0 až 4. Jednou z důležitých vlastností pole je, že celé pole je přiděleno jako jeden blok paměti a každý prvek získá svůj vlastní prostor v poli. 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, aby bylo na bezpečné straně. Většinu času ale ve skutečnosti použijeme méně prvků, než jsme přidělili. Takže značné množství paměti je ve skutečnosti zbytečné. Na druhou stranu, pokud „dostatečně velké pole“ není ve skutečnosti dostatečně velké, program by se zhroutil.

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á spojení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 tak, že začnete na hlavě a sledujete další ukazatel, dokud nedosáhnete požadovaného prvku.

I když jsou pole a propojené seznamy podobné v tom smyslu, že oba jsou používány k ukládání kolekce prvků, dochází k rozdílům v důsledku strategií, které používají k přidělování paměti svým prvkům. Pole přidělují paměť všem svým prvkům jako jeden blok a velikost pole musí být stanovena za běhu. To by učinilo pole neefektivní v situacích, kdy neznáte velikost pole v době kompilace. Protože propojený seznam přiděluje paměť jednotlivým prvkům samostatně, bylo by to mnohem účinnější v situacích, kdy neznáte velikost seznamu v době kompilace. Prohlášení a přístup k prvkům v propojeném seznamu by nebyl přímý ve srovnání s tím, jak přímo přistupujete k prvkům v poli pomocí jeho indexů.