Rozdíl mezi seznamem polí a propojeným seznamem

Jak jsou data ukládána?

Seznam polí a propojený seznam jsou běžné pojmy, pokud jde o ukládání a vyhledávání dat. Ačkoli existuje spousta úložných zařízení, v konečném důsledku závisí na úložném mechanismu. Tyto dva mechanismy ukládání ukládají vaše data do úložných zařízení a v případě potřeby je načítají. Pojďme se podívat, jak ukládají data do své paměti. Seznam polí používá sekvenční úložiště a části dat se ukládají jeden po druhém. Toto je snad jednodušší forma skladování - vyhýbá se zmatkům. Ano, můžeme načíst další položku nebo data z dalšího umístění paměti seznamu polí; uloží se však pomocí ukazatelů v propojeném seznamu. Zde potřebujeme dvě paměťová místa pro uložení - jedno pro data, druhé pro ukazatel. Ukazatel řeší umístění paměti dalších dat. Můžeme snadno pochopit, že propojený seznam nikdy neukládá data postupně; spíše používá mechanismus náhodného ukládání. Ukazatele jsou klíčové prvky při hledání umístění dat v paměti.

Dynamické pole a propojený seznam

Již jsme diskutovali o tom, jak oba ukládací mechanismy vkládají data, a můžeme definovat termín „dynamické pole“ pro schéma interního úložiště seznamu polí. Pouze vloží datové kusy jeden po druhý - odtud název - zatímco propojený seznam používá interní seznam pomocí ukazatelů ke sledování další položky. Proto používá interní propojený seznam, jako například jednoduše nebo dvojitě propojený seznam, aby nám ukázal další data.

Využití paměti

Protože seznam Array ukládá pouze skutečná data, potřebujeme místo pouze pro data, která ukládáme. Naopak v seznamu Propojení používáme také ukazatele. Proto jsou vyžadována dvě paměťová místa a můžeme říci, že propojený seznam spotřebovává více paměti než seznam Array. Výhodou stránky propojeného seznamu je to, že nikdy nevyžaduje nepřetržitá paměťová místa k ukládání našich dat, na rozdíl od seznamu polí. Ukazatele jsou schopny držet pozici dalšího datového umístění a můžeme dokonce použít menší paměťové sloty, které nejsou spojité. Pokud jde o využití paměti, hrají hlavní roli v propojeném seznamu ukazatele a také jejich účinnost.

Velikost počátečního seznamu polí a propojeného seznamu

Se seznamem polí vyžaduje i prázdný seznam velikost 10, ale u propojeného seznamu nepotřebujeme takový obrovský prostor. Můžeme vytvořit prázdný propojený seznam o velikosti 0. Později můžeme velikost podle potřeby zvětšit.

Získání dat

Získávání dat je v seznamu polí jednodušší, protože se ukládá postupně. Vše, co dělá, je identifikovat první umístění dat; odtud se k dalšímu místu přistupuje postupně, aby se získal zbytek. Vypočítá se jako první datová pozice + 'n', kde 'n' je pořadí dat v seznamu polí. Seznam Propojené odkazuje na počáteční ukazatel pro nalezení prvního umístění dat a odtud odkazuje na ukazatel přiřazený každému datu k nalezení dalšího umístění dat. Proces vyhledávání závisí hlavně na ukazatelích zde a efektivně nám ukazují další umístění dat.

Konec dat

Seznam Array používá k označení konce dat nulovou hodnotu, zatímco Propojený seznam používá pro tento účel nulový ukazatel. Jakmile systém rozpozná nulová data, seznam polí zastaví další načítání dat. Podobně nulový ukazatel zastaví systém z přechodu k dalšímu získávání dat.

Reverzní Traversal

Propojený seznam nám umožňuje pojíždět v opačných směrech pomocí sestupného nástroje (). Nemáme však takové zařízení v seznamu polí - zpětný průchod se zde stává problémem.

Syntax

Podívejme se na syntaxi Java obou mechanismů úložiště.

Vytvoření seznamu polí:

List arraylistsample = new ArrayList ();

Přidávání objektů do seznamu polí:

Arraylistsample.add („name1“);

Arraylistsample.add („name2“);

Takto bude výsledný seznam polí vypadat - [name1, name2].

Vytvoření propojeného seznamu:

List linkedlistsample = new linkedList ();

Přidávání objektů do propojeného seznamu:

Linkedlistsample.add („name3“);

Linkedlistsample.add („name4“);

Takto bude vypadat výsledný propojený seznam - [name3, name4].

 Což je lepší pro operaci Get nebo Search?

Seznam polí vyžaduje O (1) čas pro spuštění jakéhokoli vyhledávání dat, zatímco propojený seznam trvá u O (n) pro n^tis vyhledávání dat. Seznam polí proto vždy používá pro libovolné vyhledávání dat konstantní čas, ale ve propojeném seznamu závisí čas na poloze dat. Seznamy polí jsou proto vždy lepší volbou pro operace Get nebo Search.

Což je lepší pro operaci vkládání nebo přidávání?

Seznam polí i propojený seznam zabere O (1) čas pro přidání dat. Ale pokud je pole plné, pak seznam polí trvá značné množství času, než se změní jeho velikost a zkopírují se položky na novější. V takovém případě je lepším výběrem odkazovaný seznam.

Což je pro operaci odebrání lepší?

Operace odebrání zabere téměř stejné množství času v seznamu polí i propojeném seznamu. V seznamu Array tato operace vymaže data a posune polohu dat tak, aby vytvořila novější pole - zabere to čas O (n). V seznamu Propojená tato operace přejde k určitým datům a změní polohu ukazatele tak, aby vytvořila novější seznam. Čas pro průchod a odstranění je zde také O (n).

Což je rychlejší?

Víme, že seznam polí používá interní pole k ukládání skutečných dat. Proto pokud jsou některá data vymazána, pak všechna nadcházející data potřebují posun paměti. To samozřejmě vyžaduje značné množství času a zpomaluje věci. Takový posun paměti není vyžadován v seznamu Propojený, protože vše, co dělá, je změnit umístění ukazatele. Propojený seznam je proto rychlejší než seznam Array v jakémkoli druhu ukládání dat. To je však čistě závislé na typu operace, tj. Pro operaci Get nebo Search trvá propojený seznam mnohem více času než seznam Array. Když se podíváme na celkový výkon, můžeme říci, že propojený seznam je rychlejší.

Kdy použít seznam polí a propojený seznam?

Seznam polí se nejlépe hodí pro menší požadavky na data, kde je k dispozici nepřetržitá paměť. Ale když se zabýváme obrovským množstvím dat, dostupnost nepřetržité paměti implementuje mechanismy ukládání dat, ať už jsou malé nebo velké. Dále se rozhodněte, který z nich si vyberete - seznam polí nebo propojený seznam. Pokud potřebujete pouze ukládat a získávat data, můžete pokračovat se seznamem polí. Seznam vám však může pomoci s manipulací s daty. Jakmile se rozhodnete, jak často je třeba s daty manipulovat, je důležité zkontrolovat, jaký typ načítání dat obvykle provádíte. Když je to jen Get nebo Search, pak Array List je lepší volba; pro další operace, jako je vložení nebo odstranění, pokračujte seznamem propojených.

Podívejme se na rozdíly v tabulkové formě.

S. Ne	Koncepty	Rozdíly
		Seznam polí	Spojový seznam
1	Móda ukládání dat	Používá sekvenční ukládání dat	Používá nesekvenční ukládání dat
2	Schéma interního úložiště	Udržuje vnitřní dynamické pole	Udržuje propojený seznam
3	Využití paměti	Vyžaduje paměťový prostor jen pro data	Vyžaduje paměťový prostor pro data i pro ukazatele
4	Velikost počátečního seznamu	Potřebuje místo pro nejméně 10 položek	Nepotřebuje místo a můžeme dokonce vytvořit prázdný propojený seznam velikosti 0.
5	Získání dat	Vypočítá se jako první datová pozice + 'n', kde 'n' je pořadí dat v seznamu polí	Je vyžadován přechod od prvního nebo posledního do požadovaných dat
6	Konec dat	Hodnoty Null označují konec	Null Ukazatel označuje konec
7	Reverzní Traversal	To neumožňuje	Umožňuje to pomocí sestupného nástroje ()
8	Syntaxe vytvoření seznamu	List arraylistsample = new ArrayList ();	List linkedlistsample = new linkedList ();
9	Přidávání objektů	Arraylistsample.add („name1“);	Linkedlistsample.add („name3“);
10	Získejte nebo hledejte	Trvá O (1) čas a má lepší výkon	Trvá O (n) čas a výkon závisí na poloze dat
11	Vložit nebo přidat	Spotřebuje čas O (1) s výjimkou případů, kdy je pole plné	Spotřeba O (1) času za všech okolností
12	Odstranění nebo odstranění	Trvá O (n) čas	Trvá O (n) čas
13	Kdy použít?	Když je spousta operací Get nebo Search; dostupnost paměti by měla být ještě na začátku vyšší	Pokud existuje mnoho operací Vložit nebo Odstranit a dostupnost paměti nemusí být nepřetržitá