Java LinkedList

Bună! Toate cele mai recente lecții au fost dedicate ArrayList . Această structură de date este foarte convenabilă și utilă. Se poate ocupa de o mulțime de sarcini. Dar Java are o mulțime de alte structuri de date. De ce? Mai presus de toate, pentru că gama de sarcini este enormă, iar cele mai eficiente structuri de date sunt diferite pentru diferite sarcini. Astăzi vom întâlni o nouă structură: Java LinkedList , o listă dublu legată.

Să vedem cum este organizat, de ce se numește dublu legat, cum diferă de ArrayList . Elementele dintr-un Java LinkedList sunt de fapt legături dintr-un singur lanț. Pe lângă date, fiecare element stochează referințe la elementele anterioare și următoare. Aceste referințe vă permit să treceți de la un element la altul. Iată cum creezi unul:

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);

   }
}

Ieșire: [Bună lume! Numele meu este Earl, iubesc Java, locuiesc în Canada] Iată cum arată lista noastră: LinkedList - 2

Să vedem cum să adăugăm un element nou. Acest lucru se face folosind metoda add() .

earlBio.add(str2);

La punctul din cod, lista noastră constă dintr-un element: String str1 . Să vedem ce se întâmplă mai departe în imagine: LinkedList - 3

Ca rezultat, str2 și str1 devin legate prin linkurile următoare și anterioare stocate în aceste noduri ale listei: LinkedList - 4

Acum ar trebui să înțelegeți ideea principală a unei liste dublu legate. Acest lanț de legături este tocmai ceea ce face elementele LinkedList o singură listă. Spre deosebire de ArrayList , LinkedList nu are o matrice sau ceva asemănător matricei în interior. Orice lucru (bine, majoritatea) cu ArrayList se reduce la lucrul cu matricea internă. Orice lucru cu Java LinkedListse rezumă la schimbarea legăturilor. Acest lucru poate fi văzut foarte clar prin adăugarea unui element la mijlocul listei:

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);

   }
}

După cum puteți vedea, metoda supraîncărcată add() vă permite să specificați un index specific pentru un articol nou. În acest caz, dorim să adăugăm String str2 între str1 și str3 . Iată ce se va întâmpla pe plan intern: LinkedList - 5

După modificarea legăturilor interne, str2 a fost adăugat cu succes la listă: LinkedList - 6

Acum toate cele 3 elemente sunt conectate. Puteți trece prin următorul link de la primul element al lanțului la ultimul și înapoi. Deci, ne simțim destul de confortabil cu inserarea, dar cum rămâne cu eliminarea elementelor? Principiul este exact același. Actualizăm doar linkurile din cele două elemente „la stânga și la dreapta” ale elementului care este eliminat:

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);
   }
}

Iată ce se întâmplă dacă ștergem elementul cu indexul 1 (este în mijlocul listei): LinkedList - 7

După actualizarea legăturilor, obținem rezultatul dorit: LinkedList - 8

Spre deosebire de operația de ștergere din ArrayList , aici nu este nevoie să mutați elementele matricei sau să faceți orice de acest fel. Tocmai actualizăm linkurile pentru str1 și str3 . Acum indică unul către celălalt, iar str2 a „ a ieșit ” din lanțul de legături și nu mai face parte din listă.

Prezentare generală a metodelor

LinkedList are o mulțime de metode în comun cu ArrayList . De exemplu, ambele clase au metode precum add() , remove() , indexOf() , clear() , contains() (indică dacă un element este în listă), set() (înlocuiește un element existent) și dimensiune () . Deși multe dintre ele funcționează diferit intern (cum am găsit cu add() și remove() ), rezultatul final este același. Cu toate acestea, LinkedList are metode separate pentru a lucra cu începutul și sfârșitul listei, pe care ArrayList nu le are:

addFirst() , addLast() : Aceste metode pentru adăugarea unui element la începutul/sfârșitul listei

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 + '\'' +
               '}';
   }
}

Ieșire: [Mașină{model='Ferrari 360 Spider'}, Mașină{model='Bugatti Veyron'}, Mașină{model='Lamborghini Diablo'}] [Mașină{model='Ford Mondeo'}, Mașină{model=' Ferrari 360 Spider'}, mașină{model='Bugatti Veyron'}, mașină{model='Lamborghini Diablo'}, mașină{model='Fiat Ducato'}] Ajungem cu „Ford” în fruntea listei , și „Fiat” la final.

peekFirst() , peekLast() : Metodele returnează primul/ultimul element din listă. Ei returnează null dacă lista este goală.

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());
}

Ieșire: Mașină{model='Ferrari 360 Spider'} Mașină{model='Lamborghini Diablo'}

pollFirst() , pollLast() : Aceste metode returnează primul/ultimul element din listă și îl elimină din listă. Ei returnează null dacă lista este goală

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);
}

Ieșire: Mașină{model='Ferrari 360 Spider'} Mașină{model='Lamborghini Diablo'} Ce a mai rămas pe listă? [Mașină{model='Bugatti Veyron'}]

toArray() : Această metodă returnează o matrice care conține elementele din listă

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));
}

Ieșire: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] Acum știm cum funcționează LinkedList și cum diferă organizarea sa de ArrayList . Care sunt beneficiile utilizării LinkedList ? Mai presus de toate, beneficiem atunci când lucrăm la mijlocul listei. Operațiile de inserare și eliminare în mijlocul unei Liste LinkedList sunt mult mai simple decât într-un ArrayList . Pur și simplu actualizăm legăturile elementelor învecinate, iar elementul nedorit „imite” din lanțul de legături. Dar într-o ArrayList , trebuie

verificați dacă este suficient spațiu (la introducere)
dacă nu, atunci creăm o nouă matrice și copiem datele acolo (când inserăm)
scoatem/introducem elementul, si mutam toate celelalte elemente la dreapta/stânga (in functie de tipul operatiei). Iar complexitatea acestui proces depinde în mare măsură de dimensiunea listei. Una este să copiezi/muți 10 elemente și cu totul altceva să faci același lucru cu un milion de elemente.

Cu alte cuvinte, dacă operațiunile de inserare/eliminare din mijlocul listei sunt cele mai frecvente în programul dvs., LinkedList ar trebui să fie mai rapid decât ArrayList .

Teoretic

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));
   }
}

Ieșire: Timpul luat de LinkedList (în milisecunde) = 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));
   }
}

Ieșire: Timpul luat de ArrayList (în milisecunde) = 181 A fost neașteptat! Am efectuat o operație în care LinkedList ar trebui să fie mult mai eficient: inserarea a 100 de articole în mijlocul unei liste. Și lista noastră este uriașă: 5.000.000 de elemente. ArrayList a trebuit să schimbe câteva milioane de elemente la fiecare inserare! Cum a câștigat? În primul rând, timpul necesar pentru ca ArrayList să acceseze elementele este fix (constant). Când scrii

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

atunci ArrayList [2_000_000] este o adresă de memorie specifică (la urma urmei, lista are o matrice internă). Dar, o listă LinkedList nu are o matrice. Acesta va căuta elementul numărul 2_000_000 de-a lungul lanțului de legături. Pentru LinkedList, aceasta nu este o adresă de memorie, ci o legătură la care încă trebuie accesată: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next……… Ca urmare, în timpul fiecărei inserări (eliminare) în mijlocul listei , ArrayList știe deja adresa exactă de memorie de accesat, dar LinkedList încă trebuie să „ajungă acolo”. În al doilea rând, există structura ArrayListîn sine. O funcție internă specială ( System.arrayCopy() ) extinde matricea internă și copiază și mută toate elementele. Este foarte rapid, deoarece este optimizat pentru această lucrare specifică. Dar când nu trebuie să „ajungi” la un anumit index, LinkedList este câștigătorul. Să presupunem că inserăm chiar la începutul listei. Să încercăm să inserăm un milion de elemente acolo:

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());
       }
   }

}

Rezultat: Rezultatul în milisecunde: 43448 Rezultatul în milisecunde: 107 Acum obținem un rezultat complet diferit! ArrayList a petrecut mai mult de 43 de secunde inserând un milion de articole în fruntea listei, în timp ce LinkedList a reușit să o facă în 0,1 secunde! LinkedList a beneficiat aici, deoarece nu a trebuit să treacă prin lanțul de legături până la mijlocul listei de fiecare dată. Găsește imediat indexul necesar la începutul listei, astfel încât algoritmul diferit este deja un avantaj. :) De fapt, discuția „ ArrayList versus LinkedList ” este foarte răspândită și nu ne vom arunca adânc în ea la nivelul actual. Principalul lucru pe care trebuie să-l rețineți este următorul:

Nu toate avantajele teoretice ale unei anumite colecții funcționează întotdeauna în realitate (am văzut asta cu exemplul care implică mijlocul listei)
Nu adoptați o poziție extremă când vine vorba de alegerea unei colecții (" ArrayList este întotdeauna mai rapid. Folosiți-l și nu puteți greși. Nimeni nu folosește LinkedList de mult timp").

Deși chiar și autorul lui LinkedList , Joshua Bloch, spune că acesta este cazul. :) Totuși, această perspectivă este departe de a fi 100% corectă și ne-am convins de asta. În exemplul nostru anterior, LinkedList a fost de 400 (!) de ori mai rapid. Un alt lucru este că există într-adevăr puține situații în care LinkedList este cea mai bună alegere. Dar ele există și la momentul potrivit LinkedListte poate recompensa frumos. Nu uitați ce am spus la începutul lecției: cele mai eficiente structuri de date sunt diferite pentru diferite sarcini. Este imposibil să fii 100% sigur care structură de date va fi cea mai bună până când nu cunoști toate condițiile sarcinii tale. Veți afla mai multe despre aceste colecții mai târziu, ceea ce va face alegerea mai ușoară. Dar cea mai simplă și mai eficientă opțiune este întotdeauna aceeași: încercați ambele pe datele reale utilizate în programul dvs. Atunci vei putea vedea singur cum se comporta ambele tipuri de liste și cu siguranță nu vei greși. :) Pentru a consolida ceea ce ați învățat, vă sugerăm să urmăriți o lecție video de la Cursul nostru Java

Mai multe lecturi:
LinkedList Java Data Structure