Ir al contenido
Ayotl
English

← Estructuras de datos desde cero · Lección 12/32

Listas dobles y ciclos

✕
1/7

Flechas de ida y de vuelta

En una lista doble cada nodo guarda siguiente y también anterior. Cuesta un poco más de memoria y hay que mantener dos flechas en cada cambio, pero a cambio:

  • se puede recorrer hacia atrás;
  • si ya tienes un nodo en la mano, sacarlo es O(1): su anterior y su siguiente se apuntan entre sí, sin buscar a nadie.

Esa última propiedad es la que hace funcionar la caché LRU de la última unidad. El historial de un navegador (atrás y adelante) también se parece mucho a esto.

ABCnull
leccion.js

$ node leccion.js

Pulsa CORRER (o Ctrl+Enter).

Qué mirar

  • De ida A, B, C; de vuelta C, B, A.
  • Para sacar a B no se recorrió nada: dos asignaciones y ahora A y C se apuntan directo.
Toda la lección en una página

Flechas de ida y de vuelta

En una lista doble cada nodo guarda siguiente y también anterior. Cuesta un poco más de memoria y hay que mantener dos flechas en cada cambio, pero a cambio:

  • se puede recorrer hacia atrás;
  • si ya tienes un nodo en la mano, sacarlo es O(1): su anterior y su siguiente se apuntan entre sí, sin buscar a nadie.

Esa última propiedad es la que hace funcionar la caché LRU de la última unidad. El historial de un navegador (atrás y adelante) también se parece mucho a esto.

ABCnull
class NodoDoble {
  constructor(valor) { this.valor = valor; this.anterior = null; this.siguiente = null; }
}

const a = new NodoDoble("A"), b = new NodoDoble("B"), c = new NodoDoble("C");
a.siguiente = b; b.anterior = a;
b.siguiente = c; c.anterior = b;

// hacia adelante desde a, hacia atrás desde c
let ida = [], vuelta = [];
for (let n = a; n; n = n.siguiente) ida.push(n.valor);
for (let n = c; n; n = n.anterior) vuelta.push(n.valor);
console.log(ida, vuelta);

// sacar b en O(1): sus vecinos se apuntan entre sí
b.anterior.siguiente = b.siguiente;
b.siguiente.anterior = b.anterior;
console.log(a.siguiente.valor, c.anterior.valor);
  • De ida A, B, C; de vuelta C, B, A.
  • Para sacar a B no se recorrió nada: dos asignaciones y ahora A y C se apuntan directo.

Centinelas en las dos puntas

En una lista doble, los casos especiales se multiplican: ¿y si es el primero?, ¿el último?, ¿el único? La solución de siempre: dos nodos falsos fijos, uno al inicio y otro al fin. Los nodos de verdad siempre viven entre los dos, así que todos tienen anterior y siguiente, y meter o sacar es el mismo código en cualquier posición.

class NodoDoble {
  constructor(valor) { this.valor = valor; this.anterior = null; this.siguiente = null; }
}

class ListaDoble {
  constructor() {
    this.inicio = new NodoDoble(null);   // centinelas: nunca se sacan
    this.fin = new NodoDoble(null);
    this.inicio.siguiente = this.fin;
    this.fin.anterior = this.inicio;
  }
  meterAntesDe(nodo, valor) {          // el mismo código para cualquier lugar
    const n = new NodoDoble(valor);
    n.anterior = nodo.anterior; n.siguiente = nodo;
    nodo.anterior.siguiente = n; nodo.anterior = n;
    return n;
  }
  alFinal(valor) { return this.meterAntesDe(this.fin, valor); }
  alPrincipio(valor) { return this.meterAntesDe(this.inicio.siguiente, valor); }
  sacar(n) { n.anterior.siguiente = n.siguiente; n.siguiente.anterior = n.anterior; }
  aArreglo() {
    const r = [];
    for (let n = this.inicio.siguiente; n !== this.fin; n = n.siguiente) r.push(n.valor);
    return r;
  }
}

const l = new ListaDoble();
const dos = l.alFinal(2);
l.alFinal(3);
l.alPrincipio(1);
console.log(l.aArreglo());
l.sacar(dos);
console.log(l.aArreglo());

alFinal y alPrincipio son la misma operación con distinto vecino, y sacar no tiene ni un if. Los centinelas no salen en aArreglo porque el recorrido empieza después de inicio y para en fin.

La tortuga y la liebre

¿Y si, por un error, el último nodo apunta a uno de en medio? La lista se vuelve un ciclo y cualquier recorrido da vueltas para siempre. ¿Cómo darse cuenta sin guardar todos los nodos vistos?

Con dos punteros a distinta velocidad (el algoritmo de Floyd): la tortuga avanza un nodo por vuelta y la liebre, dos. Si no hay ciclo, la liebre llega a null. Si hay ciclo, la liebre entra, da vueltas y tarde o temprano alcanza a la tortuga por detrás, como en una pista de atletismo. O(n) y sin memoria extra.

class Nodo {
  constructor(valor, siguiente = null) { this.valor = valor; this.siguiente = siguiente; }
}

function tieneCiclo(cabeza) {
  let tortuga = cabeza, liebre = cabeza, vueltas = 0;
  while (liebre !== null && liebre.siguiente !== null) {
    tortuga = tortuga.siguiente;           // un paso
    liebre = liebre.siguiente.siguiente;   // dos pasos
    vueltas++;
    if (tortuga === liebre) { console.log("  se encontraron en", tortuga.valor, "tras", vueltas, "vueltas"); return true; }
  }
  return false;
}

// 1 -> 2 -> 3 -> 4 -> 5 -> (de vuelta al 3)
const nodos = [1, 2, 3, 4, 5].map(v => new Nodo(v));
for (let i = 0; i < 4; i++) nodos[i].siguiente = nodos[i + 1];
console.log(tieneCiclo(nodos[0]));

nodos[4].siguiente = nodos[2];
console.log(tieneCiclo(nodos[0]));
  • Sin ciclo, la liebre llega a null y responde false.
  • Con el 5 apuntando al 3, se encuentran dentro del ciclo tras unas pocas vueltas: true. Se comparan nodos con ===, no valores: dos nodos distintos pueden valer lo mismo.

Practica con un reto en vídeo