L'elenco collegato fa parte di Quadro della raccolta presente nel pacchetto java.util. Questa classe è un'implementazione della struttura dati dell'elenco doppiamente collegato.
La differenza principale tra una lista concatenata normale e una lista doppiamente collegata è che una lista doppiamente concatenata contiene un puntatore extra, tipicamente chiamato puntatore precedente, insieme al puntatore successivo e ai dati presenti nella lista concatenata singola.
Costruttori nella LinkedList:
Per creare una LinkedList, dobbiamo creare un oggetto della classe LinkedList. La classe LinkedList è composta da vari costruttori che permettono l'eventuale creazione della lista. Di seguito sono riportati i costruttori disponibili in questa classe:
1. Lista collegata(): Questo costruttore viene utilizzato per creare un elenco collegato vuoto. Se desideriamo creare una LinkedList vuota con il nome ll, allora può essere creata come:
ListaCollegata ll = nuova ListaCollegata();
2. Lista collegata(Raccolta C): Questo costruttore viene utilizzato per creare un elenco ordinato che contiene tutti gli elementi di una raccolta specificata, come restituito dall'iteratore della raccolta. Se desideriamo creare una LinkedList con il nome ll, allora può essere creata come:
ListaCollegata ll = nuova ListaCollegata(C);
Metodi per Java LinkedList:
| Metodo | Descrizione |
|---|---|
| add(int indice, elemento E) | Questo metodo inserisce l'elemento specificato nella posizione specificata in questo elenco. |
| add(E e) | Questo metodo Aggiunge l'elemento specificato alla fine di questo elenco. |
| addAll(int indice, Collezione c) | Questo metodo inserisce tutti gli elementi nella raccolta specificata in questo elenco, a partire dalla posizione specificata. |
| addAll(Raccolta c) | Questo metodo Aggiunge tutti gli elementi nella raccolta specificata alla fine di questo elenco, nell'ordine in cui vengono restituiti dall'iteratore della raccolta specificata. |
| aggiungiPrimo(E e) | Questo metodo inserisce l'elemento specificato all'inizio di questo elenco. |
| aggiungiUltimo(E e) | Questo metodo Aggiunge l'elemento specificato alla fine di questo elenco. |
| chiaro() | Questo metodo rimuove tutti gli elementi da questo elenco. |
| clone() | Questo metodo restituisce una copia superficiale di questa LinkedList. |
| contiene(Oggetto o) | Questo metodo restituisce true se l'elenco contiene l'elemento specificato. |
| discendenteIteratore() | Questo metodo restituisce un iteratore sugli elementi di questa deque in ordine sequenziale inverso. |
| elemento() | Questo metodo recupera ma non rimuove l'intestazione (primo elemento) di questo elenco. |
| get(indice int) | Questo metodo restituisce l'elemento nella posizione specificata in questo elenco. |
| prendiPrimo() | Questo metodo restituisce il primo elemento in questo elenco. |
| prendiUltimo() | Questo metodo restituisce l'ultimo elemento in questo elenco. |
| indiceOf(Oggetto o) | Questo metodo restituisce l'indice della prima occorrenza dell'elemento specificato in questo elenco o -1 se questo elenco non contiene l'elemento. |
| ultimoIndiceOf(Oggetto o) | Questo metodo restituisce l'indice dell'ultima occorrenza dell'elemento specificato in questo elenco o -1 se questo elenco non contiene l'elemento. |
| listIterator(int indice) | Questo metodo restituisce un iteratore di elenco degli elementi in questo elenco (nella sequenza corretta), a partire dalla posizione specificata nell'elenco. |
| offerta(E e) | Questo metodo Aggiunge l'elemento specificato come coda (ultimo elemento) di questo elenco. |
| offertaPrima(E e) | Questo metodo inserisce l'elemento specificato all'inizio di questo elenco. |
| offertaUltimo(E e) | Questo metodo inserisce l'elemento specificato alla fine di questo elenco. |
| sbirciare() | Questo metodo recupera ma non rimuove l'intestazione (primo elemento) di questo elenco. |
| sbirciareFirst() | Questo metodo recupera, ma non rimuove, il primo elemento di questo elenco o restituisce null se questo elenco è vuoto. |
| sbirciareUltimo() | Questo metodo recupera, ma non rimuove, l'ultimo elemento di questo elenco o restituisce null se questo elenco è vuoto. |
| sondaggio() | Questo metodo recupera e rimuove la testa (primo elemento) di questo elenco. |
| sondaggioPrimo() | Questo metodo recupera e rimuove il primo elemento di questo elenco o restituisce null se questo elenco è vuoto. |
| sondaggioUltimo() | Questo metodo recupera e rimuove l'ultimo elemento di questo elenco o restituisce null se questo elenco è vuoto. |
| pop() | Questo metodo Estrae un elemento dallo stack rappresentato da questo elenco. |
| push(E e) | Questo metodo inserisce un elemento nello stack rappresentato da questo elenco. |
| rimuovere() | Questo metodo recupera e rimuove la testa (primo elemento) di questo elenco. |
| rimuovi(indice int) | Questo metodo rimuove l'elemento nella posizione specificata in questo elenco. |
| rimuovi(Oggetto o) | Questo metodo rimuove la prima occorrenza dell'elemento specificato dall'elenco, se presente. |
| rimuoviPrimo() | Questo metodo rimuove e restituisce il primo elemento da questo elenco. |
| rimuoviFirstOccurrence(Oggetto o) | Questo metodo rimuove la prima occorrenza dell'elemento specificato in questo elenco (quando si attraversa l'elenco dalla testa alla coda). |
| rimuoviUltimo() | Questo metodo rimuove e restituisce l'ultimo elemento da questo elenco. |
| rimuoviUltimaOccorrenza(Oggetto o) | Questo metodo rimuove l'ultima occorrenza dell'elemento specificato in questo elenco (quando si attraversa l'elenco dalla testa alla coda). |
| set(indice int, elemento E) | Questo metodo sostituisce l'elemento nella posizione specificata in questo elenco con l'elemento specificato. |
| misurare() | Questo metodo restituisce il numero di elementi in questo elenco. |
| divisore() | Questo metodo crea uno Spliterator con associazione tardiva e fail-fast sugli elementi in questo elenco. |
| toArray() | Questo metodo restituisce un array contenente tutti gli elementi di questo elenco nella sequenza corretta (dal primo all'ultimo elemento). |
| toArray(T[] a) | Questo metodo restituisce un array contenente tutti gli elementi di questo elenco nella sequenza corretta (dal primo all'ultimo elemento); il tipo di runtime dell'array restituito è quello dell'array specificato. |
| accordare() | Questo metodo restituisce una stringa contenente tutti gli elementi dell'elenco nella sequenza corretta (dal primo all'ultimo elemento), ogni elemento è separato da virgole e la stringa è racchiusa tra parentesi quadre. |
Di seguito l’implementazione delle operazioni sopra indicate:
Giava
// 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);> >}> }> |
>
>Produzione
[D, A, E, B, C] [A]>
Nell'illustrazione precedente, AbstractList , CopyOnWriteArrayList e AbstractSequentialList sono le classi che implementano l'interfaccia dell'elenco. In ciascuna delle classi menzionate è implementata una funzionalità separata. Sono:
- AbstractList: questa classe viene utilizzata per implementare una lista immodificabile, per la quale è necessario estendere solo questa classe AbstractList e implementare solo i metodi get() e size(). CopyOnWriteArrayList: questa classe implementa l'interfaccia dell'elenco. È una versione migliorata di ArrayList in cui tutte le modifiche (aggiunta, impostazione, rimozione, ecc.) vengono implementate creando una nuova copia dell'elenco.
Esecuzione di varie operazioni su LinkedList:
- Aggiunta di elementi
- Aggiornamento degli elementi
- Rimozione di elementi
- Iterazione sugli elementi
- Alla matrice();
- Misurare();
- rimuovi Primo();
- rimuovi ultimo();
Operazione 1: Aggiunta di elementi
Per aggiungere un elemento ad un ArrayList, possiamo usare il metodo add() . Questo metodo è sovraccaricato per eseguire più operazioni in base a parametri diversi. Sono:
- add(Object): questo metodo viene utilizzato per aggiungere un elemento alla fine della LinkedList. add(int indice, Oggetto): questo metodo viene utilizzato per aggiungere un elemento a un indice specifico nella LinkedList.
Di seguito è riportata l'implementazione dell'operazione di cui sopra:
Giava
// 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);> >}> }> |
>
>Produzione
[Geeks, For, Geeks]>
Operazione 2: Modifica degli elementi
Dopo aver aggiunto gli elementi, se desideriamo modificare l'elemento, possiamo farlo utilizzando il metodo set() . Poiché una LinkedList è indicizzata, l'elemento che desideriamo modificare viene referenziato dall'indice dell'elemento. Pertanto, questo metodo accetta un indice e l'elemento aggiornato che deve essere inserito in quell'indice.
Di seguito è riportata l'implementazione dell'operazione di cui sopra:
Giava
// 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);> >}> }> |
file Linux
>
>Produzione
Initial LinkedList [Geeks, Geeks, Geeks] Updated LinkedList [Geeks, For, Geeks]>
Operazione 3: Rimozione di elementi
Per rimuovere un elemento da una LinkedList, possiamo utilizzare il metodoremove() . Questo metodo è sovraccaricato per eseguire più operazioni in base a parametri diversi. Sono:
- rimuovi(Oggetto): questo metodo viene utilizzato per rimuovere semplicemente un oggetto dalla LinkedList. Se sono presenti più oggetti di questo tipo, viene rimossa la prima occorrenza dell'oggetto. rimuovi(int indice): poiché una LinkedList è indicizzata, questo metodo accetta un valore intero che rimuove semplicemente l'elemento presente in quell'indice specifico nella LinkedList. Dopo aver rimosso l'elemento e gli indici degli elementi vengono aggiornati, anche l'oggetto di LinkedList viene aggiornato fornendo un nuovo elenco dopo la cancellazione dell'elemento/i.
Di seguito è riportata l'implementazione dell'operazione di cui sopra:
Giava
// 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);> >}> }> |
>
>Produzione
Initial LinkedList [Geeks, For, Geeks] After the Index Removal [Geeks, Geeks] After the Object Removal [Geeks]>
Operazione 4: Iterazione della LinkedList
Esistono diversi modi per scorrere LinkedList. I modi più famosi consistono nell'utilizzare il ciclo for di base in combinazione con un metodo get() per ottenere l'elemento in un indice specifico e il ciclo for avanzato.
Di seguito è riportata l'implementazione dell'operazione di cui sopra:
rimuovere il primo carattere in Excel
Giava
// 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 + ' '); } }> |
>
>Produzione
Geeks For Geeks Geeks For Geeks>
Operazione 4: elenco collegato a To Array utilizzando toArray();
Giava
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+>' '>);> >}> }> |
>
>Produzione
LinkedList: [123, 12, 11, 1134] After converted LinkedList to Array: 123 12 11 1134>
Operazione 5-size();
Giava
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());> >}> }> |
>
>Produzione
The size of the linked list is: 2>
Operazione 7 – rimuoviPrimo();
Giava
array Java dinamico
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);> >}> }> |
>
>Produzione
LinkedList:[10, 20, 30] The remove first element is: 10 Final LinkedList:[20, 30]>
Operazione 8-removelast();
Giava
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);> >}> }> |
>
>Produzione
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 in Java fa parte di Java Collections Framework e fornisce un'implementazione dell'elenco collegato dell'interfaccia List. Consente l'archiviazione e il recupero di elementi in una struttura dati di elenco doppiamente collegata, in cui ogni elemento è collegato al suo predecessore e agli elementi successori.
Ecco un semplice esempio che dimostra come utilizzare una LinkedList in Java:
Giava
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);> >}> >}> }> |
>
>Produzione
0 1 2 3 4>
Vantaggi dell'utilizzo di LinkedList in Java:
- Dimensione dinamica: come con Vector, la dimensione di una LinkedList può aumentare o ridursi dinamicamente, quindi non devi preoccuparti di impostare una dimensione iniziale.
- Inserzioni ed eliminazioni efficienti: LinkedList è una struttura dati efficiente per inserire o eliminare elementi al centro dell'elenco perché è necessario modificare solo i collegamenti tra gli elementi, anziché spostare tutti gli elementi dopo il punto di inserimento o eliminazione.
- Iterazione flessibile: con un elenco collegato, è possibile scorrere in modo efficiente l'elenco in entrambe le direzioni, poiché ogni elemento ha un riferimento sia al suo elemento predecessore che a quello successivo.
Svantaggi dell'utilizzo di LinkedList in Java:
- Prestazioni: LinkedList ha prestazioni più lente rispetto ad ArrayList quando si tratta di accedere a singoli elementi. Questo perché è necessario attraversare l'elenco per raggiungere l'elemento desiderato, mentre con ArrayList puoi semplicemente accedere all'elemento desiderato utilizzando un indice.
- Overhead di memoria: LinkedList richiede più memoria di ArrayList perché ogni elemento richiede memoria aggiuntiva per i collegamenti agli elementi predecessore e successore.
Libro di consultazione:
Un buon libro di riferimento per conoscere Java Collections Framework e LinkedList è Java Collections di Naftalin e Wadler. Questo libro fornisce uno sguardo completo al framework delle raccolte Java, incluso LinkedList, e include molti esempi ed esercizi per aiutarti a capire come utilizzare queste classi in modo efficace.