Lista doblemente enlazada
Última actualización
Una lista doblemente enlazada es una lista enlazada donde cada nodo tiene dos punteros: next (al nodo siguiente) y prev (al anterior). Ese enlace hacia atrás adicional permite recorrer en ambas direcciones y eliminar un nodo en O(1) cuando ya tienes una referencia a él, porque puedes llegar directamente a su predecesor en lugar de recorrer desde la cabeza. Pulsa reproducir arriba para ver cómo los nodos se enlazan y reenlazan en ambos sentidos.
El coste es un puntero adicional por nodo y más gestión: cada inserción y eliminación debe actualizar tanto next como prev en los vecinos. Es la estructura detrás de muchas colas dobles (deques) y cachés LRU, donde importa la eliminación rápida por ambos extremos.
Complejidad temporal
| Operación | Complejidad | Notas |
|---|---|---|
| Insertar en cabeza/cola | O(1) | Con punteros a cabeza y cola |
| Eliminar un nodo conocido | O(1) | Se llega a prev directamente, sin recorrido |
| Búsqueda | O(n) | Sigue siendo un escaneo lineal |
| Acceso por índice | O(n) | Sin acceso aleatorio |
Lista simplemente enlazada vs doblemente enlazada
| Aspecto | Simple | Doble |
|---|---|---|
| Punteros por nodo | 1 (next) | 2 (next + prev) |
| Recorrer hacia atrás | No | Sí |
| Eliminar un nodo conocido | O(n) (buscar prev) | O(1) |
| Sobrecarga de memoria | Menor | Mayor |
Ejemplo resuelto
Construyendo [10, 20, 30] añadiendo al final y luego eliminando el nodo 20:
| Paso | Estructura | Acción |
|---|---|---|
| Inicio | null | Lista vacía: head y tail son ambos null |
| Añadir 10 | 10 | Primer nodo; head y tail apuntan a él, prev = next = null |
| Añadir 20 | 10 <-> 20 | Se asigna 10.next = 20 y 20.prev = 10; tail = 20 |
| Añadir 30 | 10 <-> 20 <-> 30 | Se asigna 20.next = 30 y 30.prev = 20; tail = 30 |
| Eliminar 20 | 10 <-> 30 | Usando 20.prev y 20.next: se asigna 10.next = 30 y 30.prev = 10 en O(1) |
Cuándo usar una lista doblemente enlazada
| Úsala cuando | Evítala cuando |
|---|---|
| Necesitas recorrer o empalmar en ambas direcciones | Solo avanzas hacia adelante: una lista simple es más ligera |
Eliminas nodos arbitrarios de los que ya tienes referencia (O(1)) | Sueles indexar por posición: usa un array para acceso O(1) |
| Implementas un deque, una caché LRU o un historial de deshacer | La memoria es escasa: el puntero prev adicional duplica la sobrecarga de enlaces |
| Las inserciones y eliminaciones ocurren a menudo en ambos extremos | Los datos son pequeños y cambian poco: copiar arrays es más barato |
Código de Doubly Linked List
Una implementación limpia y ejecutable de Doubly Linked List en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Doubly Linked List en 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())Código de Doubly Linked List en 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(" <-> "));Código de Doubly Linked List en 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}Código de Doubly Linked List en 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}Código de Doubly Linked List en 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}Preguntas frecuentes sobre listas doblemente enlazadas
¿Cuál es la diferencia entre una lista simplemente enlazada y una doblemente enlazada?
Una lista simplemente enlazada tiene un puntero por nodo (
next), así que solo puedes avanzar. Una lista doblemente enlazada añade un puntero prev, lo que permite recorrer hacia atrás y eliminar un nodo del que tienes una referencia en O(1), a cambio de un puntero adicional por nodo y de actualizar dos enlaces en cada cambio.¿Cuándo compensa una lista doblemente enlazada la memoria adicional?
Cuando necesitas recorrido hacia atrás o eliminación en
O(1) de nodos arbitrarios que ya referencias: los casos clásicos son las colas dobles (deques) y las cachés LRU, donde las entradas se mueven y expulsan por ambos extremos con frecuencia.¿Por qué una lista doblemente enlazada puede eliminar un nodo en O(1)?
Para eliminar un nodo hay que conectar su predecesor con su sucesor. En una lista simplemente enlazada tendrías que recorrer desde la cabeza para encontrar el predecesor (
O(n)); en una lista doblemente enlazada el puntero prev del nodo te da el predecesor directamente, así que la reconexión es O(1).Lista doblemente enlazada vs array: ¿cuál debería usar?
Usa un array cuando necesitas acceso
O(1) por índice e iteración eficiente en caché, y cuando las inserciones ocurren sobre todo al final. Usa una lista doblemente enlazada cuando insertas o eliminas con frecuencia en el medio o en ambos extremos con una referencia a nodo, ya que eso es O(1) frente al desplazamiento O(n) de un array. Los arrays ganan en memoria y localidad; la lista gana en ediciones estructurales.¿Qué es un nodo centinela en una lista doblemente enlazada?
Un nodo centinela (o ficticio) es un marcador que se sitúa antes de la cabeza o después de la cola para que la lista nunca esté realmente vacía. Elimina las comprobaciones de
null para head, tail y las inserciones/eliminaciones en los límites, permitiendo que toda operación siga el mismo camino de reconexión. Muchas implementaciones de cachés LRU en producción usan dos centinelas para no tratar los extremos como casos especiales.¿Cuál es el error más común al eliminar de una lista doblemente enlazada?
Olvidar actualizar
head o tail al eliminar el primer o último nodo, lo que deja un puntero colgante a un nodo liberado. Comprueba siempre si node.prev es null (actualiza head) o si node.next es null (actualiza tail) antes de reconectar los vecinos.Recursos relacionados
Más visualizaciones
