La llista enllaçada forma part de Marc de la col·lecció present al paquet java.util. Aquesta classe és una implementació de l'estructura de dades de llista doblement enllaçada.
La principal diferència entre una llista enllaçada normal i una llista doblement enllaçada és que una llista doblement enllaçada conté un punter addicional, normalment anomenat punter anterior, juntament amb el punter següent i les dades que hi ha a la llista enllaçada individualment.
Constructors a LinkedList:
Per crear una LinkedList, hem de crear un objecte de la classe LinkedList. La classe LinkedList consta de diversos constructors que permeten la possible creació de la llista. Els constructors disponibles en aquesta classe són els següents:
1. LinkedList(): Aquest constructor s'utilitza per crear una llista enllaçada buida. Si volem crear una LinkedList buida amb el nom ll, es pot crear com:
LinkedList ll = new LinkedList();
2. LinkedList (Col·lecció C): Aquest constructor s'utilitza per crear una llista ordenada que conté tots els elements d'una col·lecció especificada, tal com retorna l'iterador de la col·lecció. Si volem crear una LinkedList amb el nom ll, llavors, es pot crear com:
LinkedList ll = nova LinkedList(C);
Mètodes per a Java LinkedList:
| Mètode | Descripció |
|---|---|
| afegir (índex int, element E) | Aquest mètode Insereix l'element especificat a la posició especificada d'aquesta llista. |
| afegir (I i) | Aquest mètode afegeix l'element especificat al final d'aquesta llista. |
| addAll(índex int, col·lecció c) | Aquest mètode Insereix tots els elements de la col·lecció especificada en aquesta llista, començant per la posició especificada. |
| addAll(Col·lecció c) | Aquest mètode afegeix tots els elements de la col·lecció especificada al final d'aquesta llista, en l'ordre en què són retornats per l'iterador de la col·lecció especificada. |
| afegirPrimer(E e) | Aquest mètode Insereix l'element especificat al principi d'aquesta llista. |
| addLast(E e) | Aquest mètode afegeix l'element especificat al final d'aquesta llista. |
| clar () | Aquest mètode elimina tots els elements d'aquesta llista. |
| clonar () | Aquest mètode retorna una còpia superficial d'aquesta LinkedList. |
| conté (Objecte o) | Aquest mètode retorna true si aquesta llista conté l'element especificat. |
| descendentIterator() | Aquest mètode retorna un iterador sobre els elements d'aquesta deque en ordre seqüencial invers. |
| element() | Aquest mètode recupera, però no elimina, el cap (primer element) d'aquesta llista. |
| obtenir (índex int) | Aquest mètode retorna l'element a la posició especificada en aquesta llista. |
| getFirst() | Aquest mètode retorna el primer element d'aquesta llista. |
| getLast() | Aquest mètode retorna l'últim element d'aquesta llista. |
| indexOf(Objecte o) | Aquest mètode retorna l'índex de la primera ocurrència de l'element especificat en aquesta llista, o -1 si aquesta llista no conté l'element. |
| lastIndexOf(Objecte o) | Aquest mètode retorna l'índex de l'última ocurrència de l'element especificat en aquesta llista, o -1 si aquesta llista no conté l'element. |
| listIterator (índex int) | Aquest mètode retorna un iterador de llista dels elements d'aquesta llista (en la seqüència adequada), començant a la posició especificada de la llista. |
| oferta (E e) | Aquest mètode Afegeix l'element especificat com a cua (últim element) d'aquesta llista. |
| offerFirst (E i) | Aquest mètode Insereix l'element especificat al capdavant d'aquesta llista. |
| ofertaLast(E e) | Aquest mètode Insereix l'element especificat al final d'aquesta llista. |
| ullada() | Aquest mètode recupera, però no elimina, el cap (primer element) d'aquesta llista. |
| peekFirst () | Aquest mètode recupera, però no elimina, el primer element d'aquesta llista o retorna null si aquesta llista està buida. |
| peekLast() | Aquest mètode recupera, però no elimina, l'últim element d'aquesta llista, o retorna null si aquesta llista està buida. |
| enquesta() | Aquest mètode recupera i elimina el cap (primer element) d'aquesta llista. |
| pollFirst() | Aquest mètode recupera i elimina el primer element d'aquesta llista, o retorna null si aquesta llista està buida. |
| enquestaLast() | Aquest mètode recupera i elimina l'últim element d'aquesta llista, o retorna null si aquesta llista està buida. |
| pop() | Aquest mètode mostra un element de la pila representada per aquesta llista. |
| empenta (E i) | Aquest mètode empeny un element a la pila representada per aquesta llista. |
| eliminar () | Aquest mètode recupera i elimina el cap (primer element) d'aquesta llista. |
| eliminar (índex int) | Aquest mètode elimina l'element a la posició especificada en aquesta llista. |
| eliminar (Objecte o) | Aquest mètode elimina la primera ocurrència de l'element especificat d'aquesta llista si està present. |
| removeFirst() | Aquest mètode elimina i retorna el primer element d'aquesta llista. |
| removeFirstOccurrence(Objecte o) | Aquest mètode elimina la primera ocurrència de l'element especificat en aquesta llista (quan travessa la llista de cap a final). |
| removeLast() | Aquest mètode elimina i retorna l'últim element d'aquesta llista. |
| removeLastOccurrence(Objecte o) | Aquest mètode elimina l'última ocurrència de l'element especificat en aquesta llista (quan travessa la llista de cap a final). |
| set(índex int, element E) | Aquest mètode substitueix l'element a la posició especificada en aquesta llista per l'element especificat. |
| mida () | Aquest mètode retorna el nombre d'elements d'aquesta llista. |
| divisor () | Aquest mètode crea un Spliterator d'enllaç tardà i de fallada ràpida sobre els elements d'aquesta llista. |
| toArray() | Aquest mètode retorna una matriu que conté tots els elements d'aquesta llista en la seqüència adequada (del primer al darrer element). |
| toArray(T[] a) | Aquest mètode retorna una matriu que conté tots els elements d'aquesta llista en la seqüència adequada (del primer al darrer element); el tipus d'execució de la matriu retornada és el de la matriu especificada. |
| toString() | Aquest mètode retorna una cadena que conté tots els elements d'aquesta llista en la seqüència adequada (des del primer fins a l'últim element), cada element està separat per comes i la cadena es troba entre claudàtors. |
A continuació es mostra la implementació de les operacions anteriors:
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);> >}> }> |
>
>Sortida
[D, A, E, B, C] [A]>
A la il·lustració anterior, AbstractList , CopyOnWriteArrayList i AbstractSequentialList són les classes que implementen la interfície de llista. Una funcionalitat independent s'implementa en cadascuna de les classes esmentades. Ells són:
- AbstractList: aquesta classe s'utilitza per implementar una llista no modificable, per a la qual només cal ampliar aquesta classe AbstractList i implementar només els mètodes get() i size(). CopyOnWriteArrayList: aquesta classe implementa la interfície de llista. És una versió millorada de ArrayList en què totes les modificacions (afegir, establir, eliminar, etc.) s'implementen fent una còpia nova de la llista.
Realització de diverses operacions a LinkedList:
- Afegint elements
- Elements d'actualització
- Eliminació d'elements
- Iteració sobre elements
- A Array();
- Mida ();
- eliminar Primer();
- eliminar l'últim();
Operació 1: Afegir Elements
Per afegir un element a una ArrayList, podem utilitzar el mètode add() . Aquest mètode està sobrecarregat per realitzar múltiples operacions basades en diferents paràmetres. Ells són:
- add(Object): Aquest mètode s'utilitza per afegir un element al final de la LinkedList. add(int index, Object): aquest mètode s'utilitza per afegir un element a un índex específic de la LinkedList.
A continuació es mostra la implementació de l'operació anterior:
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);> >}> }> |
>
>Sortida
[Geeks, For, Geeks]>
Operació 2: Elements canviants
Després d'afegir els elements, si volem canviar l'element, es pot fer mitjançant el mètode set() . Com que una LinkedList està indexada, l'índex de l'element fa referència a l'element que volem canviar. Per tant, aquest mètode pren un índex i l'element actualitzat que cal inserir en aquest índex.
A continuació es mostra la implementació de l'operació anterior:
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);> >}> }> |
cadena a objecte json
>
>Sortida
Initial LinkedList [Geeks, Geeks, Geeks] Updated LinkedList [Geeks, For, Geeks]>
Operació 3: Eliminació d'elements
Per eliminar un element d'una LinkedList, podem utilitzar el mètode remove() . Aquest mètode està sobrecarregat per realitzar múltiples operacions basades en diferents paràmetres. Ells són:
- remove(Object): aquest mètode s'utilitza per eliminar simplement un objecte de la LinkedList. Si hi ha diversos objectes d'aquest tipus, s'elimina la primera ocurrència de l'objecte. remove(índex int): com que una LinkedList està indexada, aquest mètode pren un valor enter que simplement elimina l'element present en aquest índex específic a LinkedList. Després d'eliminar l'element i els índexs dels elements s'actualitzen, també s'actualitza l'objecte de LinkedList donant una nova llista després de la supressió de l'element/s.
A continuació es mostra la implementació de l'operació anterior:
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);> >}> }> |
>
java int a char
>Sortida
Initial LinkedList [Geeks, For, Geeks] After the Index Removal [Geeks, Geeks] After the Object Removal [Geeks]>
Operació 4: iteració de la LinkedList
Hi ha diverses maneres d'iterar a través de LinkedList. Les maneres més famoses són utilitzant el bucle for bàsic en combinació amb un mètode get() per obtenir l'element en un índex específic i el bucle for avançat.
A continuació es mostra la implementació de l'operació anterior:
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 + ' '); } }> |
>
>Sortida
Geeks For Geeks Geeks For Geeks>
Operació 4: Llista enllaçada a To Array utilitzant 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+>' '>);> >}> }> |
>
>Sortida
LinkedList: [123, 12, 11, 1134] After converted LinkedList to Array: 123 12 11 1134>
Operació 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());> >}> }> |
>
>Sortida
The size of the linked list is: 2>
Operació 7 – removeFirst();
conté en cadena
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);> >}> }> |
>
>Sortida
LinkedList:[10, 20, 30] The remove first element is: 10 Final LinkedList:[20, 30]>
Operació 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);> >}> }> |
>
>Sortida
LinkedList:[10, 20, 30] The last element is removed: 30 Final LinkedList:[10, 20] The last element is removed: 20 Final LinkedList:[10]>
La classe LinkedList a Java forma part del Java Collections Framework i proporciona una implementació de llista enllaçada de la interfície List. Permet l'emmagatzematge i la recuperació d'elements en una estructura de dades de llista doblement enllaçada, on cada element està vinculat als seus elements predecessors i successors.
Aquí teniu un exemple senzill que demostra com utilitzar una LinkedList a 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);> >}> >}> }> |
>
>Sortida
0 1 2 3 4>
Avantatges d'utilitzar LinkedList a Java:
- Mida dinàmica: igual que amb Vector, la mida d'una LinkedList pot créixer o reduir-se dinàmicament, de manera que no us haureu de preocupar per establir una mida inicial.
- Insercions i supressions eficients: LinkedList és una estructura de dades eficient per inserir o suprimir elements al centre de la llista perquè només cal canviar els enllaços entre elements, en lloc de desplaçar tots els elements després del punt d'inserció o supressió.
- Iteració flexible: amb una llista enllaçada, podeu iterar de manera eficient a través de la llista en qualsevol adreça, ja que cada element té una referència tant al seu predecessor com als elements successors.
Desavantatges d'utilitzar LinkedList a Java:
- Rendiment: LinkedList té un rendiment més lent que ArrayList quan es tracta d'accedir a elements individuals. Això es deu al fet que cal recórrer la llista per arribar a l'element desitjat, mentre que amb ArrayList, simplement podeu accedir a l'element desitjat mitjançant un índex.
- Sobrecàrrega de memòria: LinkedList requereix més memòria que ArrayList perquè cada element requereix memòria addicional per als enllaços als seus elements predecessors i successors.
Llibre de referència:
Un bon llibre de referència per aprendre sobre el Java Collections Framework i la LinkedList és Java Collections de Naftalin i Wadler. Aquest llibre ofereix una visió completa del marc de col·leccions de Java, inclòs LinkedList, i inclou molts exemples i exercicis per ajudar-vos a entendre com utilitzar aquestes classes de manera eficaç.