Java ArrayList vs LinkedList
1. Áttekintés
Gyűjtemények esetében a Java szabványos könyvtár rengeteg lehetőséget kínál, amelyek közül választhat. E lehetőségek között van két híres Lista megvalósításként ismert Tömb lista és LinkedList, mindegyik saját tulajdonságokkal és felhasználási esetekkel rendelkezik.
Ebben az oktatóanyagban megnézzük, hogyan valósítják meg ezt a kettőt. Ezután mindegyikhez különféle alkalmazásokat fogunk értékelni.
2. Tömb lista
Belsőleg, Tömb lista tömböt használ a Lista felület. Mivel a tömbök fix méretűek Java-ban, Tömb lista tömböt hoz létre bizonyos kezdeti kapacitással. Útközben, ha az alapértelmezett kapacitásnál több elemet kell tárolnunk, akkor ezt a tömböt egy új és tágasabbra cseréli.
Tulajdonságainak jobb megértése érdekében értékeljük ezt az adatszerkezetet három fő művelete szempontjából: elemek hozzáadása, indexenként történő megszerzés és index szerinti eltávolítás.
2.1. Hozzáadás
Amikor létrehozunk egy üreset Tömb lista, alapértelmezett kapacitással (jelenleg 10) inicializálja a háttértömböt:
Új elem hozzáadása, amíg az a tömb még nincs tele, olyan egyszerű, mint hozzárendelni az elemet egy meghatározott tömbindexhez. Ezt a tömbindexet az aktuális tömbméret határozza meg, mivel gyakorlatilag csatlakozunk a listához:
backingArray [méret] = newItem; méret ++;Így, legjobb és átlagos esetekben az összeadási művelet időbeli összetettsége O (1), ami elég gyors. Amint a háttértömb megtelik, az add implementáció kevésbé hatékony:
Új elem hozzáadásához először inicializálnunk kell egy teljesen új tömböt nagyobb kapacitással, és az összes meglévő elemet át kell másolnunk az új tömbbe. Csak az aktuális elemek másolása után adhatjuk hozzá az új elemet. Ezért az idő bonyolultsága Tovább) a legrosszabb esetben, mivel másolnunk kell n elemek először.
Elméletileg egy új elem hozzáadása amortizált állandó időben fut. Vagyis hozzátéve n elemek megkövetelik Tovább) idő. Egyes egyedi kiegészítések azonban gyengén teljesítenek a másolás költségei miatt.
2.2. Hozzáférés az Index segítségével
A tételek indexek alapján történő elérése az Tömb lista igazán ragyog. Elem lekérése az indexben én, csak vissza kell adnunk a ith index a háttér tömbből. Következésképpen, az index művelettel való hozzáférés időbeli összetettsége mindig O (1).
2.3. Eltávolítás index segítségével
Tegyük fel, hogy eltávolítjuk a 6 indexet a mi indexünkből Tömb lista, amely megfelel a háttértömbünk 15. elemének:
Miután a kívánt elemet töröltként jelölte meg, minden indexet vissza kell mozgatnunk egy index után. Nyilvánvaló, hogy minél közelebb van az elem a tömb kezdetéhez, annál több elemet kell mozgatnunk. Tehát az idő összetettsége O (1) a legjobb esetben és Tovább) átlagosan és a legrosszabb esetekben.
2.4. Alkalmazások és korlátozások
Általában, Tömb lista az alapértelmezett választás sok fejlesztő számára, amikor a Lista végrehajtás. Ami azt illeti, valójában ésszerű választás, amikor az olvasások száma jóval meghaladja az írások számát.
Néha ugyanolyan gyakran kell olvasni és írni. Ha van becslésünk a lehetséges tételek maximális számáról, akkor is van értelme használni Tömb lista. Ebben az esetben inicializálhatjuk a Tömb lista kezdeti kapacitással:
int lehetségesUpperBound = 10_000; Lista elemek = new ArrayList (lehetségesUpperBound);Ez a becslés megakadályozhatja a sok felesleges másolást és tömb allokációt.
Ráadásul, tömböket indexeli int értékek Java-ban. Tehát nem lehet többet tárolni, mint 232 elemek egy Java tömbben és következésképpen az Tömb lista.
3. LinkedList
LinkedList, amint a neve is mutatja összekapcsolt csomópontok gyűjteményét használja az elemek tárolásához és letöltéséhez. Például a következőképpen néz ki a Java implementáció négy elem hozzáadása után:
Minden csomópont két mutatót tart fenn: az egyik a következő elemre mutat, a másik pedig az előzőre. Ezt kibővítve a kétszeresen összekapcsolt listán két mutató mutat az első és az utolsó elemre.
Ismét értékeljük ezt a megvalósítást ugyanazon alapvető műveletek vonatkozásában.
3.1. Hozzáadás
Új csomópont hozzáadásához először össze kell kapcsolnunk az aktuális utolsó csomópontot az új csomóponttal:
Ezután frissítse az utolsó mutatót:
Mivel mindkét művelet triviális, az add művelet időbeli összetettsége mindig O (1).
3.2. Hozzáférés az Index segítségével
LinkedList, szemben a Tömb lista, nem támogatja a gyors véletlenszerű hozzáférést. Tehát ahhoz, hogy elemet találjunk indexenként, meg kell haladnunk a lista bizonyos részétmanuálisan.
A legjobb esetben, ha a kért tétel a lista elejének vagy végének közelében van, az idő bonyolultsága olyan gyors lenne, mint O (1). Az átlagos és a legrosszabb esetekben azonban egy Tovább) hozzáférési idő, mivel sok csomópontot kell egymás után megvizsgálnunk.
3.3. Eltávolítás index segítségével
Egy elem eltávolításához először meg kell találnunk a kért elemet, majd le kell kapcsolnunk a listáról. Következésképpen a hozzáférési idő meghatározza az idő összetettségét - vagyis O (1) legjobb esetben is Tovább) átlagosan és a legrosszabb esetekben is.
3.4. Alkalmazások
LinkedLists alkalmasabbak, ha az összeadási arány sokkal nagyobb, mint az olvasási sebesség.
Használható nehéz olvasási esetekben is, amikor legtöbbször az első vagy utolsó elemre vágyunk. Érdemes ezt megemlíteni LinkedList megvalósítja a Deque interfész - a gyűjtemény mindkét végéhez való hatékony hozzáférés támogatása.
Általában, ha ismerjük megvalósítási különbségeiket, akkor könnyen választhatunk egyet egy adott felhasználási esetre.
Tegyük fel például, hogy sok idősoros eseményt tárolunk egy listaszerű adatszerkezetben. Tudjuk, hogy másodpercenként rengeteg eseményt fogunk kapni.
Emellett periodikusan meg kell vizsgálnunk az összes eseményt, és meg kell adnunk néhány statisztikát. Ehhez a használati esethez LinkedList jobb választás, mert az összeadási arány sokkal magasabb, mint az olvasási sebesség.
Ezenkívül elolvasnánk az összes elemet, így nem tudjuk legyőzni a Tovább) felső korlát.
4. Következtetés
Ebben az oktatóanyagban először elmélyültünk a hogyanban Tömb lista és LinkLists Java-ban vannak megvalósítva.
Mindegyikhez különféle felhasználási eseteket is megvizsgáltunk.
