Skip to content
Ayotl
Español

← Data structures from scratch · Lesson 12/32

Doubly linked lists and cycles

✕
1/7

Arrows going both ways

In a doubly linked list each node keeps siguiente and also anterior (previous). It costs a bit more memory and every change has to maintain two arrows, but in exchange:

  • you can walk it backwards;
  • if you already have a node in hand, removing it is O(1): its previous and next point to each other, no searching needed.

That last property is what makes the LRU cache in the final unit work. A browser history (back and forward) looks a lot like this too.

ABCnull
leccion.js

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

  • Forward A, B, C; backward C, B, A.
  • Removing B walked nothing: two assignments and now A and C point straight at each other.
The whole lesson on one page

Arrows going both ways

In a doubly linked list each node keeps siguiente and also anterior (previous). It costs a bit more memory and every change has to maintain two arrows, but in exchange:

  • you can walk it backwards;
  • if you already have a node in hand, removing it is O(1): its previous and next point to each other, no searching needed.

That last property is what makes the LRU cache in the final unit work. A browser history (back and forward) looks a lot like this too.

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;

// forward from a, backward from 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);

// remove b in O(1): its neighbors point to each other
b.anterior.siguiente = b.siguiente;
b.siguiente.anterior = b.anterior;
console.log(a.siguiente.valor, c.anterior.valor);
  • Forward A, B, C; backward C, B, A.
  • Removing B walked nothing: two assignments and now A and C point straight at each other.

Sentinels at both ends

In a doubly linked list, the special cases multiply: what if it's the first? the last? the only one? The usual fix: two fixed fake nodes, one at the start and one at the end. Real nodes always live between them, so every node has a previous and a next, and adding or removing is the same code at any position.

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

class ListaDoble {
  constructor() {
    this.inicio = new NodoDoble(null);   // sentinels: never removed
    this.fin = new NodoDoble(null);
    this.inicio.siguiente = this.fin;
    this.fin.anterior = this.inicio;
  }
  meterAntesDe(nodo, valor) {          // the same code for any position
    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 and alPrincipio are the same operation with a different neighbor, and sacar doesn't have a single if. The sentinels don't show up in aArreglo because the walk starts after inicio and stops at fin.

The tortoise and the hare

What if, by mistake, the last node points to one in the middle? The list becomes a cycle and any walk goes around forever. How do you notice without storing every node you've seen?

With two pointers at different speeds (Floyd's algorithm): the tortoise moves one node per turn and the hare, two. If there's no cycle, the hare reaches null. If there is one, the hare goes in, laps around, and sooner or later catches the tortoise from behind, like on a running track. O(n), no extra memory.

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;           // one step
    liebre = liebre.siguiente.siguiente;   // two steps
    vueltas++;
    if (tortuga === liebre) { console.log("  they met at", tortuga.valor, "after", vueltas, "turns"); return true; }
  }
  return false;
}

// 1 -> 2 -> 3 -> 4 -> 5 -> (back to 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]));
  • With no cycle, the hare reaches null and answers false.
  • With 5 pointing back to 3, they meet inside the cycle after a few turns: true. It compares nodes with ===, not values: two different nodes can hold the same value.

Practice with a video challenge