streamalism.org

1. Úvod

LinkedList je dvojnásobne prepojená implementácia zoznamu Zoznam a Deque rozhrania. Implementuje všetky voliteľné operácie so zoznamom a povoľuje všetky prvky (vrátane nulový).

2. Funkcie

Nižšie nájdete najdôležitejšie vlastnosti LinkedList:

• Operácie, ktoré indexujú do zoznamu, budú prechádzať zoznamom od začiatku alebo do konca, podľa toho, čo je bližšie k uvedenému indexu
• Nie je synchronizovaný
• Jeho Iterátor a ListIterator iterátory sú rýchle z hľadiska zlyhania (čo znamená, že po vytvorení iterátora, ak dôjde k zmene zoznamu, a ConcurrentModificationException bude vyhodený)
• Každý prvok je uzol, ktorý uchováva odkaz na nasledujúci a predchádzajúci
• Udržuje poradie vloženia

Hoci LinkedList nie je synchronizovaný, môžeme získať jeho synchronizovanú verziu zavolaním na Zbierky.synchronizovaný zoznam metóda, napríklad:

Zoznam zoznam = Collections.synchronizedList (nový LinkedList (...));

3. Porovnanie s ArrayList

Aj keď obaja implementujú Zoznam rozhranie, majú odlišnú sémantiku - čo určite ovplyvní rozhodnutie, ktorú z nich použiť.

3.1. Štruktúra

An ArrayList je indexová dátová štruktúra založená na Pole. Poskytuje náhodný prístup k svojim prvkom s výkonom rovnajúcim sa O (1).

Na druhej strane a LinkedList ukladá svoje údaje ako zoznam prvkov a každý prvok je prepojený s predchádzajúcim a nasledujúcim prvkom. V tomto prípade má operácia vyhľadávania položky čas vykonania rovný O (n).

3.2. Operácie

Operácie vloženia, pridania a vybratia položky sú rýchlejšie v a LinkedList pretože pri pridávaní prvku na ľubovoľné miesto v kolekcii nie je potrebné meniť veľkosť poľa alebo aktualizovať index, zmenia sa iba odkazy v okolitých prvkoch.

3.3. Využitie pamäte

A LinkedList spotrebúva viac pamäte ako ArrayList kvôli každému uzlu v a LinkedList ukladá dva odkazy, jeden pre svoj predchádzajúci prvok a jeden pre ďalší prvok, zatiaľ čo ArrayList uchováva iba údaje a ich index.

4. Použitie

Tu je niekoľko ukážok kódu, ktoré ukazujú, ako môžete použiť LinkedList:

4.1. Tvorba

LinkedList linkedList = nový LinkedList ();

4.2. Pridáva sa prvok

LinkedList náradie Zoznam a Deque rozhranie, okrem štandardu pridať () a pridať všetko() metódy, ktoré nájdete addFirst () a addLast (), ktorý pridáva prvok na začiatok alebo na koniec.

4.3. Odstraňuje sa prvok

Implementácia tohto zoznamu ponúka podobne ako pri pridávaní prvkov removeFirst () a removeLast ().

Existuje tiež pohodlná metóda removeFirstOccurence () a removeLastOccurence () ktorý vráti boolean (true, ak kolekcia obsahovala zadaný prvok).

4.4. Fronta operácií

Deque rozhranie poskytuje správanie podobné frontu (v skutočnosti Deque predlžuje Fronta rozhranie):

linkedList.poll (); linkedList.pop ();

Tieto metódy načítajú prvý prvok a odstránia ho zo zoznamu.

Rozdiel medzi anketa () a pop () je to tak pop bude hádzať NoSuchElementException () na prázdnom zozname, zatiaľ čo anketa vráti null. Rozhrania API pollFirst () a pollLast () sú tiež k dispozícii.

Tu je napríklad príklad, ako tam API funguje:

linkedList.push (Objekt o);

Ktorý vloží prvok ako hlavu kolekcie.

LinkedList má mnoho ďalších metód, z ktorých väčšinu by mal poznať už používaný používateľ Zoznamy. Ostatné, ktoré poskytuje Deque môže byť pohodlnou alternatívou k „štandardným“ metódam.

Celú dokumentáciu nájdete tu.

5. Záver

ArrayList je zvyčajne predvolené Zoznam implementácia.

Existujú však určité prípady použitia LinkedList bude lepšie vyhovovať, napríklad preferencie pre konštantný čas vkladania / mazania (napr. časté vkladanie / mazanie / aktualizácie), pred neustálym prístupovým časom a efektívnym využitím pamäte.

Ukážky kódu nájdete na GitHub.