Structura de date cu listă legată în Java

Sunt create diferite structuri de date pentru scopuri diferite. Poate știți despre ArrayList (dacă încă nu, vă recomandăm să citiți mai întâi despre el). În acest articol, vom afla despre LinkedList și vom realiza la ce este bună această colecție. Dacă vă uitați la sursa codului clasei LinkedList Java 8 (sau versiunea ulterioară a limbii) (pe site-ul Oracle sau în IDE-ul dvs., în cazul IDEA: crtl+B pe numele clasei), veți vedea următoarea declarație:

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

Momentan, cea mai importantă informație din cod este faptul că LinkedList implementează interfețele List și Deque . Interfața Listă păstrează secvența de adăugare a articolelor și permite accesul la articol după index. Coada „obișnuită” acceptă adăugarea de elemente la sfârșit și extragerea lor de la început. Deque este o coadă bidirecțională și acceptă adăugarea și eliminarea elementelor din ambele părți. S-ar putea să vă gândiți la asta ca la o combinație de stivă și coadă. Deci, LinkedList este o implementare a acestor două și ne permite să creăm o coadă bidirecțională formată din orice obiecte, inclusiv null. LinkedListeste o colecție de elemente. O putem vedea în sursa de cod a clasei, de data aceasta acordați atenție câmpurilor:

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

Fiecare element, de obicei l-am numit Node , conține un obiect și trimiteri la două obiecte învecinate - anterior și următorul. Prin urmare, nu este foarte eficient în ceea ce privește utilizarea memoriei. Deoarece LinkedList este de fapt o structură bidirecțională, putem adăuga sau elimina cu ușurință elemente din ambele părți.

Constructori LinkedList

Revenind la sursa codului, putem afla că LinkedList are doi constructori

• LinkedList() fără parametri este folosit pentru a construi o listă goală.
• >LinkedList(Collection<? extends E> c) este pentru crearea unei liste care să conțină elementele colecției specificate, în ordine, acestea sunt returnate de iteratorul colecției.

Declarație LinkedList

De fapt, o listă legată (Java sau în orice altă limbă) constă dintr-o secvență de noduri. Fiecare nod este conceput pentru a stoca un obiect de un tip definit la creare. Deci, pentru a crea LinkedList , codul Java este următorul:

LinkedList<Integer> myList = new LinkedList<>();

Avem un obiect pentru a păstra o secvență de numere întregi și legături către vecini. Cu toate acestea, este gol în acest moment.

Operațiuni principale LinkedList

Ca de obicei, în cazul Colecțiilor puteți pune elemente în LinkedList (până la sfârșitul acesteia sau în mijloc), puteți elimina de acolo și puteți obține un element cu index. Deci iată-le:

• add(E element) Adaugă elementul specificat la sfârșitul acestei liste;
• add(int index, E element) Inserează elementul la indexul de poziție specificat ;
• get(int index) Returnează elementul la poziția specificată în această listă;
• remove(int index) Îndepărtează elementul care se află la indexul de poziție;
• remove(Obiect o) Elimină prima apariție a lui ? o element din această listă dacă există.
• remove() Preia și elimină primul element al listei.

Implementarea listelor legate în Java, adăugarea și eliminarea elementelor. Exemplu

Să încercăm aceste operații în practică. În primul rând, implementarea Java LinkedList: crearea unei LinkedList de șiruri, adăugând acolo 3 elemente. Apoi scoateți unul, apoi adăugați unul în mijloc.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

Rezultatul rulării acestui program:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

Un LinkedList este o parte a cadrului Collection , puteți folosi Iterator pentru a elimina elemente, precum și un iterator special pentru liste - ListIterator . Mai mult, operațiunile cu iterator oferă principalele beneficii ale clasei LinkedList : performanță bună a operațiunilor de inserare/ștergere. Folosind Iterator, puteți obține un timp constant pentru ei. Mai târziu în acest articol, vom scrie un exemplu de cod pentru a compara ArrayList și LinkedList+Iterator

• Iterator.remove() elimină ultimul element returnat de acest iterator.
• ListIterator.add(E element) inserează un element în listă

Exemplu Java LinkedList: cum funcționează Iteratorul

Aici avem un mic cod Java LinkedList Example, unde încercăm să adăugăm și să ștergem prin Iterator.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
 
       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);
 
   }
}

Rezultatul rulării acestui program:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

Mai multe operații Java LinkedList :

• addFirst() , addLast() adaugă un element la începutul/sfârșitul unei liste
• clear() elimină toate elementele din listă
• contains(Object o) returnează adevărat dacă lista conține elementul o.
• indexOf(Object o) returnează indexul primei apariții a elementului o sau -1 dacă nu este în listă.
• set(index int, element E) înlocuiește elementul din poziția indexului cu elementul
• size() Returnează cantitatea de elemente din listă.
• toArray() returnează un tablou care conține toate elementele listei de la primul până la ultimul element.

BTW fiind o coadă de două dimensiuni, LinkedList în Java are operațiuni specifice stivei:

• pop() care scoate un element din stivă (reprezentat de listă)
• push(E e) care împinge un element pe stivă (reprezentat de această listă)

Cum să inversați LinkedList: exemplu

Iată un mic exemplu, o sarcină populară, dar ușoară pentru începători. Avem o listă LinkedList și ar trebui să o inversăm. Cel mai simplu algoritm este să parcurgeți LinkedList în ordine inversă și să puneți fiecare element în cel nou. Cu toate acestea, poate veți găsi o cale mai bună? Iată codul programului java listă inversată:

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

Rezultatul:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList vs ArrayList: când să utilizați primul

Atât LinkedList, cât și ArrayList sunt implementări ale interfeței List . LinkedList îl implementează cu o listă dublu legată. ArrayList îl implementează folosind o matrice de redimensionare dinamică. După cum știți deja, fiecare nod al LinkedList conține obiecte și două referințe la vecini. Aceasta înseamnă costuri suplimentare de memorie pentru stocarea referințelor între elemente în cazul Java LinkedList . ArrayList îl implementează cu o matrice de redimensionare dinamică. Unele dintre operațiunile LinkedList și ArrayList arată la fel, dar funcționează într-un mod diferit. În ArrayListcaz, manipulezi cu matrice interne, în LinkedList — cu referințe. ArrayList este cea mai populară implementare Listă . Cu siguranță ar trebui să utilizați ArrayList atunci când accesul la index este o prioritate, deoarece aceste operațiuni sunt efectuate în timp constant. Adăugarea la sfârșitul listei în medie se face și în timp constant. Mai mult decât atât, ArrayList nu are costuri suplimentare pentru stocarea unei grămadă de elemente. Puteți conta drept Contra viteza operațiunilor de inserare și eliminare atunci când nu se face la sfârșitul listei. LinkedListeste mai util în cazul performanței operațiunilor de inserare și ștergere în anumite moduri: dacă utilizați iteratoare, aceasta are loc în timp constant. Operațiile de acces prin index se efectuează prin căutarea de la începutul sfârșitului (oricare este mai aproape) până la elementul dorit. Cu toate acestea, nu uitați de costurile suplimentare pentru stocarea referințelor între elemente. Deci, aici operațiuni standard LinkedList și ArrayList cu timpi de execuție algoritmici. N se referă la numărul de articole care sunt deja pe listă. O(N) înseamnă că în cel mai rău caz ar trebui să „plimbăm” întreaga listă până când este găsită poziția necesară, de exemplu, pentru inserarea noului element în listă. O(1)înseamnă că operațiunea are loc în timp constant, independent de numărul de articole.

Complexitatea timpului LinkedList

Complexitatea timpului ArrayList

Când să utilizați LinkedList: Exemplu

Cu siguranță, ArrayList este cea mai populară implementare Listă . Cu toate acestea, este posibil să întâlniți situațiile în care operațiunile de adăugare/eliminare sunt necesare prea des. În acest caz, LinkedList împreună cu Iterator ar putea fi benefice. Iată un exemplu. Avem o listă lungă și ar trebui să ștergem fiecare element din această listă. Să facem această sarcină cu ArrayList și LinkedList + Iterator . Comparăm timpul fiecărei operațiuni și îl imprimăm în consolă. Iata codul:

import java.util.*;
import java.util.function.BiPredicate;
 
public class ListTest2 {
 
   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());
 
       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }
 
   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);
 
           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }
 
   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
 
   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

Rezultat pentru ArrayList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

Rezultat pentru LinkedList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

După cum puteți vedea în acest caz, LinkedList este mult mai eficient. Sa fim cinstiti. În dezvoltarea software-ului real, utilizarea LinkedList este un fel de eveniment rar. Cu toate acestea, un profesionist ar trebui să cunoască existența acestei structuri de date și avantajele acesteia. Dacă în codul real LinkedList este un invitat rar, pe interviurile Java Junior este foarte popular. Și totuși, iată ce a scris Joshua Bloch despre LinkedList :

AddOn: Listă Java conectată individual

Nu există nicio listă cu legături unice printre colecțiile clasice din Java, Lista legată individual este o structură în care fiecare nod conține un obiect și o referință la următorul nod, dar nu pentru cel anterior. Java LinkedList are două legături, dar nimeni nu interferează cu dvs. pentru a vă crea propria structură de date, cum ar fi un singur ,code>Linked List. Iată câțiva pași pentru a rezolva aceste sarcini:

1. Creați o clasă Node cu două atribute, date și următorul. Următorul este o referință la următorul nod.
2. Creați clasa FirstLast cu două atribute, cap și coadă.
3. Creați o metodă add() pentru a adăuga un nou nod la listă. Verificați dacă lista este goală mai întâi ( head == null ). Dacă da, capul și coada se referă la noul nod. Dacă lista nu este goală, noul nod va fi adăugat la sfârșit, astfel încât următorul atribut al cozii se referă la nodul adăugat și noul nod devine coada listei.

Apropo, puteți încerca să vă creați propria LinkedList și ca exercițiu. Mult succes in invatarea ta.