Pole a Prepojený zoznam sú dva spôsoby usporiadania údajov v pamäti. Pred pochopením rozdielov medzi Pole a Prepojený zoznam , najprv sa pozrieme v poli a prepojený zoznam .
program v jave
Čo je pole?
Dátová štruktúra, ktorá obsahuje prvky rovnakého typu. Štruktúra údajov je spôsob organizácie údajov; pole je dátová štruktúra, pretože sekvenčne organizuje dáta. Pole je veľký kus pamäte, v ktorom je pamäť rozdelená na malé-malé bloky a každý blok je schopný uložiť nejakú hodnotu.
Predpokladajme, že sme vytvorili pole, ktoré pozostáva z 10 hodnôt, potom každý blok uloží hodnotu typu celé číslo. Ak sa pokúsime uložiť hodnotu do poľa rôznych typov, potom to nie je správne pole a vyvolá chybu pri kompilácii.
Vyhlásenie poľa
Pole môže byť deklarované ako:
data_type name of the array[no of elements]
Ak chcete deklarovať pole, najprv musíme zadať typ poľa a potom názov poľa. Vo vnútri hranatých zátvoriek musíme zadať počet prvkov, ktoré má naše pole obsahovať.
Poďme to pochopiť na príklade.
int a[5];
Vo vyššie uvedenom prípade sme deklarovali pole 5 prvkov s ' a ' meno an celé číslo Dátový typ.
Čo je prepojený zoznam?
Prepojený zoznam je kolekcia uzlov, ktoré sú náhodne uložené. Každý uzol pozostáva z dvoch polí, tj. údajov a odkaz . Údaje sú tu hodnotou uloženou v tomto konkrétnom uzle a odkaz je ukazovateľ, ktorý obsahuje adresu nasledujúceho uzla.
čo je špeciálny znak
Rozdiely medzi Array a Linked zoznamom
Nemôžeme povedať, ktorá dátová štruktúra je lepšia, t.j. pole alebo prepojený zoznam . Môže existovať možnosť, že jedna dátová štruktúra je lepšia pre jeden druh požiadavky, zatiaľ čo druhá dátová štruktúra je lepšia pre iný druh požiadavky. Existujú rôzne faktory, ako sú časté operácie vykonávané s dátovou štruktúrou alebo veľkosť dát a ďalšie faktory, na základe ktorých sa vyberá dátová štruktúra. Teraz uvidíme niektoré rozdiely medzi poľom a prepojeným zoznamom na základe niektorých parametrov.
1. Náklady na prístup k prvku
V prípade poľa, bez ohľadu na veľkosť poľa, pole potrebuje konštantný čas na prístup k prvku. V poli sú prvky uložené súvislým spôsobom, takže ak poznáme základnú adresu prvku, potom môžeme ľahko získať adresu akéhokoľvek prvku v poli. Potrebujeme vykonať jednoduchý výpočet, aby sme získali adresu ľubovoľného prvku v poli. Takže prístup k prvku v poli je O(1) z hľadiska časovej náročnosti.
V prepojenom zozname nie sú prvky uložené súvislým spôsobom. Pozostáva z viacerých blokov a každý blok je reprezentovaný ako uzol. Každý uzol má dve polia, t.j. jedno je pre dátové pole a druhé ukladá adresu ďalšieho uzla. Aby sme našli akýkoľvek uzol v prepojenom zozname, musíme najprv určiť prvý uzol známy ako hlavný uzol. Ak musíme nájsť druhý uzol v zozname, musíme prejsť od prvého uzla av najhoršom prípade, aby sme našli posledný uzol, prejdeme všetky uzly. Priemerný prípad prístupu k prvku je O(n).
Dospeli sme k záveru, že náklady na prístup k prvku v poli sú nižšie ako k prepojenému zoznamu. Ak teda máme nejakú požiadavku na prístup k prvkom, lepšou voľbou je pole.
2. Náklady na vloženie prvku
Pri vkladaní môžu existovať tri scenáre:
V prípade prepojeného zoznamu na vloženie prvku na začiatok prepojeného zoznamu vytvoríme nový uzol a adresa prvého uzla sa pridá k novému uzlu. Týmto spôsobom sa nový uzol stane prvým uzlom. Časová zložitosť teda nie je úmerná veľkosti zoznamu. Časová zložitosť by bola konštantná, t.j. O(1).
Ak pole nie je plné, môžeme nový prvok pridať priamo cez index. V tomto prípade by časová zložitosť bola konštantná, t.j. O(1). Ak je pole plné, najprv musíme pole skopírovať do iného poľa a pridať nový prvok. V tomto prípade by časová zložitosť bola O(n).
Aby sme vložili prvok na koniec prepojeného zoznamu, musíme prejsť celým zoznamom. Ak prepojený zoznam pozostáva z n prvkov, potom by časová zložitosť bola O(n).
Predpokladajme, že chceme vložiť prvok na ithpoloha poľa; musíme posunúť n/2 prvkov doprava. Preto je časová zložitosť úmerná počtu prvkov. Časová zložitosť by bola O(n) pre priemerný prípad.
koľko filmov s nemožnými úlohami existuje
V prípade prepojeného zoznamu musíme prejsť na pozíciu, do ktorej musíme vložiť nový prvok. Aj keď nemusíme vykonávať žiadne radenie, ale musíme prejsť do polohy n/2. Čas je úmerný počtu n prvkov a časová zložitosť pre priemerný prípad by bola O(n).
Výsledný prepojený zoznam je:
Implementácia poľa je v porovnaní s prepojeným zoznamom jednoduchá. Pri vytváraní programu pomocou prepojeného zoznamu je program náchylnejší na chyby, ako je chyba segmentácie alebo únik pamäte. Takže pri vytváraní programu v prepojenom zozname je potrebné venovať veľkú pozornosť.
Prepojený zoznam má dynamickú veľkosť, zatiaľ čo pole je statické. Tu statický neznamená, že nemôžeme určiť veľkosť v čase spustenia, ale nemôžeme ju zmeniť, keď sa už o veľkosti rozhodne.
3. Požiadavky na pamäť
Tak ako sa prvky v poli ukladajú do jedného súvislého bloku pamäte, pole má pevnú veľkosť. Predpokladajme, že máme pole veľkosti 7 a pole pozostáva zo 4 prvkov, potom je zvyšok priestoru nevyužitý. Pamäť obsadená 7 prvkami:
Pamäťový priestor = 7*4 = 28 bajtov
Kde 7 je počet prvkov v poli a 4 je počet bajtov celočíselného typu.
V prípade prepojeného zoznamu nie je žiadna nevyužitá pamäť, ale extra pamäť je obsadená premennými ukazovateľa. Ak sú dáta celočíselného typu, potom celková pamäť obsadená jedným uzlom je 8 bajtov, t.j. 4 bajty pre dáta a 4 bajty pre premennú ukazovateľa. Ak sa prepojený zoznam skladá zo 4 prvkov, pamäťový priestor zaberaný prepojeným zoznamom bude:
webový ovládač
Pamäťový priestor = 8*4 = 32 bajtov
Prepojený zoznam by bol lepšou voľbou, ak je dátová časť väčšia. Predpokladajme, že údaje majú 16 bajtov. Pamäťový priestor, ktorý zaberá pole, by bol 16*7=112 bajtov, zatiaľ čo prepojený zoznam zaberá 20*4=80, tu sme zadali 20 bajtov ako 16 bajtov pre veľkosť údajov plus 4 bajty pre premennú ukazovateľ. Ak zvolíme väčšiu veľkosť údajov, prepojený zoznam by spotreboval menej pamäte; inak to závisí od faktorov, ktoré používame na určenie veľkosti.
Pozrime sa na rozdiely medzi poľom a prepojeným zoznamom v tabuľkovej forme.
| Pole | Prepojený zoznam |
|---|---|
| Pole je súbor prvkov podobného typu údajov. | Prepojený zoznam je kolekcia objektov známych ako uzol, kde uzol pozostáva z dvoch častí, t. j. údajov a adresy. |
| Prvky poľa sa ukladajú do súvislého pamäťového miesta. | Prepojené prvky zoznamu môžu byť uložené kdekoľvek v pamäti alebo náhodne uložené. |
| Pole pracuje so statickou pamäťou. Statická pamäť tu znamená, že veľkosť pamäte je pevná a nemožno ju počas behu meniť. | Prepojený zoznam pracuje s dynamickou pamäťou. Dynamická pamäť tu znamená, že veľkosť pamäte môže byť zmenená za behu podľa našich požiadaviek. |
| Prvky poľa sú navzájom nezávislé. | Prvky prepojeného zoznamu sú na sebe závislé. Keďže každý uzol obsahuje adresu nasledujúceho uzla, na prístup k ďalšiemu uzlu potrebujeme prístup k jeho predchádzajúcemu uzlu. |
| Pole trvá viac času pri vykonávaní akejkoľvek operácie, ako je vkladanie, mazanie atď. | Prepojený zoznam trvá menej času pri vykonávaní akejkoľvek operácie, ako je vkladanie, mazanie atď. |
| Prístup k akémukoľvek prvku v poli je rýchlejší, pretože k prvku v poli možno pristupovať priamo cez index. | Prístup k prvku v prepojenom zozname je pomalší, pretože začína prechádzať od prvého prvku prepojeného zoznamu. |
| V prípade poľa je pamäť alokovaná v čase kompilácie. | V prípade prepojeného zoznamu sa pamäť prideľuje v čase spustenia. |
| Využitie pamäte v poli je neefektívne. Napríklad, ak je veľkosť poľa 6 a pole pozostáva iba z 3 prvkov, zvyšok priestoru bude nevyužitý. | Využitie pamäte je efektívne v prípade prepojeného zoznamu, pretože pamäť môže byť pridelená alebo uvoľnená v čase behu podľa našej požiadavky. |