Java LinkedList

Szia! Az összes legújabb leckét az ArrayListnek szentelték . Ez az adatstruktúra nagyon kényelmes és hasznos. Rengeteg feladatot elbír. De a Java sok más adatstruktúrával rendelkezik. Miért? Mindenekelőtt azért, mert a feladatok köre óriási, és a leghatékonyabb adatstruktúrák is eltérőek a különböző feladatokhoz. Ma egy új szerkezettel találkozunk: Java LinkedList , egy duplán linkelt lista.

Nézzük meg, hogyan szerveződik, miért hívják duplán linkeltnek, miben különbözik az ArrayListtől . A Java LinkedList elemei valójában egyetlen lánc linkjei. Az adatokon kívül minden elem hivatkozásokat tárol az előző és a következő elemekre. Ezek a hivatkozások lehetővé teszik, hogy egyik elemről a másikra léphessen. Így hozhat létre egyet:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

Kimenet: [Hello World! A nevem Earl, szeretem a Java-t, Kanadában élek] Így néz ki a listánk: LinkedList – 2

Nézzük meg, hogyan adjunk hozzá új elemet. Ez az add() metódussal történik .

earlBio.add(str2);

A kód pontján a listánk egy elemből áll: a String str1 . Lássuk, mi történik ezután a képen: LinkedList – 3

Ennek eredményeként az str2 és str1 összekapcsolódik a lista ezen csomópontjaiban tárolt következő és előző LinkedList – 4

hivatkozásokon keresztül: Most meg kell értenie a duplán linkelt lista fő gondolatát. Pontosan ez a linklánc teszi a LinkedList elemeket egyetlen listává. Az ArrayListtel ellentétben a LinkedList nem tartalmaz tömböt vagy bármi tömbszerűt. Bármilyen (jó, a legtöbb) az ArrayListtel végzett munka a belső tömbbel való munkavégzésre vezethető vissza. Bármilyen munka a Java LinkedList- tela linkek megváltoztatásában merül ki. Ez nagyon jól látható, ha hozzáadunk egy elemet a lista közepéhez:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

Amint láthatja, a túlterhelt add() metódus lehetővé teszi egy adott index megadását egy új elemhez. Ebben az esetben az str2 karakterláncot szeretnénk hozzáadni az str1 és str3 közé . Belsőleg ez fog történni: LinkedList – 5

A belső hivatkozások megváltoztatása után az str2 sikeresen felkerült a listára: LinkedList – 6

Most mind a 3 elem csatlakoztatva van. A következő linken keresztül léphet a lánc első elemétől az utolsóig, majd vissza. Tehát elég kényelmesek vagyunk a beillesztéssel, de mi a helyzet az elemek eltávolításával? Az elv pontosan ugyanaz. Csak frissítjük a linkeket az eltávolítandó elemtől "balra és jobbra" lévő két elemben:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

A következőképpen történik, ha az 1-es indexű elemet töröljük (a lista közepén van): LinkedList – 7

A hivatkozások frissítése után a kívánt eredményt kapjuk: Az ArrayList LinkedList - 8

eltávolítási művelettel ellentétben itt nem kell eltolni a tömb elemeit, ill. bármi ilyesmi. Csak frissítjük az str1 és str3 hivatkozásait . Most egymásra mutatnak, és az str2 " kiesett " a linkek láncából, és már nem szerepel a listán.

A módszerek áttekintése

A LinkedListnek sok közös metódusa van az ArrayListtel . Például mindkét osztálynak vannak olyan metódusai, mint add() , remove() , indexOf() , clear() , include() (jelzi, hogy egy elem szerepel-e a listában), set() (egy meglévő elemet helyettesít), és méret () . Bár sok másképp működik belülről (ahogyan az add() és remove() esetén is tapasztaltuk ), a végeredmény ugyanaz. A LinkedListnek azonban külön módszerei vannak a lista elején és végén történő munkavégzéshez, amelyekkel az ArrayList nem rendelkezik:

addFirst() , addLast() : Ezek a módszerek egy elem hozzáadására a lista elejére/végére

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

Kimenet: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] [Car{model='Ford Mondeo'}, Car{model=' Ferrari 360 Spider'}, autó{model='Bugatti Veyron'}, autó{model='Lamborghini Diablo'}, autó{model='Fiat Ducato'}] Végül a „Ford” áll a lista élén , és a "Fiat" a végén.

peekFirst() , peekLast() : A metódusok a lista első/utolsó elemét adják vissza. Ha a lista üres, nullát adnak vissza .

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

Kimenet: Car{model='Ferrari 360 Spider'} Car{model='Lamborghini Diablo'}

pollFirst() , pollLast() : Ezek a metódusok a lista első/utolsó elemét adják vissza, és eltávolítják a listából. Ha a lista üres, nullát adnak vissza

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println ("What's on the list?");
   System.out.println(cars);
}

Kimenet: Autó{model='Ferrari 360 Spider'} Autó{model='Lamborghini Diablo'} Mi van még a listán? [Autó{model='Bugatti Veyron'}]

toArray() : Ez a metódus a listaelemeket tartalmazó tömböt adja vissza

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

Kimenet: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] Most már tudjuk, hogyan működik a LinkedList, és miben tér el a szervezete az ArrayListtől . Milyen előnyei vannak a LinkedList használatának ? Mindenekelőtt a lista közepén dolgozunk. A LinkedList közepén végzett beszúrási és eltávolítási műveletek sokkal egyszerűbbek, mint az ArrayListben . Egyszerűen frissítjük a szomszédos elemek linkjeit, és a nem kívánt elem "kiesik" a linkek láncolatából. De egy ArrayListben muszáj

ellenőrizze, hogy van-e elég hely (behelyezéskor)
ha nem, akkor létrehozunk egy új tömböt és oda másoljuk az adatokat (beszúráskor)
eltávolítjuk/beszúrjuk az elemet, az összes többi elemet pedig jobbra/balra mozgatjuk (művelet típusától függően). És ennek a folyamatnak a bonyolultsága nagymértékben függ a lista méretétől. Egy dolog 10 elemet másolni/áthelyezni, és egészen más megtenni ugyanezt millió elemmel.

Más szóval, ha a lista közepén található beillesztési/eltávolítási műveletek a leggyakoribbak a programban, akkor a LinkedListnek gyorsabbnak kell lennie, mint az ArrayList .

Elméletben

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Kimenet: A LinkedList által felhasznált idő (ezredmásodpercben) = 1873

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Kimenet: Az ArrayList által felhasznált idő (ezredmásodpercben) = 181 Ez váratlan volt! Elvégeztünk egy műveletet, ahol a LinkedList sokkal hatékonyabbnak kell lennie: 100 elemet beszúrtunk egy lista közepére. A listánk pedig óriási: 5 000 000 elem. Az ArrayListnek minden beillesztéskor el kellett tolnia pár millió elemet! Hogyan nyert? Először is, az ArrayList számára az elemek eléréséhez szükséges idő fix (állandó). Amikor írsz

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

akkor az ArrayList [2_000_000] egy adott memóriacím (elvégre a listának van belső tömbje). De a LinkedList-nek nincs tömbje. Megkeresi a 2_000_000 számú elemet a linkek láncolatában. A LinkedList esetében ez nem egy memóriacím, hanem egy hivatkozás, amelyet még el kell érni: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. Következő _ , az ArrayList már tudja az elérendő memória pontos címét, de a LinkedList-nek még "oda kell jutnia". Másodszor, ott van az ArrayList szerkezetemaga. Egy speciális belső függvény ( System.arrayCopy() ) kibővíti a belső tömböt, és másolja és eltolja az összes elemet. Nagyon gyors, mert erre a konkrét munkára van optimalizálva. De ha nem kell „eljutnia” egy adott indexhez, a LinkedList a nyerő. Tegyük fel, hogy beszúrjuk a lista legelejére. Próbáljunk meg millió elemet beszúrni oda:

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       // Write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
       System.out.println("The result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

Kimenet: Az eredmény ezredmásodpercben: 43448 Az eredmény ezredmásodpercben: 107 Most egy teljesen más eredményt kapunk! Az ArrayList több mint 43 másodpercet töltött egymillió elem beszúrásával a lista elejére, míg a LinkedList 0,1 másodperc alatt sikerült! A LinkedList hasznot húzott itt, mert nem kellett minden alkalommal végigfutnia a linkek láncán a lista közepéig. Azonnal megtalálja a kívánt indexet a lista elején, így a különböző algoritmus már előnyt jelent. :) Valójában nagyon elterjedt az " ArrayList versus LinkedList " vita, amibe a jelenlegi szinten nem is merülünk bele. A legfontosabb dolog, amit emlékezned kell, ez:

Egy adott gyűjtemény elméleti előnyei közül nem minden működik a valóságban (ezt láttuk a lista közepén lévő példánál)
Ne foglaljon el szélsőséges álláspontot a gyűjtemény kiválasztásakor (" Az ArrayList mindig gyorsabb. Használja, és nem hibázhat. A LinkedList-et már régóta nem használja").

Bár még a LinkedList szerzője, Joshua Bloch is ezt mondja. :) Ennek ellenére ez a perspektíva korántsem 100%-ig helyes, és erről mi is meggyőződtünk. Előző példánkban a LinkedList 400-szor (!) volt gyorsabb. A másik dolog az, hogy valóban kevés olyan helyzet van, amikor a LinkedList a legjobb választás. De léteznek, és a megfelelő pillanatban a LinkedListbőségesen megjutalmazhat. Ne felejtsük el, amit a lecke elején mondtunk: a leghatékonyabb adatstruktúrák különböző feladatokhoz eltérőek. Nem lehet 100%-ban biztos abban, hogy melyik adatstruktúra lesz a legjobb, amíg nem ismeri a feladat összes feltételét. Ezekről a kollekciókról később többet megtudhat, ami megkönnyíti a választást. De a legegyszerűbb és leghatékonyabb lehetőség mindig ugyanaz: próbálja mindkettőt a programjában használt tényleges adatokon. Ezután saját szemével láthatja, hogyan teljesít mindkét listatípus, és biztosan nem fog tévedni. :) A tanultak megerősítése érdekében javasoljuk, hogy nézzen meg egy videóleckét a Java-tanfolyamról

További olvasnivalók:
LinkedList Java adatstruktúra