0Pricing
Java Academy · Lezione

Internals di LinkedList

Esplori la struttura a nodi doppiamente concatenati di LinkedList e il relativo profilo di complessità temporale.

Internals di LinkedList è una lezione Java Academy gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Java Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Java Academy include 4 lezioni in totale.

Struttura interna di LinkedList

La LinkedList di Java è una lista doppiamente concatenata: ogni nodo contiene un riferimento al nodo precedente e a quello successivo, oltre al valore dell'elemento. A differenza di ArrayList, non esiste un array di supporto: la memoria viene allocata per ogni nodo.

class Node<T> {
    T data;
    Node<T> prev;
    Node<T> next;
    Node(T data) { this.data = data; }
}

Profilo della complessità temporale

Le caratteristiche delle prestazioni di LinkedList differiscono significativamente da quelle di ArrayList:

  • addFirst / addLast: O(1)
  • get(index): O(n): è necessario attraversare la lista dalla testa o dalla coda
  • remove(index): O(n) per trovare l'elemento, poi O(1) per scollegarlo
  • Attraversamento con Iterator: O(n)

Utilizzi LinkedList quando sono necessari frequenti inserimenti in testa o in coda, non per l'accesso casuale.

Creazione e attraversamento di una LinkedList

La creazione di una LinkedList e la sua iterazione seguono la stessa interfaccia List che già conosce. La differenza riguarda la struttura interna.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("Alice");
list.add("Bob");
list.add("Carol");

for (String name : list) {
    System.out.println(name);
}

System.out.println("First: " + list.getFirst()); // Alice
System.out.println("Last: "  + list.getLast());  // Carol

addFirst, addLast, removeFirst, removeLast

LinkedList espone operazioni sulla testa e sulla coda che ArrayList non offre in modo efficiente:

LinkedList<Integer> nums = new LinkedList<>();
nums.addLast(10);   // [10]
nums.addLast(20);   // [10, 20]
nums.addFirst(5);   // [5, 10, 20]

System.out.println(nums.removeFirst()); // 5  → [10, 20]
System.out.println(nums.removeLast());  // 20 → [10]

Scollegamento dei nodi: eliminazione O(1) dopo la ricerca

Una volta ottenuto un riferimento a un nodo tramite un iteratore, la rimozione ha complessità O(1), perché è necessario aggiornare solo i puntatori next/prev: non occorre spostare gli elementi come in ArrayList.

import java.util.*;

LinkedList<String> tasks = new LinkedList<>(List.of("A","B","C","D"));
Iterator<String> it = tasks.iterator();
while (it.hasNext()) {
    String t = it.next();
    if (t.equals("B") || t.equals("D")) {
        it.remove(); // O(1) unlink
    }
}
System.out.println(tasks); // [A, C]

Overhead di memoria rispetto ad ArrayList

Ogni nodo LinkedList contiene due riferimenti aggiuntivi (prev, next) oltre al riferimento all'elemento: circa 48 byte per voce su una JVM a 64 bit. ArrayList memorizza solo il riferimento all'elemento (8 byte) in un array contiguo.

Per dataset di grandi dimensioni con molte operazioni di lettura, ArrayList è generalmente più efficiente per la cache e utilizza meno memoria.

Operazioni Deque: stack e coda

LinkedList implementa l'interfaccia Deque, quindi può essere utilizzata sia come stack sia come coda.

import java.util.LinkedList;
import java.util.Deque;

// As a Queue (FIFO)
Deque<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
System.out.println(queue.poll()); // first

// As a Stack (LIFO)
Deque<String> stack = new LinkedList<>();
stack.push("bottom");
stack.push("top");
System.out.println(stack.pop()); // top

Panoramica di PriorityQueue

PriorityQueue è una coda basata su heap in cui l'elemento più piccolo, secondo l'ordinamento naturale o un comparator, viene sempre estratto per primo. NON è basata su una lista concatenata: utilizza un array che rappresenta un heap binario.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(40);
pq.offer(10);
pq.offer(25);

System.out.println(pq.poll()); // 10 (smallest)
System.out.println(pq.poll()); // 25
System.out.println(pq.poll()); // 40

PriorityQueue con Comparator personalizzato

Passi un Comparator per invertire l'ordinamento o ordinare in base a un campo personalizzato:

import java.util.*;

record Task(String name, int priority) {}

PriorityQueue<Task> tasks = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed() // highest first
);
tasks.offer(new Task("Low", 1));
tasks.offer(new Task("High", 10));
tasks.offer(new Task("Med", 5));

while (!tasks.isEmpty()) {
    System.out.println(tasks.poll().name());
}
// High, Med, Low

Scelta tra LinkedList e ArrayList

Regola generale:

  • Utilizzi ArrayList per l'accesso casuale, l'iterazione e nella maggior parte degli scenari.
  • Utilizzi LinkedList quando sono necessari frequenti inserimenti o rimozioni O(1) a entrambe le estremità e non serve l'accesso tramite indice.
  • Utilizzi PriorityQueue quando è necessaria un'elaborazione ordinata, ad esempio per la pianificazione di attività o l'algoritmo di Dijkstra.

Problemi comuni

Eviti di chiamare get(i) in un ciclo su una LinkedList: la complessità totale è O(n²):

LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) list.add(i);

// BAD: O(n^2) — each get(i) traverses from head
for (int i = 0; i < list.size(); i++) {
    int val = list.get(i); // slow!
}

// GOOD: O(n) — use iterator
for (int val : list) {
    // process val
}

Verifica rapida

Quale operazione di LinkedList ha complessità O(1) indipendentemente dalle dimensioni della lista?

Riepilogo: LinkedList e Deque

Punti chiave:

  • LinkedList è una lista doppiamente concatenata con operazioni O(1) sulla testa e sulla coda
  • L'accesso casuale (get/set tramite indice) ha complessità O(n)
  • Implementa Deque, quindi può essere utilizzata come stack o coda
  • PriorityQueue fornisce un'elaborazione ordinata tramite heap
  • Preferisca ArrayList nella maggior parte dei casi d'uso; LinkedList è vantaggiosa per frequenti modifiche in testa o in coda

Domande Frequenti

La lezione «Internals di LinkedList» è gratuita?

Sì — il testo completo di «Internals di LinkedList» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Java Academy, passa a CoddyKit PRO. Il corso Java Academy include 4 lezioni in totale.

Cosa imparerò in «Internals di LinkedList»?

Esplori la struttura a nodi doppiamente concatenati di LinkedList e il relativo profilo di complessità temporale. Eserciti Java Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Java Academy?

Non è richiesta alcuna esperienza precedente. Java Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.

Quanto tempo richiede la lezione «Internals di LinkedList»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Java Academy?

Sì. Ogni lezione Java Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

  1. Internals di LinkedList
  2. Operazioni su Deque: stack e queue
  3. LinkedList e ArrayList a confronto
  4. PriorityQueue per l'elaborazione ordinata
← Torna a Java Academy