Doubly Linked List
Una Doubly Linked List (Lista Doblemente Enlazada) es una estructura de datos lineal donde cada nodo tiene una referencia tanto al siguiente como al nodo anterior.
¿Qué es una Doubly Linked List?
A diferencia de una Singly Linked List, una Doubly Linked List tiene nodos con dos punteros: uno al siguiente nodo y otro al nodo anterior. Esto permite recorrer la lista en ambas direcciones y facilita ciertas operaciones como eliminar nodos sin necesidad de recorrer desde el principio.
Analogía del Mundo Real
Imagina una lista de reproducción donde puedes avanzar y retroceder entre canciones. Cada canción sabe cuál es la anterior y la siguiente. Eso es una Doubly Linked List: puedes navegar en ambas direcciones fácilmente.
Cómo Funciona Internamente una Doubly Linked List
- Cada nodo contiene tres partes: el valor, una referencia al siguiente nodo y una referencia al anterior.
- Para insertar, se actualizan ambas referencias del nuevo nodo y los nodos vecinos.
- Para eliminar, puedes usar la referencia anterior para saltarte el nodo actual sin recorrer desde el inicio.
- Requiere más espacio que una Singly Linked List, pero mejora operaciones que necesitan acceso bidireccional.
Ejemplos de Código
// Creating a Doubly Linked List in JavaScript
class Node {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
append(value) {
const newNode = new Node(value);
if (!this.tail) {
this.head = this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
}
prepend(value) {
const newNode = new Node(value);
if (!this.head) {
this.head = this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
}
delete(value) {
let current = this.head;
while (current) {
if (current.value === value) {
if (current.prev) current.prev.next = current.next;
if (current.next) current.next.prev = current.prev;
if (current === this.head) this.head = current.next;
if (current === this.tail) this.tail = current.prev;
break;
}
current = current.next;
}
}
printForward() {
let current = this.head;
while (current) {
console.log(current.value);
current = current.next;
}
}
printBackward() {
let current = this.tail;
while (current) {
console.log(current.value);
current = current.prev;
}
}
}Explicación Visual (🚧 En progreso)
Estamos trabajando en un video para explicar esta estructura de datos
Complejidad en Tiempo y Espacio
| Operación | Promedio | Peor Escenario |
|---|---|---|
| Acceso | O(n) | O(n) |
| Búsqueda | O(n) | O(n) |
| Inserción | O(1) | O(1) |
| Eliminación | O(1) | O(1) |
Donde n es el número de nodos en la lista.
Es necesario mantener referencias dobles correctamente para evitar errores en la manipulación.
Operaciones Comunes
- .append(value)Agrega un nodo al final de la lista
- .prepend(value)Agrega un nodo al inicio de la lista
- .delete(value)Elimina un nodo con un valor específico
- .printForward()Imprime los valores desde el inicio al final
- .printBackward()Imprime los valores desde el final al inicio