streamalism.org

1. Bemutatkozás

LinkedList egy kétszeresen összekapcsolt lista megvalósítása a Lista és Deque interfészek. Végrehajtja az összes opcionális listaműveletet és engedélyezi az összes elemet (beleértve a nulla).

2. Jellemzők

Az alábbiakban megtalálja a LinkedList:

• A listába indexelő műveletek a listát elejétől vagy végétől fogják végigjárni, attól függően, hogy melyik áll közelebb a megadott indexhez
• Nincs szinkronizálva
• Az Iterátor és ListIterator az iterátorok hibamentesek (ami azt jelenti, hogy az iterátor létrehozása után, ha a lista módosul, a ConcurrentModificationException eldobják)
• Minden elem egy csomópont, amely megőrzi a következő és az előző hivatkozásokat
• Fenntartja a beszúrási sorrendet

Habár LinkedList nincs szinkronizálva, a szinkronizált verzióját a Collections.synchronizedList módszer, például:

Lista lista = Collections.synchronizedList (új LinkedList (...));

3. Összehasonlítás a Tömb lista

Bár mindketten végrehajtják a Lista interfész, különböző szemantikájuk van - ami határozottan befolyásolja a döntést, hogy melyiket használja.

3.1. Szerkezet

An Tömb lista egy index alapú adatszerkezet, amelyet egy Sor. Véletlenszerű hozzáférést biztosít elemeihez, O (1) értékkel megegyező teljesítménnyel.

Másrészt a LinkedList adatait elemek listájaként tárolja, és minden elem kapcsolódik az előző és a következő elemhez. Ebben az esetben az elem keresési műveletének végrehajtási ideje egyenlő O (n).

3.2. Tevékenységek

Egy elem beillesztési, hozzáadási és eltávolítási műveletei gyorsabbak a LinkedList mivel nincs szükség egy tömb átméretezésére vagy az index frissítésére, amikor egy elemet hozzáadunk valamilyen tetszőleges pozícióhoz a gyűjtemény belsejében, csak a környező elemek hivatkozásai változnak.

3.3. Memóriahasználat

A LinkedList több memóriát fogyaszt, mint egy Tömb lista a csomópontok miatt LinkedList két referenciát tárol, egyet az előző elemére és egyet a következő elemére, míg a Tömb lista csak az adatokat és azok indexét tárolja.

4. Használat

Íme néhány kódminta, amelyek bemutatják, hogyan használhatja LinkedList:

4.1. Teremtés

LinkedList linkedList = új LinkedList ();

4.2. Elem hozzáadása

LinkedList megvalósítja Lista és Deque interfész, a standard mellett add () és az összes hozzáadása() módszereket találhat addFirst () és addLast (), amely egy elemet ad hozzá az elejéhez vagy a végéhez, ill.

4.3. Elem eltávolítása

Az elemek hozzáadásához hasonlóan ez a lista megvalósítása is kínál removeFirst () és removeLast ().

Ezenkívül van egy kényelmes módszer removeFirstOccurence () és removeLastOccurence () amely logikai értéket ad vissza (igaz, ha a gyűjtemény megadott elemet tartalmaz).

4.4. Sor műveletek

Deque interfész biztosítja a sorszerű viselkedést (valójában Deque kiterjed Sor felület):

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

Ezek a módszerek lekérik az első elemet és eltávolítják a listáról.

A különbség közvélemény kutatás() és pop() az, hogy a pop dobni fog NoSuchElementException () üres listán, míg közvélemény kutatás null értéket ad vissza. Az API-k pollFirst () és pollLast () is rendelkezésre állnak.

Itt van például a nyom Az API működik:

linkedList.push (o objektum);

Ami beszúrja az elemet a gyűjtemény élére.

LinkedList sok más módszerrel rendelkezik, amelyek többségének ismernie kell a már használt felhasználó számára Listák. Mások, amelyeket a Deque kényelmes alternatíva lehet a „szokásos” módszerekkel szemben.

A teljes dokumentáció itt található.

5. Következtetés

Tömb lista általában az alapértelmezett Lista végrehajtás.

Vannak azonban bizonyos használati esetek, amikor a LinkedList jobban illeszkedik, például az állandó beillesztési / törlési idő preferenciái (például gyakori beillesztések / törlések / frissítések), az állandó hozzáférési idő és a hatékony memóriahasználat mellett.

A kódminták megtalálhatók a GitHubon.