Pole a Spojový seznam jsou dva způsoby organizace dat v paměti. Než pochopíte rozdíly mezi Pole a Spojový seznam , nejprve se podíváme v poli a propojený seznam .
char na řetězec v jazyce Java
Co je pole?
Datová struktura, která obsahuje prvky stejného typu. Datová struktura je způsob organizace dat; pole je datová struktura, protože sekvenčně organizuje data. Pole je velký kus paměti, ve kterém je paměť rozdělena na malé-malé bloky a každý blok je schopen uložit nějakou hodnotu.
Předpokládejme, že jsme vytvořili pole, které se skládá z 10 hodnot, pak každý blok bude ukládat hodnotu typu celé číslo. Pokud se pokusíme uložit hodnotu do pole různých typů, pak to není správné pole a vyvolá chybu při kompilaci.
Deklarace pole
Pole může být deklarováno jako:
data_type name of the array[no of elements]
Abychom pole deklarovali, musíme nejprve určit typ pole a poté název pole. Uvnitř hranatých závorek musíme zadat počet prvků, které má naše pole obsahovat.
Pojďme to pochopit na příkladu.
int a[5];
Ve výše uvedeném případě jsme deklarovali pole 5 prvků s ' A ' jméno an celé číslo datový typ.
Co je propojený seznam?
Propojený seznam je kolekce uzlů, které jsou náhodně uloženy. Každý uzel se skládá ze dvou polí, tj. data a odkaz . Zde jsou data hodnotou uloženou v tomto konkrétním uzlu a odkaz je ukazatel, který obsahuje adresu dalšího uzlu.
c# datum a čas
Rozdíly mezi Array a Linked seznamem
Nemůžeme říci, která datová struktura je lepší, tedy pole nebo spojový seznam . Může existovat možnost, že jedna datová struktura je lepší pro jeden druh požadavku, zatímco druhá datová struktura je lepší pro jiný druh požadavku. Existují různé faktory, jako jsou časté operace prováděné s datovou strukturou nebo velikost dat a další faktory, na základě kterých se datová struktura vybírá. Nyní uvidíme některé rozdíly mezi polem a propojeným seznamem na základě některých parametrů.
1. Náklady na přístup k prvku
V případě pole, bez ohledu na velikost pole, pole potřebuje konstantní čas pro přístup k prvku. V poli jsou prvky uloženy souvisle, takže pokud známe základní adresu prvku, můžeme snadno získat adresu libovolného prvku v poli. Potřebujeme provést jednoduchý výpočet, abychom získali adresu libovolného prvku v poli. Takže přístup k prvku v poli je O(1) z hlediska časové náročnosti.
V propojeném seznamu nejsou prvky uloženy souvisle. Skládá se z více bloků a každý blok je reprezentován jako uzel. Každý uzel má dvě pole, tj. jedno je pro datové pole a další ukládá adresu dalšího uzlu. Abychom našli jakýkoli uzel v propojeném seznamu, musíme nejprve určit první uzel známý jako hlavní uzel. Pokud máme najít druhý uzel v seznamu, pak musíme procházet od prvního uzlu a v nejhorším případě, abychom našli poslední uzel, projdeme všechny uzly. Průměrný případ přístupu k prvku je O(n).
Došli jsme k závěru, že náklady na přístup k prvku v poli jsou nižší než náklady na propojený seznam. Pokud tedy máme nějaký požadavek na přístup k prvkům, pak je lepší volbou pole.
2. Náklady na vložení prvku
Při vkládání mohou být tři scénáře:
V případě propojeného seznamu pro vložení prvku na začátek propojeného seznamu vytvoříme nový uzel a adresa prvního uzlu se přidá k novému uzlu. Tímto způsobem se nový uzel stane prvním uzlem. Časová složitost tedy není úměrná velikosti seznamu. Časová složitost by byla konstantní, tj. O(1).
Pokud pole není plné, můžeme nový prvek přidat přímo přes index. V tomto případě by časová složitost byla konstantní, tj. O(1). Pokud je pole plné, musíme nejprve pole zkopírovat do jiného pole a přidat nový prvek. V tomto případě by časová složitost byla O(n).
Abychom vložili prvek na konec propojeného seznamu, musíme projít celý seznam. Pokud se propojený seznam skládá z n prvků, pak by časová složitost byla O(n).
Předpokládejme, že chceme vložit prvek do ičtpozice pole; potřebujeme posunout n/2 prvků doprava. Časová složitost je tedy úměrná počtu prvků. Časová složitost by pro průměrný případ byla O(n).
cout
V případě propojeného seznamu musíme přejít na pozici, kde musíme vložit nový prvek. I když nemusíme provádět žádné řazení, ale musíme traverzovat do polohy n/2. Čas je úměrný počtu n prvků a časová složitost pro průměrný případ by byla O(n).
Výsledný propojený seznam je:
Implementace pole je ve srovnání s propojeným seznamem snadná. Při vytváření programu pomocí propojeného seznamu je program náchylnější k chybám, jako je chyba segmentace nebo únik paměti. Při vytváření programu v propojeném seznamu je tedy třeba věnovat velkou pozornost.
Propojený seznam má dynamickou velikost, zatímco pole je statické. Zde statický neznamená, že nemůžeme určit velikost za běhu, ale nemůžeme ji změnit, jakmile je velikost rozhodnuta.
3. Požadavky na paměť
Stejně jako se prvky v poli ukládají do jednoho souvislého bloku paměti, má pole pevnou velikost. Předpokládejme, že máme pole o velikosti 7 a pole se skládá ze 4 prvků, pak je zbytek prostoru nevyužitý. Paměť obsazená 7 prvky:
Paměťový prostor = 7*4 = 28 bajtů
Kde 7 je počet prvků v poli a 4 je počet bajtů celočíselného typu.
V případě propojeného seznamu není žádná nevyužitá paměť, ale další paměť je obsazena proměnnými ukazatele. Pokud jsou data typu integer, pak celková paměť obsazená jedním uzlem je 8 bajtů, tj. 4 bajty pro data a 4 bajty pro proměnnou ukazatele. Pokud se propojený seznam skládá ze 4 prvků, pak paměťový prostor obsazený propojeným seznamem bude:
webový ovladač
Paměťový prostor = 8*4 = 32 bajtů
Propojený seznam by byl lepší volbou, pokud je datová část větší. Předpokládejme, že data mají 16 bajtů. Paměťový prostor obsazený polem by byl 16*7=112 bajtů, zatímco propojený seznam zabírá 20*4=80, zde jsme zadali 20 bajtů jako 16 bajtů pro velikost dat plus 4 bajty pro proměnnou ukazatel. Pokud bychom zvolili větší velikost dat, pak by propojený seznam spotřeboval méně paměti; jinak to závisí na faktorech, které používáme k určení velikosti.
Podívejme se na rozdíly mezi polem a propojeným seznamem v tabulkové formě.
| Pole | Spojový seznam |
|---|---|
| Pole je kolekce prvků podobného datového typu. | Propojený seznam je kolekce objektů známých jako uzel, kde se uzel skládá ze dvou částí, tj. dat a adresy. |
| Prvky pole se ukládají do souvislého paměťového místa. | Prvky propojeného seznamu mohou být uloženy kdekoli v paměti nebo náhodně. |
| Pole pracuje se statickou pamětí. Zde statická paměť znamená, že velikost paměti je pevná a nelze ji za běhu měnit. | Propojený seznam pracuje s dynamickou pamětí. Dynamická paměť zde znamená, že velikost paměti může být změněna za běhu podle našich požadavků. |
| Prvky pole jsou na sobě nezávislé. | Prvky propojeného seznamu jsou na sobě závislé. Protože každý uzel obsahuje adresu dalšího uzlu, pro přístup k dalšímu uzlu potřebujeme přístup k jeho předchozímu uzlu. |
| Pole zabere více času při provádění jakékoli operace, jako je vkládání, mazání atd. | Propojený seznam zabere méně času při provádění jakékoli operace, jako je vkládání, mazání atd. |
| Přístup k jakémukoli prvku v poli je rychlejší, protože k prvku v poli lze přímo přistupovat prostřednictvím indexu. | Přístup k prvku v propojeném seznamu je pomalejší, protože začíná procházet od prvního prvku propojeného seznamu. |
| V případě pole je paměť alokována v době kompilace. | V případě propojeného seznamu je paměť alokována za běhu. |
| Využití paměti v poli je neefektivní. Pokud je například velikost pole 6 a pole se skládá pouze ze 3 prvků, zbytek prostoru bude nevyužit. | Využití paměti je efektivní v případě propojeného seznamu, protože paměť může být alokována nebo uvolněna za běhu podle našich požadavků. |