Rozdiel medzi zoznamom polí a prepojeným zoznamom

Ako sa ukladajú údaje?

Zoznam polí a prepojený zoznam sú bežné pojmy, pokiaľ ide o ukladanie a získavanie údajov. Aj keď existuje veľa úložných zariadení, v konečnom dôsledku závisia od mechanizmu úložiska. Tieto dva mechanizmy ukladania údajov ukladajú vaše údaje do úložných zariadení av prípade potreby ich získavajú. Pozrime sa, ako ukladajú údaje do svojej pamäte. Zoznam polí používa postupné ukladanie a kusy údajov sa ukladajú jeden po druhom. Toto je možno jednoduchšia forma ukladania - nedochádza k zámene. Áno, môžeme načítať ďalšiu položku alebo údaje z nasledujúceho pamäťového umiestnenia v zozname polí; uloží sa však pomocou ukazovateľov v zozname Prepojené. Tu potrebujeme dve pamäťové miesta na uloženie - jedno pre dáta a druhé pre ukazovateľ. Ukazovateľ adresuje miesto v pamäti ďalších údajov. Môžeme ľahko pochopiť, že prepojený zoznam nikdy neukladá údaje postupne; skôr používa mechanizmus náhodného ukladania. Ukazovatele sú kľúčovými prvkami pri vyhľadávaní umiestnení údajov v pamäti.

Dynamické pole a prepojený zoznam

Už sme diskutovali o tom, ako oba mechanizmy ukladania údajov vkladajú údaje, a môžeme definovať pojem „dynamické pole“ pre schému interného ukladania zoznamu polí. Jednoducho vkladá dátové kúsky za sebou - odtiaľ názov - zatiaľ čo Zoznam Prepojených používa interný zoznam pomocou ukazovateľov na sledovanie ďalšej položky. Preto používa interný prepojený zoznam, ako napríklad jednoducho alebo dvojnásobne prepojený zoznam, aby nám ukázal ďalšie údaje.

Využitie pamäte

Pretože zoznam Array ukladá iba skutočné údaje, potrebujeme miesto iba pre ukladané údaje. Naopak, v zozname Prepojené používame tiež ukazovatele. Preto sú potrebné dve pamäťové miesta a môžeme povedať, že prepojený zoznam spotrebuje viac pamäte ako zoznam Array. Výhodou stránky Prepojeného zoznamu je to, že na ukladanie našich údajov na rozdiel od zoznamu polí nikdy nevyžaduje trvalé miesta v pamäti. Ukazovatele sú schopné udržať pozíciu nasledujúceho dátového umiestnenia a môžeme dokonca použiť menšie pamäťové sloty, ktoré nie sú súvislé. Pokiaľ ide o využitie pamäte, ukazovatele hrajú hlavnú úlohu v zozname Prepojené a rovnako tak aj ich účinnosť.

Veľkosť počiatočného zoznamu polí a prepojeného zoznamu

V prípade zoznamu polí si vyžaduje aj prázdny zoznam veľkosť 10, ale v prípade prepojeného zoznamu nepotrebujeme taký obrovský priestor. Môžeme vytvoriť prázdny prepojený zoznam s veľkosťou 0. Neskôr môžeme veľkosť podľa potreby zväčšiť.

Získavanie údajov

Získavanie údajov je v zozname polí jednoduchšie, pretože sa ukladá postupne. Všetko, čo robí, je identifikovať prvé umiestnenie údajov; odtiaľ je prístup k ďalšiemu miestu postupne, aby sa získal zvyšok. Vypočíta sa ako prvá dátová pozícia + 'n', kde 'n' je poradie údajov v zozname polí. Prepojený zoznam odkazuje na počiatočný ukazovateľ na nájdenie prvého údajového umiestnenia a odtiaľ odkazuje na ukazovateľ spojený s každým údajom na nájdenie nasledujúceho údajového umiestnenia. Proces získavania údajov závisí predovšetkým od ukazovateľov, ktoré nám efektívne ukazujú ďalšie umiestnenie údajov.

Koniec údajov

Zoznam polí používa nulovú hodnotu na označenie konca údajov, zatiaľ čo zoznam prepojených používa na tento účel nulový ukazovateľ. Akonáhle systém rozpozná nulové údaje, zoznam polí zastaví ďalšie získavanie údajov. Podobným spôsobom nulový ukazovateľ zastaví systém z pokračovania k ďalšiemu vyhľadávaniu údajov.

Spätný prechod

Prepojený zoznam nám umožňuje prechádzať v opačných smeroch pomocou nástroja na klesanie (). Nemáme však také zariadenie v zozname polí - spätný prechod sa tu stáva problémom.

syntax

Pozrime sa na syntax Java oboch mechanizmov úložiska.

Vytvorenie zoznamu polí:

Zoznam arraylistsample = new ArrayList ();

Pridávanie objektov do zoznamu polí:

Arraylistsample.add ( "NAME1");

Arraylistsample.add ( "meno2");

Takto bude vyzerať výsledný zoznam polí - [name1, name2].

Vytvorenie prepojeného zoznamu:

List linkedlistsample = new linkedList ();

Pridávanie objektov do prepojeného zoznamu:

Linkedlistsample.add ( "meno3");

Linkedlistsample.add ( "NAME4");

Takto bude vyzerať výsledný zoznam prepojení - [name3, name4].

 Čo je lepšie pre operáciu Get alebo Search?

Zoznam polí vyžaduje O (1) čas na spustenie akéhokoľvek vyhľadávania údajov, zatiaľ čo prepojený zoznam trvá u O (n) pre n^th vyhľadávanie údajov. Preto zoznam polí vždy používa konštantný čas pre akékoľvek vyhľadávanie dát, ale v zozname prepojení, potrebný čas závisí od polohy údajov. Zoznamy polí sú preto vždy lepšou voľbou pre operácie získavania alebo vyhľadávania.

Čo je lepšie pre operáciu vkladania alebo pridávania?

Zoznam polí aj prepojený zoznam zaberajú O (1) čas na pridanie údajov. Ak je však pole plné, zoznam polí si vyžaduje značné množstvo času na jeho zmenu veľkosti a kopírovanie položiek na novšiu. V takom prípade je lepšou voľbou prepojený zoznam.

Čo je lepšie pre operáciu odstránenia?

Operácia odstránenia trvá takmer rovnako dlhý čas v zozname polí aj v zozname prepojení. V zozname polí táto operácia vymaže údaje a potom posunie polohu údajov, aby vytvorila novšie pole - zaberie to čas O (n). V zozname Prepojená táto operácia prejde na konkrétne údaje a zmení polohu ukazovateľa na novší zoznam. Čas na prechod a odstránenie je tu tiež O (n).

Čo je rýchlejšie?

Vieme, že zoznam polí používa interné pole na ukladanie skutočných údajov. Preto, ak sú nejaké dáta vymazané, potom všetky nasledujúce dáta potrebujú posun pamäte. Je zrejmé, že to vyžaduje značné množstvo času a spomaľuje veci. Takýto posun pamäte nie je potrebný v zozname Prepojené, pretože iba zmení umiestnenie ukazovateľa. Prepojený zoznam je preto rýchlejší ako zoznam polí v akomkoľvek druhu ukladania údajov. To je však čisto závislé od typu operácie, t. J. Pri operácii Získať alebo Vyhľadať trvá Prepojený zoznam oveľa viac času ako Zoznam polí. Keď sa pozrieme na celkový výkon, môžeme povedať, že prepojený zoznam je rýchlejší.

Kedy použiť zoznam polí a prepojený zoznam?

Zoznam polí je najvhodnejší pre menšie požiadavky na dáta, keď je k dispozícii nepretržitá pamäť. Keď však pracujeme s obrovským množstvom údajov, dostupnosť nepretržitej pamäte implementuje mechanizmy ukladania údajov, či už sú malé alebo veľké. Potom sa rozhodnite, ktorý z nich si vyberiete - zoznam polí alebo zoznam prepojení. Ak potrebujete ukladať a získavať údaje, môžete pokračovať v zozname polí. Zoznam vám však môže pomôcť pri manipulácii s údajmi. Keď sa rozhodnete, ako často sa vyžaduje manipulácia s údajmi, je dôležité skontrolovať, aký typ získavania údajov zvyčajne vykonávate. Ak je to len vyhľadávanie alebo vyhľadávanie, potom je lepšou voľbou zoznam polí; pri ďalších operáciách, ako je vkladanie alebo mazanie, pokračujte zoznamom prepojení.

Pozrime sa na rozdiely v tabuľkovej podobe.

S.No	koncepty	rozdiely
		Zoznam polí	Prepojený zoznam
1	Móda ukladania údajov	Používa sekvenčné ukladanie údajov	Používa nesekvenčné ukladanie údajov
2	Schéma interného ukladania	Zachováva internú dynamickú sústavu	Udržuje prepojený zoznam
3	Využitie pamäte	Vyžaduje pamäťový priestor len pre dáta	Vyžaduje pamäťový priestor pre dáta, ako aj pre ukazovatele
4	Veľkosť úvodného zoznamu	Potrebuje priestor pre najmenej 10 položiek	Nepotrebuje miesto a môžeme dokonca vytvoriť prázdny prepojený zoznam veľkosti 0.
5	Získavanie údajov	Vypočíta sa ako prvá dátová pozícia + 'n', kde 'n' je poradie údajov v zozname polí	Vyžaduje sa prechod od prvého alebo posledného do požadovaných údajov
6	Koniec údajov	Hodnoty Null označujú koniec	Null Ukazovateľ označuje koniec
7	Spätný prechod	Nepovoľuje to	Umožňuje to pomocou oddeľovača ()
8	Syntax vytvorenia zoznamu	Zoznam arraylistsample = new ArrayList ();	List linkedlistsample = new linkedList ();
9	Pridávanie objektov	Arraylistsample.add ( "NAME1");	Linkedlistsample.add ( "meno3");
10	Získajte alebo vyhľadajte	Trvá O (1) čas a má lepšiu výkonnosť	Trvá O (n) čas a výkonnosť závisí od polohy údajov
11	Vložiť alebo pridať	Spotrebuje čas O (1) okrem prípadu, keď je pole plné	Spotrebuje O (1) čas za všetkých okolností
12	Vymazanie alebo odstránenie	Trvá O (n) čas	Trvá O (n) čas
13	Kedy použiť?	Keď je zapojených veľa operácií Get alebo Search; dostupnosť pamäte by mala byť vyššia aj na začiatku	Ak existuje veľa operácií vloženia alebo odstránenia a dostupnosť pamäte nemusí byť nepretržitá