Bemutatkozik a LinkedList gyűjtemény

1. TörténeteLinkedList

A Java-nak van egy másik gyűjteményosztálya, a Java a C++ nyelvből örökölte. Ez az az LinkedListosztály, amely egy "összekapcsolt listát" valósít meg.

Külsőleg LinkedListúgy tűnik, hogy a megegyezik egy ArrayList. Az LinkedListosztálynak ugyanazok a metódusai vannak, mint az ArrayListosztálynak. Elvileg mindig használhatsz a LinkedListhelyett ArrayListés minden működni fog.

Akkor miért van szükségünk egy másik listás osztályra?

A válasz mindennek az osztály belső felépítéséhez kapcsolódik LinkedList. Tömb helyett duplán linkelt listát használ . Kicsit később elmagyarázzuk, mi ez.

Az LinkedListosztály eltérő belső felépítése miatt a leggyorsabban beszúrhat elemeket a lista közepére.

Az interneten gyakran találhat összehasonlításokat a ArrayListés LinkedListosztályok között:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Minden elég világosnak tűnik: ha gyakran kell elemeket beszúrnia a listába, használja a LinkedList; ha ritkán, akkor használja az ArrayList-et. De a valóság egy kicsit más.

2. Senki sem használjaLinkedList

Senki sem használja LinkedList.

Még az LinkedListosztály szerzője is nemrég Twitteren üzent: "Valaki valóban használja LinkedList? Én írtam, és soha nem használom."

Szóval mi a helyzet?

Először az ArrayListosztály kezdett nagyon gyorsan beszúrni elemeket a lista közepére. Ha egy elemet a lista közepére szúr be, a beszúrási pont utáni összes elemet el kell tolnia 1-gyel a lista vége felé. Ez régen időbe telt.

De most minden megváltozott. Egy tömb minden eleme közel van egymáshoz ugyanabban a memóriablokkban, így az elemek eltolása egy nagyon gyors, alacsony szintű paranccsal történik: .System.arraycopy()

Ráadásul a mai processzorok nagy gyorsítótárral rendelkeznek, amely általában a teljes tömböt képes tárolni, ami lehetővé teszi, hogy a tömb elemei a gyorsítótáron belül helyezkedjenek el, nem pedig a memóriában. Millió elem könnyen eltolható egyetlen ezredmásodperc alatt.

Másodszor, az LinkedListosztály gyorsan beszúrhat elemeket, ha iterátorral szúrja be őket. Ha egy iterátort használunk az elemek áthaladásához LinkedListés folyamatosan új elemek beszúrásához (vagy a meglévők eltávolításához), a művelet szupergyors.

Ha egyszerűen csak elemeket ad hozzá egy objektumhoz LinkedListegy hurkon belül, akkor minden gyors beszúrási művelethez lassú "elem beszerzése" művelet társul.

A valóság sokkal közelebb áll ehhez:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Miért kap egy elemet egy LinkedListilyen lassú műveletből?

Erre a kérdésre válaszolhat, miután egy kicsit megismerkedett a LinkedListszerkezet felépítésével.

3. Hogyan LinkedListépül fel

LinkedListmás belső szerkezettel rendelkezik, mint a ArrayList. Nincs belső tömbje az elemek tárolására. Ehelyett egy duplán tintával ellátott listának nevezett adatstruktúrát használ .

A duplán linkelt lista minden eleme hivatkozást tárol az előző és a következő elemre. Ez némileg olyan, mint egy sor az üzletben, ahol mindenki emlékszik az előtte állóra és a mögötte állóra.

Így néz ki egy ilyen lista a memóriában:

A fej és a farok (szürke hátterű cellák) a firstés lastváltozók, amelyek az objektumokra való hivatkozásokat tárolják Node.

Középen van egy objektumlánc Node(objektumok, nem változók). Mindegyik három mezőből áll:

• prev— hivatkozást (hivatkozást) tárol az előző objektumra Node(sárga hátterű cellák).
• value— tárolja a lista ezen elemének értékét (zöld hátterű cellák).
• next— tárol egy hivatkozást (hivatkozást) a következő objektumra Node(kék hátterű cellák)

A második objektum (F24 cím) a következő ( next) az első objektumhoz, és az előző ( prev) a harmadik objektumhoz. A harmadik objektum sárga mezője az F24, az első objektum kék mezője pedig az F24 címet tartalmazza.

Az első és a harmadik objektum nyilai ugyanarra a második objektumra mutatnak. Helyesebb lenne tehát így rajzolni a nyilakat.

4. Szúrjon be egy elemet egy hivatkozott listába

Ahhoz, hogy valakit ilyen sorba adjon, csak két egymás mellett álló ember engedélyét kell megszereznie. Az első ember úgy emlékszik a jövevényre, mint "a mögöttem lévő személy", a második pedig úgy emlékszik rájuk, mint "az előttem lévő személy".

Csak annyit kell tennie, hogy megváltoztatja a két szomszédos objektum hivatkozását:

A második és harmadik objektum hivatkozásainak megváltoztatásával új elemet adtunk a listánkhoz. Az új objektum a következő a régi második objektumhoz, és az előző a régi harmadik objektumhoz. És természetesen magának az új objektumnak is el kell tárolnia a megfelelő hivatkozásokat: az előző objektuma a régi második, a következő objektuma pedig a régi harmadik objektum.

Egy elem eltávolítása még egyszerűbb: Ha el akarjuk távolítani mondjuk a 100. objektumot a listából, akkor csak a 99. objektum mezőjét kell módosítanunk nextúgy, hogy az a 101. objektumra mutasson, és módosítani kell preva 101. objektum mezőjét. objektumot úgy, hogy az a 99.-re mutasson. Ez az.

De a 100. tárgy megszerzése nem olyan egyszerű.

5. Távolítson el egy elemet a listából

A hivatkozott lista 100. elemének lekéréséhez a következőket kell tennie:

firstAz 1. objektum lekérése: Ezt az objektum változójával teheti meg LinkedList. Az next1. objektum mezője a 2. objektumra való hivatkozást tárolja. Így kapjuk meg a második tárgyat. A 2. objektumnak van hivatkozása a harmadikra, és így tovább.

Ha hivatkozást kell kapnunk a 100. objektumra, akkor egymás után végig kell haladnunk az összes objektumon az 1.-től a 100.-ig. És ha egy listában a milliomodik elemre van szükségünk, akkor egymás után több mint egymillió objektumot kell iterálnunk!

És ha ezek az objektumok különböző időpontokban kerültek a listára, akkor a memória különböző részein helyezkednek el, és nem valószínű, hogy egyidejűleg a processzor gyorsítótárába kerülnek. Ez azt jelenti, hogy a hivatkozott lista elemei feletti iteráció nem csak lassú, hanem nagyon lassú.

Ezzel van dolgunk.

Akkor miért tanítjuk meg, hogyan LinkedListműködik ez a lassú?

Nos, az állásinterjúk során megkérdezik, miben LinkedListtér el aArrayList . Egyértelműen.