Linked List face parte din Cadrul de colectare prezent în pachetul java.util. Această clasă este o implementare a structurii de date a listei dublu legate.
Principala diferență dintre o listă normală legată și o listă dublu legată este că o listă dublu legată conține un pointer suplimentar, numit în mod obișnuit indicatorul anterior, împreună cu următorul pointer și datele care sunt acolo în lista legată individual.
Constructori din LinkedList:
Pentru a crea un LinkedList, trebuie să creăm un obiect din clasa LinkedList. Clasa LinkedList este formată din diverși constructori care permit crearea posibilă a listei. Următorii sunt constructorii disponibili în această clasă:
1. LinkedList(): Acest constructor este folosit pentru a crea o listă goală legată. Dacă dorim să creăm o LinkedList goală cu numele ll, atunci aceasta poate fi creată ca:
LinkedList ll = new LinkedList();
2. LinkedList(Colecția C): Acest constructor este folosit pentru a crea o listă ordonată care conține toate elementele unei colecții specificate, așa cum este returnată de iteratorul colecției. Dacă dorim să creăm o LinkedList cu numele ll, atunci aceasta poate fi creată ca:
LinkedList ll = noua Lista Linked(C);
Metode pentru Java LinkedList:
| Metodă | Descriere |
|---|---|
| adaugă (index int, element E) | Această metodă Inserează elementul specificat la poziția specificată în această listă. |
| adaugă (și și) | Această metodă Adaugă elementul specificat la sfârșitul acestei liste. |
| addAll(index int, Colecția c) | Această metodă Inserează toate elementele din colecția specificată în această listă, începând de la poziția specificată. |
| addAll(Colecția c) | Această metodă adaugă toate elementele din colecția specificată la sfârșitul acestei liste, în ordinea în care sunt returnate de iteratorul colecției specificate. |
| addFirst(E e) | Această metodă Inserează elementul specificat la începutul acestei liste. |
| addLast(E e) | Această metodă Adaugă elementul specificat la sfârșitul acestei liste. |
| clar() | Această metodă elimină toate elementele din această listă. |
| clona() | Această metodă returnează o copie superficială a acestei LinkedList. |
| conține (obiectul o) | Această metodă returnează true dacă această listă conține elementul specificat. |
| descendingIterator() | Această metodă returnează un iterator peste elementele din acest deque în ordine secvenţială inversă. |
| element() | Această metodă preia, dar nu îndepărtează, capul (primul element) al acestei liste. |
| get(index int) | Această metodă returnează elementul la poziția specificată în această listă. |
| getFirst() | Această metodă returnează primul element din această listă. |
| getLast() | Această metodă returnează ultimul element din această listă. |
| indexOf(Obiect o) | Această metodă returnează indexul primei apariții a elementului specificat în această listă sau -1 dacă această listă nu conține elementul. |
| lastIndexOf(Obiect o) | Această metodă returnează indexul ultimei apariții a elementului specificat în această listă sau -1 dacă această listă nu conține elementul. |
| listIterator(index int) | Această metodă returnează un iterator de listă al elementelor din această listă (în ordinea corespunzătoare), începând de la poziția specificată în listă. |
| oferta(E e) | Această metodă Adaugă elementul specificat ca coadă (ultimul element) al acestei liste. |
| oferFirst (E și) | Această metodă Inserează elementul specificat în fruntea acestei liste. |
| oferLast(E e) | Această metodă Inserează elementul specificat la sfârșitul acestei liste. |
| arunca o privire() | Această metodă preia, dar nu îndepărtează, capul (primul element) al acestei liste. |
| peekFirst() | Această metodă preia, dar nu elimină, primul element al acestei liste sau returnează null dacă această listă este goală. |
| peekLast() | Această metodă preia, dar nu elimină, ultimul element al acestei liste sau returnează null dacă această listă este goală. |
| sondaj() | Această metodă preia și elimină capul (primul element) din această listă. |
| pollFirst() | Această metodă preia și elimină primul element din această listă sau returnează null dacă această listă este goală. |
| sondajLast() | Această metodă preia și elimină ultimul element din această listă sau returnează null dacă această listă este goală. |
| pop() | Această metodă scoate un element din stiva reprezentată de această listă. |
| împinge (E și) | Această metodă împinge un element în stiva reprezentată de această listă. |
| elimina() | Această metodă preia și elimină capul (primul element) din această listă. |
| elimina (index int) | Această metodă elimină elementul din poziția specificată în această listă. |
| elimina (obiectul o) | Această metodă elimină prima apariție a elementului specificat din această listă dacă este prezent. |
| removeFirst() | Această metodă elimină și returnează primul element din această listă. |
| removeFirstOccurrence(Obiect o) | Această metodă elimină prima apariție a elementului specificat în această listă (când parcurgeți lista de la cap la coadă). |
| removeLast() | Această metodă elimină și returnează ultimul element din această listă. |
| removeLastOccurrence(Obiect o) | Această metodă elimină ultima apariție a elementului specificat în această listă (când parcurgeți lista de la cap la coadă). |
| set(index int, element E) | Această metodă înlocuiește elementul din poziția specificată în această listă cu elementul specificat. |
| mărimea() | Această metodă returnează numărul de elemente din această listă. |
| spliterator() | Această metodă creează un Spliterator cu legare tardivă și cu eșec rapid peste elementele din această listă. |
| toArray() | Această metodă returnează o matrice care conține toate elementele din această listă în ordinea corectă (de la primul până la ultimul element). |
| toArray(T[] a) | Această metodă returnează un tablou care conține toate elementele din această listă în ordinea corectă (de la primul până la ultimul element); tipul de rulare al matricei returnate este cel al matricei specificate. |
| toString() | Această metodă returnează un șir care conține toate elementele din această listă în ordinea corectă (de la primul până la ultimul element), fiecare element este separat prin virgule și șirul este cuprins între paranteze drepte. |
Mai jos este implementarea operațiunilor de mai sus:
Java
// Java Program to Demonstrate> // Implementation of LinkedList> // class> > // Importing required classes> import> java.util.*;> > // Main class> public> class> GFG {> > >// Driver code> >public> static> void> main(String args[])> >{> >// Creating object of the> >// class linked list> >LinkedList ll =>new> LinkedList();> > >// Adding elements to the linked list> >ll.add(>'A'>);> >ll.add(>'B'>);> >ll.addLast(>'C'>);> >ll.addFirst(>'D'>);> >ll.add(>2>,>'E'>);> > >System.out.println(ll);> > >ll.remove(>'B'>);> >ll.remove(>3>);> >ll.removeFirst();> >ll.removeLast();> > >System.out.println(ll);> >}> }> |
>
>Ieșire
[D, A, E, B, C] [A]>
În ilustrația de mai sus, AbstractList , CopyOnWriteArrayList și AbstractSequentialList sunt clasele care implementează interfața listă. O funcționalitate separată este implementată în fiecare dintre clasele menționate. Sunt:
- AbstractList: Această clasă este folosită pentru a implementa o listă nemodificabilă, pentru care trebuie doar să extindeți această clasă AbstractList și să implementați doar metodele get() și size(). CopyOnWriteArrayList: Această clasă implementează interfața listă. Este o versiune îmbunătățită a ArrayList în care toate modificările (adăugați, setați, eliminați etc.) sunt implementate prin realizarea unei noi copii a listei.
Efectuarea diferitelor operații pe LinkedList:
- Adăugarea de elemente
- Elemente de actualizare
- Îndepărtarea elementelor
- Iterarea peste elemente
- To Array();
- Mărimea();
- elimina primul();
- elimina ultimul();
Operațiunea 1: Adăugarea de elemente
Pentru a adăuga un element la o ArrayList, putem folosi metoda add() . Această metodă este supraîncărcată pentru a efectua mai multe operații bazate pe diferiți parametri. Sunt:
- add(Object): Această metodă este folosită pentru a adăuga un element la sfârșitul LinkedList. add(int index, Object): Această metodă este folosită pentru a adăuga un element la un index specific din LinkedList.
Mai jos este implementarea operațiunii de mai sus:
Java
// Java program to add elements> // to a LinkedList> > import> java.util.*;> > public> class> GFG {> > >public> static> void> main(String args[])> >{> >LinkedList ll =>new> LinkedList();> > >ll.add(>'Geeks'>);> >ll.add(>'Geeks'>);> >ll.add(>1>,>'For'>);> > >System.out.println(ll);> >}> }> |
>
>Ieșire
[Geeks, For, Geeks]>
Operațiunea 2: Schimbarea elementelor
După adăugarea elementelor, dacă dorim să schimbăm elementul, se poate face folosind metoda set() . Deoarece o listă LinkedList este indexată, elementul pe care dorim să-l schimbăm este referit de indexul elementului. Prin urmare, această metodă ia un index și elementul actualizat care trebuie inserat la acel index.
Mai jos este implementarea operațiunii de mai sus:
Java
// Java program to change elements> // in a LinkedList> > import> java.util.*;> > public> class> GFG {> > >public> static> void> main(String args[])> >{> >LinkedList ll =>new> LinkedList();> > >ll.add(>'Geeks'>);> >ll.add(>'Geeks'>);> >ll.add(>1>,>'Geeks'>);> > >System.out.println(>'Initial LinkedList '> + ll);> > >ll.set(>1>,>'For'>);> > >System.out.println(>'Updated LinkedList '> + ll);> >}> }> |
cum să obțineți data curentă în java
>
>Ieșire
Initial LinkedList [Geeks, Geeks, Geeks] Updated LinkedList [Geeks, For, Geeks]>
Operațiunea 3: Îndepărtarea elementelor
Pentru a elimina un element dintr-un LinkedList, putem folosi metoda remove() . Această metodă este supraîncărcată pentru a efectua mai multe operații bazate pe diferiți parametri. Sunt:
- remove(Object): Această metodă este folosită pentru a elimina pur și simplu un obiect din LinkedList. Dacă există mai multe astfel de obiecte, atunci prima apariție a obiectului este eliminată. remove(int index): Deoarece o listă LinkedList este indexată, această metodă ia o valoare întreagă care pur și simplu elimină elementul prezent la acel index specific din LinkedList. După eliminarea elementului și indicii elementelor sunt actualizați, la fel și obiectul LinkedList este actualizat, oferind o nouă Listă după ștergerea elementului/elelor.
Mai jos este implementarea operațiunii de mai sus:
Java
// Java program to remove elements> // in a LinkedList> > import> java.util.*;> > public> class> GFG {> > >public> static> void> main(String args[])> >{> >LinkedList ll =>new> LinkedList();> > >ll.add(>'Geeks'>);> >ll.add(>'Geeks'>);> >ll.add(>1>,>'For'>);> > >System.out.println(>'Initial LinkedList '> + ll);> > >// Function call> >ll.remove(>1>);> > >System.out.println(>'After the Index Removal '> + ll);> > >ll.remove(>'Geeks'>);> > >System.out.println(>'After the Object Removal '> >+ ll);> >}> }> |
>
>
program c pentru matrice bidimensionalăIeșire
Initial LinkedList [Geeks, For, Geeks] After the Index Removal [Geeks, Geeks] After the Object Removal [Geeks]>
Operațiunea 4: Repetarea LinkedList
Există mai multe moduri de a repeta prin LinkedList. Cele mai cunoscute moduri sunt folosirea buclei for de bază în combinație cu metoda get() pentru a obține elementul la un index specific și bucla for avansată.
Mai jos este implementarea operațiunii de mai sus:
Java
// Java program to iterate the elements> // in an LinkedList> > import> java.util.*;> > public> class> GFG {> > >public> static> void> main(String args[])> >{> >LinkedList ll> >=>new> LinkedList();> > >ll.add(>'Geeks'>);> >ll.add(>'Geeks'>);> >ll.add(>1>,>'For'>);> > >// Using the Get method and the> >// for loop> >for> (>int> i =>0>; i System.out.print(ll.get(i) + ' '); } System.out.println(); // Using the for each loop for (String str : ll) System.out.print(str + ' '); } }> |
>
>Ieșire
Geeks For Geeks Geeks For Geeks>
Operația 4: Lista legată la To Array utilizând toArray();
Java
import> java.util.*;> public> class> GFG2 {> >public> static> void> main(String[] args)> >{> >LinkedList list=>new> LinkedList();> >list.add(>123>);> >list.add(>12>);> >list.add(>11>);> >list.add(>1134>);> >System.out.println(>'LinkedList: '>+ list);> >Object[] a = list.toArray();> >System.out.print(>'After converted LinkedList to Array: '>);> >for>(Object element : a)> >System.out.print(element+>' '>);> >}> }> |
>
>Ieșire
LinkedList: [123, 12, 11, 1134] After converted LinkedList to Array: 123 12 11 1134>
Operațiune 5-size();
Java
import> java.io.*;> import> java.util.LinkedList;> public> class> GFG2 {> >public> static> void> main(String args[]) {> >LinkedList list =>new> LinkedList();> >list.add(>'Geeks for Geeks '>);> >list.add(>'is best '>);> >// Displaying the size of the list> >System.out.println(>'The size of the linked list is: '> + list.size());> >}> }> |
>
>Ieșire
The size of the linked list is: 2>
Operațiunea 7 – removeFirst();
Java
mașină virtuală java
import> java.io.*;> import> java.util.LinkedList;> public> class> GFG2 {> >public> static> void> main(String args[]) {> > >LinkedList list =>new> LinkedList();> >list.add(>10>);> >list.add(>20>);> >list.add(>30>);> >System.out.println(>'LinkedList:'> + list);> >System.out.println(>'The remove first element is: '> + list.removeFirst());> >// Displaying the final list> >System.out.println(>'Final LinkedList:'> + list);> >}> }> |
>
>Ieșire
LinkedList:[10, 20, 30] The remove first element is: 10 Final LinkedList:[20, 30]>
Operația 8- removelast();
Java
import> java.io.*;> import> java.util.LinkedList;> public> class> GFG2 {> >public> static> void> main(String args[])> >{> > >LinkedList list =>new> LinkedList();> >list.add(>10>);> >list.add(>20>);> >list.add(>30>);> >System.out.println(>'LinkedList:'> + list);> >// Remove the tail using removeLast()> >System.out.println(>'The last element is removed: '> + list.removeLast());> >// Displaying the final list> >System.out.println(>'Final LinkedList:'> + list);> >// Remove the tail using removeLast()> >System.out.println(>'The last element is removed: '> + list.removeLast());> >// Displaying the final list> >System.out.println(>'Final LinkedList:'> + list);> >}> }> |
>
>Ieșire
LinkedList:[10, 20, 30] The last element is removed: 30 Final LinkedList:[10, 20] The last element is removed: 20 Final LinkedList:[10]>
Clasa LinkedList din Java este o parte a Java Collections Framework și oferă o implementare a listei legate a interfeței List. Permite stocarea și preluarea elementelor într-o structură de date de listă dublu legată, în care fiecare element este legat de elementele sale predecesoare și succesoare.
Iată un exemplu simplu care demonstrează cum se utilizează o listă LinkedList în Java:
Java
import> java.util.LinkedList;> > public> class> LinkedListExample {> >public> static> void> main(String[] args) {> >// Create a new linked list> >LinkedList linkedList =>new> LinkedList();> > >// Add elements to the linked list> >linkedList.add(>1>);> >linkedList.add(>2>);> >linkedList.add(>3>);> > >// Add an element to the beginning of the linked list> >linkedList.addFirst(>0>);> > >// Add an element to the end of the linked list> >linkedList.addLast(>4>);> > >// Print the elements of the linked list> >for> (>int> i : linkedList) {> >System.out.println(i);> >}> >}> }> |
>
>Ieșire
0 1 2 3 4>
Avantajele utilizării LinkedList în Java:
- Dimensiune dinamică: ca și în cazul Vector, dimensiunea unei liste LinkedList poate crește sau micșora dinamic, astfel încât nu trebuie să vă faceți griji cu privire la setarea unei dimensiuni inițiale.
- Inserări și ștergeri eficiente: LinkedList este o structură de date eficientă pentru inserarea sau ștergerea elementelor în mijlocul listei, deoarece trebuie doar să modificați legăturile dintre elemente, mai degrabă decât să mutați toate elementele după punctul de inserare sau ștergere.
- Iterație flexibilă: Cu o listă legată, puteți itera eficient prin listă în oricare direcție, deoarece fiecare element are o referință atât la elementele predecesoare, cât și la cele succesoare.
Dezavantajele utilizării LinkedList în Java:
- Performanță: LinkedList are o performanță mai lentă decât ArrayList când vine vorba de accesarea elementelor individuale. Acest lucru se datorează faptului că trebuie să parcurgeți lista pentru a ajunge la elementul dorit, în timp ce cu ArrayList, puteți accesa pur și simplu elementul dorit folosind un index.
- Overhead de memorie: LinkedList necesită mai multă memorie decât ArrayList, deoarece fiecare element necesită memorie suplimentară pentru legăturile către elementele predecesoare și succesoare.
Carte de referinta:
O carte de referință bună pentru a afla despre Cadrul colecțiilor Java și Lista Linked este Colecțiile Java de Naftalin și Wadler. Această carte oferă o privire cuprinzătoare asupra cadrului colecțiilor Java, inclusiv LinkedList, și include multe exemple și exerciții pentru a vă ajuta să înțelegeți cum să utilizați eficient aceste clase.