Data Structure & Algorithms
Listas enlazadas simples, dobles y circulares: nodos, sentinels, operaciones, inversión, merge y detección de ciclos con Floyd.
Una linked list almacena elementos en nodos conectados mediante referencias. Los nodos no necesitan estar contiguos en memoria y cada uno indica cómo llegar al siguiente.
head
↓
[10 | next] → [20 | next] → [30 | null]Su fortaleza es modificar conexiones sin desplazar todos los elementos. Su costo es perder acceso directo por índice y añadir memoria por nodo.
class ListNode<T> {
next: ListNode<T> | null = null;
constructor(public value: T) {}
}head apunta al primer nodo. Si head === null, la lista está vacía. El último nodo tiene next === null.
Los valores pueden repetirse; la identidad de cada nodo sigue siendo distinta.
Cada nodo conoce únicamente al siguiente.
A → B → C → nullPermite avanzar, pero no regresar directamente.
class SinglyLinkedList<T> {
private head: ListNode<T> | null = null;
private tail: ListNode<T> | null = null;
private length = 0;
get size(): number {
return this.length;
}
isEmpty(): boolean {
return this.length === 0;
}
first(): T | undefined {
return this.head?.value;
}
last(): T | undefined {
return this.tail?.value;
}
prepend(value: T): void {
const node = new ListNode(value);
node.next = this.head;
this.head = node;
if (!this.tail) {
this.tail = node;
}
this.length += 1;
}
append(value: T): void {
const node = new ListNode(value);
if (!this.tail) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.length += 1;
}
removeFirst(): T | undefined {
if (!this.head) return undefined;
const value = this.head.value;
this.head = this.head.next;
this.length -= 1;
if (!this.head) {
this.tail = null;
}
return value;
}
toArray(): T[] {
const result: T[] = [];
let current = this.head;
while (current) {
result.push(current.value);
current = current.next;
}
return result;
}
}La clase debe conservar:
length === 0 si y solo si head y tail son null;tail.next === null;length coincide con la cantidad de nodos alcanzables desde head;El caso de eliminar el único nodo debe actualizar head y tail.
| Operación | Singly list con head/tail | Razón |
|---|---|---|
| Leer primero | O(1) | Referencia directa |
| Prepend | O(1) | Cambia head y una referencia |
| Append | O(1) | Existe tail |
| Remove first | O(1) | Cambia head |
| Acceso por índice | O(n) | Debe avanzar nodo por nodo |
| Buscar valor | O(n) | No hay orden o índice auxiliar |
| Eliminar último | O(n) | Debe localizar el penúltimo |
append solo es O(1) porque la clase conserva tail. Sin esa referencia tendría que recorrer la lista y sería O(n).
Esta afirmación es incompleta:
“Insertar o eliminar en medio cuesta
O(1).”
Modificar referencias sí cuesta O(1) si ya tienes el nodo anterior o la referencia exacta necesaria.
Si recibes un índice o valor y primero debes encontrar la posición:
localizar O(n) + reconectar O(1) = O(n)La estructura no hace desaparecer el costo de búsqueda.
function insertAfter<T>(node: ListNode<T>, value: T): ListNode<T> {
const inserted = new ListNode(value);
inserted.next = node.next;
node.next = inserted;
return inserted;
}Tiempo: O(1). Si el nodo era tail, una clase completa debe actualizar tail y size.
function removeAfter<T>(node: ListNode<T>): T | undefined {
if (!node.next) return undefined;
const removed = node.next;
node.next = removed.next;
removed.next = null;
return removed.value;
}También es O(1), pero requiere el nodo anterior. En una singly linked list no puedes obtenerlo desde el nodo actual sin recorrer desde head.
Un sentinel o dummy node no representa un elemento real. Se coloca antes de head para unificar casos.
dummy → head → ...Sin sentinel, eliminar el primer nodo exige una rama especial. Con sentinel, todos los nodos reales tienen un anterior durante la operación.
function removeFirstMatch<T>(
head: ListNode<T> | null,
target: T,
equals: (a: T, b: T) => boolean = Object.is,
): ListNode<T> | null {
const dummy = new ListNode<T>(undefined as T);
dummy.next = head;
let current = dummy;
while (current.next) {
if (equals(current.next.value, target)) {
current.next = current.next.next;
break;
}
current = current.next;
}
return dummy.next;
}El cast existe porque el sentinel no tiene un valor real. En producción puede modelarse con un tipo de nodo separado para evitarlo.
Cada nodo conoce al anterior y al siguiente.
null ← A ⇄ B ⇄ C → nullclass DoublyNode<T> {
previous: DoublyNode<T> | null = null;
next: DoublyNode<T> | null = null;
constructor(public value: T) {}
}Ventajas:
O(1) sin buscar el anterior;O(1) con tail;Costos:
function detach<T>(
node: DoublyNode<T>,
): { previous: DoublyNode<T> | null; next: DoublyNode<T> | null } {
const { previous, next } = node;
if (previous) previous.next = next;
if (next) next.previous = previous;
node.previous = null;
node.next = null;
return { previous, next };
}Una clase completa también actualiza head, tail y size cuando el nodo está en un extremo.
El último nodo apunta al primero.
A → B → C
↑ ↓
└───────┘Útil para:
Ya no existe null como terminación. El recorrido debe detenerse al regresar al nodo inicial o después de una cantidad conocida. Un while (current) sería infinito.
Dos punteros que avanzan a velocidades distintas resuelven varios problemas.
function middle<T>(head: ListNode<T> | null): ListNode<T> | null {
let slow = head;
let fast = head;
while (fast?.next) {
slow = slow!.next;
fast = fast.next.next;
}
return slow;
}Cuando fast avanza dos pasos y llega al final, slow recorrió aproximadamente la mitad.
Con longitud par, esta versión devuelve el segundo de los dos nodos centrales. La política debe declararse.
function hasCycle<T>(head: ListNode<T> | null): boolean {
let slow = head;
let fast = head;
while (fast?.next) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}Si hay ciclo, la distancia relativa dentro de él cambia hasta que ambos punteros coinciden.
O(n);O(1).Un Set de nodos también detecta ciclo en O(n) tiempo, pero usa O(n) memoria.
A → B → C → null
null ← A ← B ← Cfunction reverse<T>(head: ListNode<T> | null): ListNode<T> | null {
let previous: ListNode<T> | null = null;
let current = head;
while (current) {
const next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
}Invariante:
previous es la parte ya invertida;current es el primer nodo pendiente;next conserva el resto antes de cambiar la referencia.Olvidar guardar next pierde acceso al resto de la lista.
Tiempo: O(n). Espacio adicional: O(1).
function mergeSorted(
left: ListNode<number> | null,
right: ListNode<number> | null,
): ListNode<number> | null {
const dummy = new ListNode(0);
let tail = dummy;
let a = left;
let b = right;
while (a && b) {
if (a.value <= b.value) {
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
tail.next = a ?? b;
return dummy.next;
}Reutiliza nodos existentes:
O(n + m);O(1);Si las listas deben preservarse, crea nodos nuevos y cuenta O(n + m) de memoria.
| Propiedad | Array dinámico | Linked list |
|---|---|---|
| Acceso por índice | O(1) | O(n) |
| Append | O(1) amortizado | O(1) con tail |
| Insertar al inicio | O(n) | O(1) |
| Insertar después de posición conocida | O(n) por desplazamiento | O(1) |
| Memoria por elemento | Baja | Referencias adicionales |
| Localidad de caché | Buena | Generalmente peor |
En la práctica, arrays dinámicos son una gran opción por localidad de memoria y simplicidad. Linked lists aportan valor cuando necesitas nodos estables y modificaciones frecuentes en posiciones ya localizadas.
Un feed o playlist no se beneficia automáticamente de una linked list. Si la aplicación accede por índice, filtra y renderiza secuencialmente, un array puede ser mejor.
previous y next desincronizadas;O(1) sin contar localización.tail al insertar o eliminar.next antes de guardarlo.null.size desincronizado.O(1); encontrarla puede costar O(n).tail cambia append de O(n) a O(1).Recibes un índice y debes eliminar ese elemento de una singly linked list. ¿La operación es O(1)?
No en general. Debes recorrer hasta el nodo anterior, lo que cuesta O(n) en el peor caso. Reconectar referencias después sí cuesta O(1).