Struttura dati elenco collegato in Java

Diverse strutture di dati vengono create per scopi diversi. Potresti conoscere ArrayList (in caso contrario, ti consigliamo di leggerlo prima). In questo articolo, impareremo a conoscere LinkedList e capiremo a cosa serve questa raccolta. Se guardi nella sorgente del codice della classe LinkedList Java 8 (o versione successiva del linguaggio) (sul sito Web Oracle o nel tuo IDE, in caso di IDEA: crtl + B sul nome della classe) vedrai la seguente dichiarazione:

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

Al momento l'informazione più importante dal codice è il fatto che LinkedList implementa le interfacce List e Deque . L'interfaccia Elenco mantiene la sequenza di aggiunta di elementi e consente l'accesso all'elemento tramite indice. La coda "ordinaria" supporta l'aggiunta di elementi alla fine e l'estrazione dall'inizio. Deque è una coda bidirezionale e supporta l'aggiunta e la rimozione di elementi da entrambi i lati. Potresti pensarlo come una combinazione di stack e coda. Quindi, LinkedList è un'implementazione di questi due e ci consente di creare una coda bidirezionale composta da qualsiasi oggetto incluso null. Lista collegataè una raccolta di elementi. Possiamo vederlo nel codice sorgente della classe, stavolta prestando attenzione ai campi:

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

Ogni elemento, di solito lo chiamiamo Node , contiene un oggetto e fa riferimento a due oggetti vicini: il precedente e il successivo. Quindi, non è molto efficace in termini di utilizzo della memoria. Poiché LinkedList è in realtà una struttura bidirezionale, possiamo facilmente aggiungere o rimuovere elementi da entrambi i lati.

Costruttori LinkedList

Tornando al codice sorgente, possiamo scoprire che LinkedList ha due costruttori

• LinkedList() senza parametri viene utilizzato per costruire un elenco vuoto.
• >LinkedList(Collection<? extends E> c) serve per creare un elenco contenente gli elementi della raccolta specificata, nell'ordine in cui vengono restituiti dall'iteratore della raccolta.

Dichiarazione LinkedList

Infatti una lista collegata (Java o in qualsiasi altro linguaggio) è costituita da una sequenza di nodi. Ogni nodo è progettato per memorizzare un oggetto di un tipo definito durante la creazione. Quindi per creare LinkedList , il codice Java è il seguente:

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

Abbiamo un oggetto per mantenere una sequenza di numeri interi e collegamenti ai vicini. Tuttavia, al momento è vuoto.

Operazioni principali di LinkedList

Come al solito, nel caso delle raccolte puoi inserire elementi in LinkedList (alla fine o al centro), rimuoverli da lì e ottenere un elemento per indice. Quindi eccoli:

• add(E elemento) Aggiunge l'elemento specificato alla fine di questo elenco;
• add(int index, E element) Inserisce l' elemento nella posizione specificata index ;
• get(int index) Restituisce l'elemento nella posizione specificata in questo elenco;
• remove(int index) Rimuove l'elemento che si trova nella posizione index;
• remove(Object o) Rimuove la prima occorrenza di ? o elemento da questo elenco se è presente.
• remove() Recupera e rimuove il primo elemento dell'elenco.

Implementazione di elenchi collegati in Java, aggiunta e rimozione di elementi. Esempio

Proviamo queste operazioni con la pratica. Innanzitutto, implementazione Java LinkedList: creazione di una LinkedList of Strings, aggiungendo lì 3 elementi. Quindi rimuoverne uno, quindi aggiungerne uno nel mezzo.

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);
   }

Il risultato dell'esecuzione di questo programma:

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 fa parte del framework Collection , è possibile utilizzare Iterator per rimuovere elementi, nonché un iteratore speciale per gli elenchi: ListIterator . Inoltre, le operazioni con iteratore forniscono i principali vantaggi della classe LinkedList : buone prestazioni delle operazioni di inserimento/cancellazione. Usando Iterator potresti ottenere un tempo costante per loro. Più avanti in questo articolo, scriveremo un esempio di codice per confrontare ArrayList e LinkedList+Iterator

• Iterator.remove() rimuove l'ultimo elemento restituito da questo iteratore.
• ListIterator.add(E elemento) inserisce un elemento nell'elenco

Esempio Java LinkedList: come funziona Iterator

Qui abbiamo un piccolo codice di esempio Java LinkedList , in cui proviamo ad aggiungere ed eliminare tramite 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);
 
   }
}

Il risultato dell'esecuzione di questo programma:

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

Altre operazioni Java LinkedList :

• addFirst() , addLast() aggiungono un elemento all'inizio/fine di una lista
• clear() rimuove tutti gli elementi dalla lista
• contains(Object o) restituisce true se la lista contiene l'elemento o.
• indexOf(Object o) restituisce l'indice della prima occorrenza dell'elemento o, oppure -1 se non è nell'elenco.
• set(int index, E element) sostituisce l'elemento nella posizione dell'indice con l'elemento
• size() Restituisce la quantità di elementi nell'elenco.
• toArray() restituisce un array contenente tutti gli elementi della lista dal primo all'ultimo elemento.

A proposito, essendo una coda di due dimensioni, LinkedList in Java ha operazioni specifiche per lo stack:

• pop() che estrae un elemento dallo stack (rappresentato dalla lista)
• push(E e) che inserisce un elemento nello stack (rappresentato da questa lista)

Come invertire LinkedList: esempio

Ecco un piccolo esempio, un compito popolare ma facile per i principianti. Abbiamo una LinkedList e dovremmo invertirla. L'algoritmo più semplice è passare attraverso la LinkedList in ordine inverso e inserire ogni elemento in quello nuovo. Tuttavia, forse troverai un modo migliore? Ecco il codice del programma java della lista collegata inversa:

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;
   }
}

Il risultato:

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

LinkedList vs ArrayList: quando usare il primo

Sia LinkedList che ArrayList sono implementazioni dell'interfaccia List . LinkedList lo implementa con un elenco doppiamente collegato. ArrayList lo implementa utilizzando un array di ridimensionamento dinamico. Come già sai, ogni nodo di LinkedList contiene Oggetti e due riferimenti ai vicini. Ciò significa costi di memoria aggiuntivi per la memorizzazione di riferimenti tra elementi nel caso di Java LinkedList . ArrayList lo implementa con un array di ridimensionamento dinamico. Alcune delle operazioni LinkedList e ArrayList hanno lo stesso aspetto, ma funzionano in modo diverso. In ArrayListcaso, manipoli con array interni, in LinkedList - con riferimenti. ArrayList è l' implementazione List più popolare . Dovresti assolutamente usare ArrayList quando l'accesso all'indice è una priorità poiché queste operazioni vengono eseguite in un tempo costante. Anche l'aggiunta alla fine dell'elenco in media viene eseguita in un tempo costante. Inoltre, ArrayList non ha costi aggiuntivi per l'archiviazione di una serie di elementi. Puoi contare come Contro la velocità delle operazioni di inserimento e rimozione quando non è alla fine dell'elenco. Lista collegataè più utile in caso di esecuzione delle operazioni di inserimento e cancellazione in qualche modo: se si utilizzano iteratori si verifica in tempo costante. Le operazioni di accesso per indice vengono eseguite cercando dall'inizio alla fine (qualunque sia più vicino) all'elemento desiderato. Tuttavia, non dimenticare i costi aggiuntivi per l'archiviazione dei riferimenti tra gli elementi. Quindi qui operazioni LinkedList e ArrayList standard con tempi di esecuzione algoritmici. N si riferisce al numero di elementi già presenti nell'elenco. O(N) significa che nel peggiore dei casi dovremmo “percorrere” l'intera lista fino a trovare la posizione necessaria, ad esempio, per l'inserimento del nuovo elemento nella lista. O(1)significa che l'operazione avviene a tempo costante, indipendentemente dal numero di articoli.

Complessità temporale LinkedList

Complessità temporale ArrayList

Quando utilizzare LinkedList: Esempio

Sicuramente, ArrayList è l'implementazione di List più popolare . Tuttavia, potresti incontrare situazioni in cui le operazioni di aggiunta/rimozione sono necessarie troppo spesso. In tal caso, LinkedList insieme a Iterator potrebbe essere utile. Ecco un esempio. Abbiamo un lungo elenco e dovremmo eliminare ogni elemento da questo elenco. Facciamo questo compito con ArrayList e LinkedList + Iterator . Confrontiamo il tempo di ogni operazione e lo stampiamo nella console. Qui il codice:

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);
       }
   }
}

Risultato per ArrayList:

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

Risultato per LinkedList:

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

Come puoi vedere in questo caso LinkedList è molto più efficace. Diciamo la verità. Nello sviluppo di software reale, l'utilizzo di LinkedList è una specie di evento raro. Tuttavia, un professionista dovrebbe conoscere l'esistenza di questa struttura dati e i suoi vantaggi. Se nel codice reale LinkedList è un ospite raro, nelle interviste Java Junior è molto popolare. Eppure, ecco cosa ha scritto Joshua Bloch su LinkedList :

Componente aggiuntivo: elenco collegato singolarmente Java

Non esiste una Singly Linked List tra le Collection classiche in Java, Singly Linked List è una struttura in cui ogni nodo contiene un Oggetto e un riferimento al Nodo successivo, ma non per quello precedente. Java LinkedList è a due collegamenti, ma nessuno interferisce con te per creare la tua struttura dati, come un codice singolo> elenco collegato. Ecco alcuni passaggi per risolvere questi compiti:

1. Crea una classe Node con due attributi, data e next. Next è un riferimento al nodo successivo.
2. Crea la classe FirstLast con due attributi, head e tail.
3. Crea un metodo add() per aggiungere un nuovo nodo all'elenco. Controlla prima se l'elenco è vuoto ( head == null ). In tal caso, testa e coda si riferiscono al nuovo nodo. Se la lista non è vuota, il nuovo nodo verrà aggiunto alla fine, quindi l'attributo successivo della coda si riferisce al nodo aggiunto e il nuovo nodo diventa la coda della lista.

A proposito, puoi anche provare a creare la tua LinkedList come esercizio. Buona fortuna per il tuo apprendimento.