Lista doppiamente concatenata
Ultimo aggiornamento
Una lista doppiamente concatenata è una lista concatenata in cui ogni nodo contiene due puntatori: next (verso il nodo successivo) e prev (verso quello precedente). Questo collegamento all'indietro in più ti permette di scorrere la lista in entrambe le direzioni e di eliminare un nodo in O(1) quando hai già un riferimento a esso, perché puoi raggiungere direttamente il predecessore invece di partire dalla testa. Premi play qui sopra per vedere i nodi collegarsi e ricollegarsi in entrambe le direzioni.
Il costo è un puntatore in più per nodo e più lavoro di gestione: ogni inserimento ed eliminazione deve aggiornare sia next sia prev sui vicini. È la struttura dietro molte deque e cache LRU, dove conta la rimozione veloce da entrambe le estremità.
Complessità temporale
| Operazione | Complessità | Note |
|---|---|---|
| Inserimento in testa/coda | O(1) | Con i puntatori head e tail |
| Eliminazione di un nodo noto | O(1) | Raggiunge prev direttamente, senza scorrere |
| Ricerca | O(n) | Sempre una scansione lineare |
| Accesso per indice | O(n) | Nessun accesso casuale |
Lista semplicemente e doppiamente concatenata
| Aspetto | Semplice | Doppia |
|---|---|---|
| Puntatori per nodo | 1 (next) | 2 (next + prev) |
| Scorrere all'indietro | No | Sì |
| Eliminare un nodo noto | O(n) (trovare prev) | O(1) |
| Consumo di memoria | Minore | Maggiore |
Esempio svolto
Costruzione di [10, 20, 30] aggiungendo in coda, poi eliminazione del nodo 20:
| Passo | Struttura | Azione |
|---|---|---|
| Inizio | null | Lista vuota: head e tail sono entrambi null |
| Aggiungi 10 | 10 | Primo nodo; head e tail puntano entrambi a esso, prev = next = null |
| Aggiungi 20 | 10 <-> 20 | Imposta 10.next = 20 e 20.prev = 10; tail = 20 |
| Aggiungi 30 | 10 <-> 20 <-> 30 | Imposta 20.next = 30 e 30.prev = 20; tail = 30 |
| Elimina 20 | 10 <-> 30 | Usando 20.prev e 20.next: imposta 10.next = 30 e 30.prev = 10 in O(1) |
Quando usare una lista doppiamente concatenata
| Usala quando | Evitala quando |
|---|---|
| Ti serve scorrere o unire pezzi di lista in entrambe le direzioni | Vai sempre e solo avanti: una lista semplicemente concatenata è più leggera |
Elimini nodi arbitrari di cui hai già un riferimento (O(1)) | Accedi soprattutto per posizione: usa un array per l'accesso O(1) |
| Implementi una deque, una cache LRU o una cronologia di annullamento a schermo | La memoria è poca: il puntatore prev in più raddoppia il costo dei collegamenti |
| Inserimenti e rimozioni avvengono spesso a entrambe le estremità | I dati sono pochi e cambiano di rado: le copie di array costano meno |
Codice Doubly Linked List
Un'implementazione di Doubly 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 Doubly Linked List in Python
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.prev = None5 self.next = None6
7
8class DoublyLinkedList:9 def __init__(self):10 self.head = None11 self.tail = None12
13 def append(self, value):14 node = Node(value)15 if self.tail is None:16 self.head = self.tail = node17 return18 # Wire both directions: old tail <-> new node19 node.prev = self.tail20 self.tail.next = node21 self.tail = node22
23 def prepend(self, value):24 node = Node(value)25 if self.head is None:26 self.head = self.tail = node27 return28 node.next = self.head29 self.head.prev = node30 self.head = node31
32 def forward(self):33 values, current = [], self.head34 while current:35 values.append(current.value)36 current = current.next37 return values38
39 def backward(self):40 values, current = [], self.tail41 while current:42 values.append(current.value)43 current = current.prev44 return values45
46
47lst = DoublyLinkedList()48for value in [2, 3, 4]:49 lst.append(value)50lst.prepend(1)51
52print("Forward: ", lst.forward())53print("Backward:", lst.backward())Codice Doubly Linked List in JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.prev = null;5 this.next = null;6 }7}8
9class DoublyLinkedList {10 constructor() {11 this.head = null;12 this.tail = null;13 }14
15 // Tail pointer makes append O(1)16 append(value) {17 const node = new Node(value);18 if (!this.tail) {19 this.head = node;20 this.tail = node;21 return;22 }23 node.prev = this.tail;24 this.tail.next = node;25 this.tail = node;26 }27
28 forward() {29 const out = [];30 for (let n = this.head; n; n = n.next) out.push(n.value);31 return out;32 }33
34 backward() {35 const out = [];36 for (let n = this.tail; n; n = n.prev) out.push(n.value);37 return out;38 }39}40
41const list = new DoublyLinkedList();42for (const value of [10, 20, 30, 40]) list.append(value);43console.log("Forward: ", list.forward().join(" <-> "));44console.log("Backward:", list.backward().join(" <-> "));Codice Doubly Linked List in Java
Java
1public class Main {2 static class Node {3 int value;4 Node prev, next;5 Node(int value) { this.value = value; }6 }7
8 static Node head, tail;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = tail = node; return; }13 node.prev = tail;14 tail.next = node;15 tail = node;16 }17
18 // Unlink in O(1) once found: fix both neighbor pointers19 static void delete(int value) {20 for (Node cur = head; cur != null; cur = cur.next) {21 if (cur.value != value) continue;22 if (cur.prev != null) cur.prev.next = cur.next; else head = cur.next;23 if (cur.next != null) cur.next.prev = cur.prev; else tail = cur.prev;24 return;25 }26 }27
28 public static void main(String[] args) {29 append(1);30 append(2);31 append(3);32 append(4);33
34 StringBuilder forward = new StringBuilder("Forward:");35 for (Node cur = head; cur != null; cur = cur.next) forward.append(" ").append(cur.value);36 System.out.println(forward);37
38 StringBuilder backward = new StringBuilder("Backward:");39 for (Node cur = tail; cur != null; cur = cur.prev) backward.append(" ").append(cur.value);40 System.out.println(backward);41
42 delete(3);43 StringBuilder after = new StringBuilder("After delete 3:");44 for (Node cur = head; cur != null; cur = cur.next) after.append(" ").append(cur.value);45 System.out.println(after);46 }47}Codice Doubly Linked List in C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* prev = nullptr;6 Node* next = nullptr;7 explicit Node(int v) : value(v) {}8};9
10struct DoublyLinkedList {11 Node* head = nullptr;12 Node* tail = nullptr;13
14 void append(int value) {15 Node* node = new Node(value);16 if (tail == nullptr) {17 head = tail = node;18 return;19 }20 node->prev = tail; // link both directions21 tail->next = node;22 tail = node;23 }24
25 void prepend(int value) {26 Node* node = new Node(value);27 if (head == nullptr) {28 head = tail = node;29 return;30 }31 node->next = head;32 head->prev = node;33 head = node;34 }35
36 void printForward() const {37 for (Node* cur = head; cur != nullptr; cur = cur->next) {38 std::cout << cur->value << " <-> ";39 }40 std::cout << "null\n";41 }42
43 void printBackward() const {44 for (Node* cur = tail; cur != nullptr; cur = cur->prev) {45 std::cout << cur->value << " <-> ";46 }47 std::cout << "null\n";48 }49};50
51int main() {52 DoublyLinkedList list;53 for (int value : {10, 20, 30}) list.append(value);54 list.prepend(5);55 std::cout << "Forward: ";56 list.printForward();57 std::cout << "Backward: ";58 list.printBackward();59 return 0;60}Codice Doubly Linked List in C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* prev;7 struct Node* next;8} Node;9
10Node* head = NULL;11Node* tail = NULL;12
13Node* newNode(int value) {14 Node* n = calloc(1, sizeof(Node));15 n->value = value;16 return n;17}18
19void append(int value) {20 Node* node = newNode(value);21 if (tail == NULL) {22 head = tail = node;23 return;24 }25 node->prev = tail; // link both directions26 tail->next = node;27 tail = node;28}29
30void prepend(int value) {31 Node* node = newNode(value);32 if (head == NULL) {33 head = tail = node;34 return;35 }36 node->next = head;37 head->prev = node;38 head = node;39}40
41void printForward(void) {42 for (Node* cur = head; cur != NULL; cur = cur->next) {43 printf("%d <-> ", cur->value);44 }45 printf("NULL\n");46}47
48void printBackward(void) {49 for (Node* cur = tail; cur != NULL; cur = cur->prev) {50 printf("%d <-> ", cur->value);51 }52 printf("NULL\n");53}54
55int main(void) {56 int values[] = {10, 20, 30};57 for (int i = 0; i < 3; i++) append(values[i]);58 prepend(5);59 printf("Forward: ");60 printForward();61 printf("Backward: ");62 printBackward();63 return 0;64}Domande frequenti sulla lista doppiamente concatenata
Qual è la differenza tra una lista semplicemente e una doppiamente concatenata?
Una lista semplicemente concatenata ha un puntatore per nodo (
next), quindi puoi solo andare avanti. Una lista doppiamente concatenata aggiunge un puntatore prev, che ti permette di scorrere all'indietro e di eliminare in O(1) un nodo di cui hai un riferimento, al costo di un puntatore in più per nodo e dell'aggiornamento di due collegamenti a ogni modifica.Quando vale la pena spendere la memoria extra di una lista doppiamente concatenata?
Quando ti serve scorrere all'indietro o eliminare in
O(1) nodi arbitrari che hai già come riferimento: i casi classici sono le deque (code a doppia estremità) e le cache LRU, dove le voci vengono spostate ed espulse spesso da entrambe le estremità.Perché una lista doppiamente concatenata può eliminare un nodo in O(1)?
Per rimuovere un nodo devi collegare il suo predecessore al suo successore. In una lista semplicemente concatenata dovresti partire dalla testa per trovare il predecessore (
O(n)); in una lista doppiamente concatenata il puntatore prev del nodo ti dà direttamente il predecessore, quindi il ricollegamento è O(1).Lista doppiamente concatenata o array: quale usare?
Usa un array quando ti serve accesso
O(1) per indice e un'iterazione che sfrutti bene la cache, e quando gli inserimenti avvengono soprattutto in fondo. Usa una lista doppiamente concatenata quando inserisci o rimuovi spesso in mezzo o alle due estremità avendo un riferimento al nodo, perché è O(1) contro lo spostamento O(n) di un array. Gli array vincono su memoria e località; la lista vince sulle modifiche strutturali.Cos'è un nodo sentinella in una lista doppiamente concatenata?
Un nodo sentinella (o fittizio) è un segnaposto che sta prima della testa e/o dopo la coda, così la lista non è mai davvero vuota. Elimina i controlli su
null per head, tail e per inserimenti ed eliminazioni ai bordi, permettendo a ogni operazione di seguire lo stesso codice di ricollegamento. Molte implementazioni reali di cache LRU usano due sentinelle per non dover gestire le estremità come casi speciali.Qual è il bug più comune quando si elimina da una lista doppiamente concatenata?
Dimenticare di aggiornare
head o tail quando elimini il primo o l'ultimo nodo, lasciando un puntatore pendente verso un nodo liberato. Controlla sempre se node.prev è null (aggiorna head) o se node.next è null (aggiorna tail) prima di ricollegare i vicini.Risorse correlate
Altre visualizzazioni
