Linked list (lista concatenata)
Ultimo aggiornamento
Una lista concatenata memorizza una sequenza come una catena di nodi, in cui ogni nodo contiene un valore e un puntatore al nodo successivo. A differenza di un array, i nodi non sono contigui in memoria: per scorrere la lista segui i puntatori next. Premi play qui sopra per vedere i nodi collegati in testa e in coda, la ricerca di un valore percorrendo la catena e la rimozione di un nodo ricollegando un puntatore.
Inserire o eliminare in testa è O(1) perché basta spostare il puntatore alla testa. Raggiungere una posizione in mezzo o la coda è O(n) perché prima devi arrivarci. Questo compromesso, estremità economiche e nessun accesso casuale, è ciò che distingue una lista concatenata da un array.
Complessità temporale
| Operazione | Complessità | Note |
|---|---|---|
| Inserimento in testa | O(1) | Sposta head |
| Inserimento in coda | O(n) | Prima arriva alla fine (O(1) con un puntatore tail) |
| Ricerca | O(n) | Segui i puntatori next |
| Eliminazione della testa | O(1) | Sposta head oltre il nodo |
| Accesso per indice | O(n) | Nessun accesso casuale |
Lista concatenata e array a confronto
| Aspetto | Lista concatenata | Array |
|---|---|---|
| Memoria | Nodi sparsi + puntatori | Blocco contiguo |
| Accesso casuale | O(n) | O(1) |
| Inserimento/eliminazione in testa | O(1) | O(n) (spostamento) |
| Uso della cache | Scarso | Buono |
Esempio svolto
Costruzione della lista [10, 20], inserimento di 5 in testa, poi eliminazione di 20:
| Passo | Struttura | Azione |
|---|---|---|
| Inizio | head -> null | Lista vuota |
| Inserisci in testa 10 | head -> 10 -> null | Sposta head su un nuovo nodo il cui next è la vecchia testa (null) |
| Inserisci in coda 20 | head -> 10 -> 20 -> null | Arriva al nodo 10, imposta il suo next su un nuovo nodo 20 |
| Inserisci in testa 5 | head -> 5 -> 10 -> 20 -> null | Il nuovo nodo 5 punta alla vecchia testa 10; ora head punta a 5 |
| Elimina 20 | head -> 5 -> 10 -> null | Arriva a 10, cambia il suo next da 20 a null; il nodo 20 viene scollegato |
Quando usare una lista concatenata
| Usala quando | Evitala quando |
|---|---|
| Inserisci o elimini alle estremità (o in un nodo di cui hai il riferimento) molto più spesso di quanto accedi per indice | Ti serve un accesso casuale veloce per posizione (indicizzazione O(1)) |
| La dimensione cambia molto e non vuoi costi di ridimensionamento o copia | Esegui cicli stretti in cui la località della cache domina le prestazioni |
| Stai costruendo una coda, una pila o una lista di adiacenza | La memoria è poca: ogni nodo paga un puntatore in più per elemento |
| Ti servono riferimenti stabili ai nodi che sopravvivano agli inserimenti altrove | Leggi soprattutto e modifichi di rado, quindi un array è più semplice e veloce |
Codice Linked List
Un'implementazione di Linked List pulita ed eseguibile in Python, JavaScript, Java, C++, C. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Linked List in Python
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.next = None5
6
7class LinkedList:8 def __init__(self):9 self.head = None10
11 def append(self, value):12 node = Node(value)13 if self.head is None:14 self.head = node15 return16 current = self.head17 while current.next:18 current = current.next19 current.next = node20
21 def find(self, value):22 current = self.head23 while current:24 if current.value == value:25 return True26 current = current.next27 return False28
29 def delete(self, value):30 # Re-link the previous node around the match31 current, prev = self.head, None32 while current:33 if current.value == value:34 if prev is None:35 self.head = current.next36 else:37 prev.next = current.next38 return True39 prev, current = current, current.next40 return False41
42 def __str__(self):43 values, current = [], self.head44 while current:45 values.append(str(current.value))46 current = current.next47 return " -> ".join(values) + " -> None"48
49
50lst = LinkedList()51for value in [3, 7, 1, 9]:52 lst.append(value)53
54print("List: ", lst)55print("find(7): ", lst.find(7))56lst.delete(1)57print("After delete(1):", lst)Codice Linked List in JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.next = null;5 }6}7
8class LinkedList {9 constructor() {10 this.head = null;11 }12
13 append(value) {14 const node = new Node(value);15 if (!this.head) {16 this.head = node;17 return;18 }19 let current = this.head;20 while (current.next) current = current.next;21 current.next = node;22 }23
24 find(value) {25 for (let n = this.head; n; n = n.next) {26 if (n.value === value) return n;27 }28 return null;29 }30
31 delete(value) {32 if (!this.head) return false;33 if (this.head.value === value) {34 this.head = this.head.next;35 return true;36 }37 // Walk to the node just before the one to remove38 for (let n = this.head; n.next; n = n.next) {39 if (n.next.value === value) {40 n.next = n.next.next;41 return true;42 }43 }44 return false;45 }46
47 toArray() {48 const out = [];49 for (let n = this.head; n; n = n.next) out.push(n.value);50 return out;51 }52}53
54const list = new LinkedList();55for (const value of [10, 20, 30, 40]) list.append(value);56console.log("List:", list.toArray().join(" -> "));57console.log("find(30):", list.find(30) !== null);58list.delete(20);59console.log("After delete(20):", list.toArray().join(" -> "));Codice Linked List in Java
Java
1public class Main {2 static class Node {3 int value;4 Node next;5 Node(int value) { this.value = value; }6 }7
8 static Node head;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = node; return; }13 Node cur = head;14 while (cur.next != null) cur = cur.next;15 cur.next = node;16 }17
18 static boolean find(int value) {19 for (Node cur = head; cur != null; cur = cur.next) {20 if (cur.value == value) return true;21 }22 return false;23 }24
25 // Unlink the first node holding value26 static void delete(int value) {27 if (head == null) return;28 if (head.value == value) { head = head.next; return; }29 Node cur = head;30 while (cur.next != null && cur.next.value != value) cur = cur.next;31 if (cur.next != null) cur.next = cur.next.next;32 }33
34 static void print() {35 StringBuilder sb = new StringBuilder();36 for (Node cur = head; cur != null; cur = cur.next) {37 sb.append(cur.value).append(" -> ");38 }39 System.out.println(sb.append("null"));40 }41
42 public static void main(String[] args) {43 append(3); append(7); append(1); append(9);44 print();45 System.out.println("find 7: " + find(7));46 delete(7);47 print();48 System.out.println("find 7: " + find(7));49 }50}Codice Linked List in C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* next = nullptr;6 explicit Node(int v) : value(v) {}7};8
9struct LinkedList {10 Node* head = nullptr;11
12 void append(int value) {13 Node* node = new Node(value);14 if (head == nullptr) {15 head = node;16 return;17 }18 Node* cur = head;19 while (cur->next != nullptr) cur = cur->next;20 cur->next = node;21 }22
23 bool find(int value) const {24 for (Node* cur = head; cur != nullptr; cur = cur->next) {25 if (cur->value == value) return true;26 }27 return false;28 }29
30 void remove(int value) {31 if (head == nullptr) return;32 if (head->value == value) { // removing the head is a special case33 Node* old = head;34 head = head->next;35 delete old;36 return;37 }38 for (Node* cur = head; cur->next != nullptr; cur = cur->next) {39 if (cur->next->value == value) {40 Node* old = cur->next;41 cur->next = old->next;42 delete old;43 return;44 }45 }46 }47
48 void print() const {49 for (Node* cur = head; cur != nullptr; cur = cur->next) {50 std::cout << cur->value << " -> ";51 }52 std::cout << "null\n";53 }54};55
56int main() {57 LinkedList list;58 for (int value : {10, 20, 30, 40}) list.append(value);59 list.print();60 std::cout << std::boolalpha << "find(30): " << list.find(30) << "\n";61 list.remove(20);62 list.remove(10);63 list.print();64 return 0;65}Codice Linked List in C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* next;8} Node;9
10Node* head = NULL;11
12void append(int value) {13 Node* node = malloc(sizeof(Node));14 node->value = value;15 node->next = NULL;16 if (head == NULL) {17 head = node;18 return;19 }20 Node* cur = head;21 while (cur->next != NULL) cur = cur->next;22 cur->next = node;23}24
25bool find(int value) {26 for (Node* cur = head; cur != NULL; cur = cur->next) {27 if (cur->value == value) return true;28 }29 return false;30}31
32void deleteValue(int value) {33 if (head == NULL) return;34 if (head->value == value) { // removing the head is a special case35 Node* old = head;36 head = head->next;37 free(old);38 return;39 }40 for (Node* cur = head; cur->next != NULL; cur = cur->next) {41 if (cur->next->value == value) {42 Node* old = cur->next;43 cur->next = old->next;44 free(old);45 return;46 }47 }48}49
50void printList(void) {51 for (Node* cur = head; cur != NULL; cur = cur->next) {52 printf("%d -> ", cur->value);53 }54 printf("NULL\n");55}56
57int main(void) {58 int values[] = {10, 20, 30, 40};59 for (int i = 0; i < 4; i++) append(values[i]);60 printList();61 printf("find(30): %s\n", find(30) ? "true" : "false");62 deleteValue(20);63 deleteValue(10);64 printList();65 return 0;66}Domande frequenti sulla lista concatenata
Qual è la differenza tra una lista concatenata e un array?
Un array memorizza gli elementi in un unico blocco contiguo, dando accesso casuale
O(1) ma inserimenti ed eliminazioni O(n) che spostano gli elementi. Una lista concatenata memorizza i nodi ovunque in memoria collegandoli con puntatori, dando inserimenti ed eliminazioni O(1) in una posizione nota ma accesso O(n), perché devi percorrere la catena.Quando conviene usare una lista concatenata?
Le liste concatenate danno il meglio quando inserisci o rimuovi spesso alle estremità (o in un nodo di cui hai già un riferimento) e raramente ti serve l'accesso casuale: per esempio code, pile, liste di adiacenza e cache LRU. Se ti serve un accesso veloce per indice, di solito è meglio un array o un array dinamico.
Qual è la complessità temporale di una lista concatenata?
Inserire o eliminare in testa è
O(1). Cercare, o raggiungere la coda senza un puntatore tail, è O(n) perché segui i puntatori next uno per uno. Non c'è accesso casuale O(1): accedere per indice a una lista concatenata è O(n).Qual è la differenza tra una lista semplicemente e una doppiamente concatenata?
Una lista semplicemente concatenata memorizza solo un puntatore
next per nodo, quindi puoi scorrerla in una sola direzione ed eliminare un nodo richiede un riferimento al suo predecessore. Una lista doppiamente concatenata aggiunge un puntatore prev, che permette di scorrere all'indietro e di eliminare in O(1) un nodo di cui hai il riferimento, al costo di un puntatore in più per nodo e di più lavoro a ogni inserimento ed eliminazione.Perché inserire in coda è O(n) se inserire in testa è O(1)?
Inserire in testa ricollega solo il puntatore
head, un lavoro costante. Raggiungere la coda significa seguire i puntatori next dalla testa fino alla fine, cosa che è O(n). Tenere un puntatore tail separato rende anche l'inserimento in coda O(1), ed è per questo che le liste reali spesso tengono traccia di entrambe le estremità.Le liste concatenate hanno inserimento O(1) ovunque?
No, è un equivoco comune. L'inserimento in sé è
O(1) solo se hai già un puntatore al nodo dopo cui inserire. Trovare quella posizione per valore o per indice costa comunque O(n), perché devi percorrere la catena per arrivarci.Risorse correlate
Altre visualizzazioni
