In questo tutorial, impareremo in dettaglio Java LinkedList con l'aiuto di esempi.
La LinkedListclasse del framework delle collezioni Java fornisce la funzionalità della struttura dati della lista collegata (doppiamente lista collegata).
Java Double LinkedList
Ogni elemento in un elenco collegato è noto come nodo . Consiste di 3 campi:
- Prec : memorizza un indirizzo dell'elemento precedente nell'elenco. È
nullper il primo elemento - Avanti : memorizza l'indirizzo dell'elemento successivo nell'elenco. È
nullper l'ultimo elemento - Dati : memorizza i dati effettivi
Creazione di una LinkedList Java
Ecco come possiamo creare elenchi collegati in Java:
LinkedList linkedList = new LinkedList();
Qui, Tipo indica il tipo di un elenco collegato. Per esempio,
// create Integer type linked list LinkedList linkedList = new LinkedList(); // create String type linked list LinkedList linkedList = new LinkedList();
Esempio: creare LinkedList in Java
import java.util.LinkedList; class Main ( public static void main(String() args)( // create linkedlist LinkedList animals = new LinkedList(); // Add elements to LinkedList animals.add("Dog"); animals.add("Cat"); animals.add("Cow"); System.out.println("LinkedList: " + animals); ) )
Produzione
LinkedList: (Cane, Gatto, Mucca)
Nell'esempio sopra, abbiamo creato un LinkedListanimale con nome.
Qui abbiamo utilizzato il add()metodo per aggiungere elementi a LinkedList. Impareremo di più sul add()metodo più avanti in questo tutorial.
Lavorare su una LinkedList Java
Gli elementi negli elenchi collegati non vengono memorizzati in sequenza. Invece, sono sparsi e collegati tramite collegamenti ( Prec e Succ ).
Implementazione di Java LinkedList
Qui abbiamo 3 elementi in un elenco collegato.
- Dog - è il primo elemento che contiene null come indirizzo precedente e l'indirizzo di Cat come indirizzo successivo
- Gatto - è il secondo elemento che contiene un indirizzo di Cane come indirizzo precedente e l'indirizzo di Mucca come indirizzo successivo
- Mucca: è l'ultimo elemento che contiene l'indirizzo di Cat come indirizzo precedente e null come elemento successivo
Per saperne di più, visita la struttura dei dati di LinkedList.
Metodi di Java LinkedList
LinkedListfornisce vari metodi che ci consentono di eseguire diverse operazioni in elenchi collegati. In questo tutorial esamineremo quattro operatori di LinkedList comunemente usati:
- Aggiungi elementi
- Elementi di accesso
- Cambia elementi
- Rimuovi elementi
1. Aggiungere elementi a un LinkedList
Possiamo usare il add()metodo per aggiungere un elemento (nodo) alla fine della LinkedList. Per esempio,
import java.util.LinkedList; class Main ( public static void main(String() args)( // create linkedlist LinkedList animals = new LinkedList(); // add() method without the index parameter animals.add("Dog"); animals.add("Cat"); animals.add("Cow"); System.out.println("LinkedList: " + animals); // add() method with the index parameter animals.add(1, "Horse"); System.out.println("Updated LinkedList: " + animals); ) )
Produzione
LinkedList: (Dog, Cat, Cow) Aggiornato LinkedList: (Dog, Horse, Cat, Cow)
Nell'esempio precedente, abbiamo creato una LinkedList denominata animali. Qui abbiamo utilizzato il add()metodo per aggiungere elementi agli animali.
Notare la dichiarazione,
animals.add(1, "Horse");
Qui abbiamo utilizzato il parametro del numero di indice . È un parametro opzionale che specifica la posizione in cui viene aggiunto il nuovo elemento.
Per ulteriori informazioni sull'aggiunta di elementi a LinkedList, visitare il programma Java per aggiungere elementi a LinkedList.
2. Accedere agli elementi di LinkedList
Il get()metodo della classe LinkedList viene utilizzato per accedere a un elemento da LinkedList. Per esempio,
import java.util.LinkedList; class Main ( public static void main(String() args) ( LinkedList languages = new LinkedList(); // add elements in the linked list languages.add("Python"); languages.add("Java"); languages.add("JavaScript"); System.out.println("LinkedList: " + languages); // get the element from the linked list String str = languages.get(1); System.out.print("Element at index 1: " + str); ) )
Produzione
LinkedList: (Python, Java, JavaScript) Elemento all'indice 1: Java
Nell'esempio sopra, abbiamo utilizzato il get()metodo con il parametro 1 . Qui, il metodo restituisce l'elemento all'indice 1 .
Possiamo anche accedere agli elementi della LinkedList usando iterator()il listIterator()metodo e. Per saperne di più, visita il programma Java per accedere agli elementi di LinkedList.
3. Modificare gli elementi di un LinkedList
Il set()metodo di LinkedListclasse viene utilizzato per modificare gli elementi della LinkedList. Per esempio,
import java.util.LinkedList; class Main ( public static void main(String() args) ( LinkedList languages = new LinkedList(); // add elements in the linked list languages.add("Java"); languages.add("Python"); languages.add("JavaScript"); languages.add("Java"); System.out.println("LinkedList: " + languages); // change elements at index 3 languages.set(3, "Kotlin"); System.out.println("Updated LinkedList: " + languages); ) )
Produzione
LinkedList: (Java, Python, JavaScript, Java) Aggiornato LinkedList: (Java, Python, JavaScript, Kotlin)
Nell'esempio precedente, abbiamo creato una LinkedList denominata languages. Notare la linea,
languages.set(3, "Kotlin");
Qui, il set()metodo cambia l'elemento all'indice 3 in Kotlin.
4. Rimuovere l'elemento da un LinkedList
The remove() method of the LinkedList class is used to remove an element from the LinkedList. For example,
import java.util.LinkedList; class Main ( public static void main(String() args) ( LinkedList languages = new LinkedList(); // add elements in LinkedList languages.add("Java"); languages.add("Python"); languages.add("JavaScript"); languages.add("Kotlin"); System.out.println("LinkedList: " + languages); // remove elements from index 1 String str = languages.remove(1); System.out.println("Removed Element: " + str); System.out.println("Updated LinkedList: " + languages); ) )
Output
LinkedList: (Java, Python, JavaScript, Kotlin) Removed Element: Python New LinkedList: (Java, JavaScript, Kotlin)
Here, the remove() method takes the index number as the parameter. And, removes the element specified by the index number.
To learn more about removing elements from the linkedlist, visit the Java program to remove elements from LinkedList…
Other Methods
| Methods | Description |
|---|---|
contains() | checks if the LinkedList contains the element |
indexOf() | returns the index of the first occurrence of the element |
lastIndexOf() | returns the index of the last occurrence of the element |
clear() | removes all the elements of the LinkedList |
iterator() | returns an iterator to iterate over LinkedList |
LinkedList as Deque and Queue
Since the LinkedList class also implements the Queue and the Deque interface, it can implement methods of these interfaces as well. Here are some of the commonly used methods:
| Methods | Descriptions |
|---|---|
addFirst() | adds the specified element at the beginning of the linked list |
addLast() | adds the specified element at the end of the linked list |
getFirst() | returns the first element |
getLast() | returns the last element |
removeFirst() | removes the first element |
removeLast() | removes the last element |
peek() | returns the first element (head) of the linked list |
poll() | returns and removes the first element from the linked list |
offer() | adds the specified element at the end of the linked list |
Example: Java LinkedList as Queue
import java.util.LinkedList; import java.util.Queue; class Main ( public static void main(String() args) ( Queue languages = new LinkedList(); // add elements languages.add("Python"); languages.add("Java"); languages.add("C"); System.out.println("LinkedList: " + languages); // access the first element String str1 = languages.peek(); System.out.println("Accessed Element: " + str1); // access and remove the first element String str2 = languages.poll(); System.out.println("Removed Element: " + str2); System.out.println("LinkedList after poll(): " + languages); // add element at the end languages.offer("Swift"); System.out.println("LinkedList after offer(): " + languages); ) )
Output
LinkedList: (Python, Java, C) Accessed Element: Python Removed Element: Python LinkedList after poll(): (Java, C) LinkedList after offer(): (Java, C, Swift)
Example: LinkedList as Deque
import java.util.LinkedList; import java.util.Deque; class Main ( public static void main(String() args)( Deque animals = new LinkedList(); // add element at the beginning animals.add("Cow"); System.out.println("LinkedList: " + animals); animals.addFirst("Dog"); System.out.println("LinkedList after addFirst(): " + animals); // add elements at the end animals.addLast("Zebra"); System.out.println("LinkedList after addLast(): " + animals); // remove the first element animals.removeFirst(); System.out.println("LinkedList after removeFirst(): " + animals); // remove the last element animals.removeLast(); System.out.println("LinkedList after removeLast(): " + animals); ) )
Output
LinkedList: (Cow) LinkedList after addFirst(): (Dog, Cow) LinkedList after addLast(): (Dog, Cow, Zebra) LinkedList after removeFirst(): (Cow, Zebra) LinkedList after removeLast(): (Cow)
Iterating through LinkedList
We can use the Java for-each loop to iterate through LinkedList. For example,
import java.util.LinkedList; class Main ( public static void main(String() args) ( // Creating a linked list LinkedList animals = new LinkedList(); animals.add("Cow"); animals.add("Cat"); animals.add("Dog"); System.out.println("LinkedList: " + animals); // Using forEach loop System.out.println("Accessing linked list elements:"); for(String animal: animals) ( System.out.print(animal); System.out.print(", "); ) ) )
Output
LinkedList: (Cow, Cat, Dog) Accessing linked list elements: Cow, Cat, Dog,
LinkedList Vs. ArrayList
Both the Java ArrayList and LinkedList implements the List interface of the Collections framework. However, there exists some difference between them.
| LinkedList | ArrayList |
|---|---|
Implements List, Queue, and Deque interfaces. | Implements List interface. |
| Stores 3 values (previous address, data, and next address) in a single position. | Memorizza un singolo valore in una singola posizione. |
| Fornisce l'implementazione dell'elenco a doppio collegamento. | Fornisce un'implementazione di array ridimensionabile. |
Ogni volta che viene aggiunto un elemento preve l' nextindirizzo viene modificato. | Ogni volta che viene aggiunto un elemento, tutti gli elementi dopo quella posizione vengono spostati. |
| Per accedere a un elemento, dobbiamo iterare dall'inizio all'elemento. | Può accedere in modo casuale agli elementi utilizzando gli indici. |
Nota : possiamo anche creare una LinkedList utilizzando le interfacce in Java. Per esempio,
// create linkedlist using List List animals1 = new LinkedList(); // creating linkedlist using Queue Queue animals2 = new LinkedList(); // creating linkedlist using Deque Deque animals3 = new LinkedList();
In questo caso, se la LinkedList viene creata utilizzando un'interfaccia, non possiamo utilizzare i metodi forniti da altre interfacce. Cioè, gli animali1 non possono usare metodi specifici per Queuee Dequeinterfacce.
