La classe LinkedList in Java

Concetti Chiave
  • La classe LinkedList in Java fornisce una struttura dati di lista collegata che implementa le interfacce List, Deque e Queue.
  • LinkedList è una classe generica che consente di specificare il tipo di oggetti contenuti nella lista.
  • LinkedList offre operazioni efficienti per l'inserimento e la rimozione di elementi, specialmente all'inizio e alla fine della lista.
  • LinkedList consente l'accesso agli elementi tramite indici, ma le operazioni di accesso casuale possono essere più lente rispetto ad altre strutture dati come ArrayList.
  • La classe fornisce metodi per aggiungere, rimuovere e ottenere elementi, nonché per modificare i valori degli elementi esistenti.

La Classe LinkedList

La classe LinkedList estende AbstractSequentialList e implementa le interfacce List, Deque e Queue. Fornisce una struttura dati di lista collegata. LinkedList è una classe generica che ha questa dichiarazione:

class LinkedList<E>

Qui, E specifica il tipo di oggetti che la lista conterrà. LinkedList ha i due costruttori mostrati qui:

LinkedList()
LinkedList(Collection<? extends E> c)

Il primo costruttore costruisce una lista collegata vuota. Il secondo costruttore costruisce una lista collegata che è inizializzata con gli elementi della collezione c.

Poiché LinkedList implementa l'interfaccia Deque, abbiamo accesso ai metodi definiti da Deque:

  • Ad esempio, per aggiungere elementi all'inizio di una lista, possiamo usare addFirst() o offerFirst().
  • Per aggiungere elementi alla fine della lista, usiamo addLast() o offerLast().
  • Per ottenere il primo elemento, possiamo usare getFirst() o peekFirst().
  • Per ottenere l'ultimo elemento, usiamo getLast() o peekLast().
  • Per rimuovere il primo elemento, usiamo removeFirst() o pollFirst().
  • Per rimuovere l'ultimo elemento, usiamo removeLast() o pollLast().

Il seguente programma illustra l'uso di LinkedList:

// Dimostrazione di LinkedList in Java
import java.util.*;

class DemoLinkedList {

    public static void main(String[] args) {

        // Crea una LinkedList di stringhe.
        LinkedList<String> ll = new LinkedList<String>();

        // Aggiunge elementi alla LinkedList.
        ll.add("F");
        ll.add("B");
        ll.add("D");
        ll.add("E");
        ll.add("C");
        ll.addLast("Z");
        ll.addFirst("A");
        ll.add(1, "A2");
        System.out.println("Contenuti originali di ll: " + ll);

        // Rimuove elementi dalla LinkedList.
        ll.remove("F");
        ll.remove(2);
        System.out.println("Contenuti di ll dopo la cancellazione: "
                           + ll);

        // Rimuove primo e ultimo elemento.
        ll.removeFirst();
        ll.removeLast();
        System.out.println("ll dopo aver cancellato primo e ultimo: "
                           + ll);

        // Ottiene e imposta un valore.
        String valore = ll.get(2);
        ll.set(2, valore + " Cambiato");
        System.out.println("ll dopo il cambiamento: " + ll);
    }

}

L'output da questo programma è mostrato qui:

Contenuti originali di ll: [A, A2, F, B, D, E, C, Z]
Contenuti di ll dopo la cancellazione: [A, A2, D, E, C, Z]
ll dopo aver cancellato primo e ultimo: [A2, D, E, C]
ll dopo il cambiamento: [A2, D, E Cambiato, C]

Poiché LinkedList implementa l'interfaccia List, le chiamate a add(E) aggiungono elementi alla fine della lista, così come fanno le chiamate a addLast(). Per inserire elementi in una posizione specifica, usiamo la forma add(int, E) di add(), come illustrato dalla chiamata a add(1, "A2") nell'esempio.

Notiamo come il terzo elemento in ll viene cambiato impiegando chiamate a get() e set(). Per ottenere il valore corrente di un elemento, passiamo a get() l'indice al quale l'elemento è memorizzato. Per assegnare un nuovo valore a quell'indice, passiamo a set() l'indice e il suo nuovo valore.