streamalism.org

1. Prehľad

Pokiaľ ide o zbierky, štandardná knižnica Java poskytuje veľa možností na výber. Medzi týmito možnosťami sú dve známe Zoznam implementácie známe ako ArrayList a LinkedList, každý má svoje vlastné vlastnosti a prípady použitia.

V tomto tutoriále sa pozrieme na to, ako sú tieto dva nástroje skutočne implementované. Potom pre každú z nich vyhodnotíme rôzne aplikácie.

2. ArrayList

Interne, ArrayList používa pole na implementáciu Zoznam rozhranie. Pretože sú polia v Jave pevnej veľkosti, ArrayList vytvorí pole s určitou počiatočnou kapacitou. Ak v budúcnosti budete musieť uložiť viac položiek, ako je predvolená kapacita, nahradí toto pole novým a priestrannejším.

Aby sme lepšie porozumeli jej vlastnostiam, poďme vyhodnotiť túto dátovú štruktúru s ohľadom na jej tri hlavné operácie: pridanie položiek, získanie jednej pomocou indexu a odstránenie podľa indexu.

2.1. Pridať

Keď vytvárame prázdny ArrayList, inicializuje svoje podporné pole s predvolenou kapacitou (momentálne 10):

Pridanie novej položky, kým ešte nie je plné, je také jednoduché ako priradenie tejto položky k určitému indexu poľa. Tento index poľa je určený aktuálnou veľkosťou poľa, pretože sa prakticky pripájame k zoznamu:

backingArray [veľkosť] = nová položka; veľkosť ++;

Takže v najlepších a priemerných prípadoch je časová zložitosť pre operáciu pridania O (1), čo je dosť rýchle. Keď sa podporné pole zaplní, implementácia add sa stane menej efektívnym:

Ak chcete pridať novú položku, mali by sme najskôr inicializovať úplne nové pole s väčšou kapacitou a skopírovať všetky existujúce položky do nového poľa. Až po skopírovaní aktuálnych prvkov môžeme pridať novú položku. Z tohto dôvodu je časová zložitosť O (n) v najhoršom prípade, pretože musíme kopírovať n prvky ako prvé.

Teoreticky vzaté, pridanie nového prvku beží v amortizovanom konštantnom čase. Teda pridanie n prvky vyžaduje O (n) čas. Niektoré jednotlivé doplnky však môžu mať z dôvodu réžie kopírovania slabý výkon.

2.2. Prístup podľa indexu

Prístup k položkám podľa ich indexov je tam, kde ArrayList naozaj svieti. Načítanie položky v indexe ja, musíme len vrátiť položku s bydliskom v i index z podporného poľa. V dôsledku toho časová zložitosť prístupu pomocou indexovej operácie je vždy O (1).

2.3. Odstrániť podľa indexu

Predpokladajme, že odstránime index 6 z nášho ArrayList, čo zodpovedá prvku 15 v našom podpornom poli:

Po označení požadovaného prvku ako odstráneného by sme mali všetky prvky po ňom presunúť späť o jeden index. Je zrejmé, že čím je prvok bližšie k začiatku poľa, tým viac prvkov by sme mali presunúť. Časová zložitosť teda je O (1) v lepšom prípade a O (n) v priemere a najhorších prípadoch.

2.4. Aplikácie a obmedzenia

Zvyčajne ArrayList je predvolená voľba pre mnohých vývojárov, keď potrebujú Zoznam implementácia. V skutočnosti je to vlastne rozumná voľba, keď je počet prečítaní oveľa väčší ako počet zápisov.

Niekedy potrebujeme rovnako časté čítanie a písanie. Ak máme odhad maximálneho počtu možných položiek, potom to ešte má zmysel použiť ArrayList. Ak je to tak, môžeme inicializovať ArrayList s počiatočnou kapacitou:

int possibleUpperBound = 10_000; Zoznam položiek = nový ArrayList (possibleUpperBound);

Tento odhad môže zabrániť množstvu zbytočného kopírovania a prideľovaniu polí.

Navyše, polia sú indexované pomocou int hodnoty v Jave. Nie je teda možné uložiť viac ako 232 prvky v poli Java a následne v ArrayList.

3. LinkedList

LinkedList, ako naznačuje jeho názov, používa kolekciu prepojených uzlov na ukladanie a načítanie prvkov. Napríklad takto vyzerá implementácia Java po pridaní štyroch prvkov:

Každý uzol obsahuje dva ukazovatele: jeden smerujúci na ďalší prvok a druhý odkazujúci na predchádzajúci prvok. Tento zoznam, ktorý je rozšírený dvakrát, má dva ukazovatele smerujúce na prvú a poslednú položku.

Znova hodnotíme túto implementáciu s ohľadom na rovnaké základné operácie.

3.1. Pridať

Ak chcete pridať nový uzol, mali by sme najskôr prepojiť aktuálny posledný uzol s novým uzlom:

A potom aktualizujte posledný ukazovateľ:

Pretože obe tieto operácie sú triviálne, časová zložitosť operácie pridania je vždy O (1).

3.2. Prístup podľa indexu

LinkedList, oproti ArrayList, nepodporuje rýchly náhodný prístup. Aby sme teda našli prvok podľa indexu, mali by sme prejsť niektorú časť zoznamuručne.

V najlepšom prípade, keď je požadovaná položka blízko začiatku alebo konca zoznamu, časová zložitosť bude rovnako rýchla ako O (1). V priemerných a najhorších scenároch však môžeme skončiť s O (n) čas prístupu, pretože musíme skúmať veľa uzlov jeden za druhým.

3.3. Odstrániť podľa indexu

Aby sme mohli položku odstrániť, mali by sme najskôr nájsť požadovanú položku a potom ju zo zoznamu odpojiť. Následne čas prístupu určuje časovú zložitosť - to znamená O (1) v lepšom prípade a O (n) v priemere a v najhorších scenároch.

3.4. Aplikácie

LinkedLists sú vhodnejšie, keď je rýchlosť pridávania oveľa vyššia ako rýchlosť čítania.

Môže sa tiež použiť v scenároch náročných na čítanie, keď väčšinu času chceme prvý alebo posledný prvok. Za zmienku to stojí LinkedList tiež implementuje Deque rozhranie - podpora efektívneho prístupu k obom koncom zbierky.

Všeobecne platí, že ak poznáme ich implementačné rozdiely, mohli by sme si ľahko vybrať jeden pre konkrétny prípad použitia.

Povedzme napríklad, že budeme ukladať veľa udalostí časových radov do dátovej štruktúry podobnej zoznamu. Vieme, že každú sekundu budeme dostávať výbuchy udalostí.

Tiež musíme pravidelne skúmať všetky udalosti jeden po druhom a poskytovať určité štatistiky. Pre tento prípad použitia LinkedList je lepšia voľba, pretože rýchlosť pridávania je oveľa vyššia ako rýchlosť čítania.

Tiež by sme prečítali všetky položky, takže nemôžeme poraziť O (n) Horná hranica.

4. Záver

V tomto tutoriáli sme sa najskôr ponorili do toho, ako na to ArrayList a Zoznamy odkazov sú implementované v Jave.

Pre každý z nich sme tiež vyhodnotili rôzne prípady použitia.