← Data structures from scratch · Lesson 11/32
Removing, reversing and merging
Removing is skipping a node
To remove a node from the middle, nothing moves: the previous node stops pointing at it and points to the one after. anterior.siguiente = anterior.siguiente.siguiente. The skipped node has nobody pointing at it, and JavaScript cleans it up on its own.
The odd case is the head, which has no previous node. A common trick is to put a fake node before the head (a *sentinel*, or *dummy*): then every node has a previous one and the code needs no special case.
$ node leccion.js
Press RUN (or Ctrl+Enter).
What to look at
All three work with the same code: removing from the middle, removing the head, and emptying the list. Without the sentinel, the last two cases would need a separate if.
The whole lesson on one page
Removing is skipping a node
To remove a node from the middle, nothing moves: the previous node stops pointing at it and points to the one after. anterior.siguiente = anterior.siguiente.siguiente. The skipped node has nobody pointing at it, and JavaScript cleans it up on its own.
The odd case is the head, which has no previous node. A common trick is to put a fake node before the head (a *sentinel*, or *dummy*): then every node has a previous one and the code needs no special case.
class Nodo {
constructor(valor, siguiente = null) { this.valor = valor; this.siguiente = siguiente; }
}
const desde = arr => arr.reduceRight((sig, v) => new Nodo(v, sig), null);
const ver = c => { const r = []; for (; c; c = c.siguiente) r.push(c.valor); return r.join(" -> ") || "(empty)"; };
function borrar(cabeza, x) {
const falso = new Nodo(null, cabeza); // sentinel before the head
let anterior = falso;
while (anterior.siguiente !== null) {
if (anterior.siguiente.valor === x) {
anterior.siguiente = anterior.siguiente.siguiente; // skip it
break;
}
anterior = anterior.siguiente;
}
return falso.siguiente; // the head (maybe a new one)
}
console.log(ver(borrar(desde([3, 8, 5]), 8)));
console.log(ver(borrar(desde([3, 8, 5]), 3)));
console.log(ver(borrar(desde([3]), 3)));
All three work with the same code: removing from the middle, removing the head, and emptying the list. Without the sentinel, the last two cases would need a separate if.
Reversing: flip every arrow
Reversing a list copies nothing: it flips every arrow. You walk with three pointers:
anterior(previous): what's already flipped (starts atnull).actual(current): the node whose turn it is.siguiente(next): saved before flipping, because changingactual.siguienteloses the way forward.
At each step, actual starts pointing to anterior, and all three move on. At the end, anterior is the new head. O(n), no extra memory. It's one of the most famous interview problems.
class Nodo {
constructor(valor, siguiente = null) { this.valor = valor; this.siguiente = siguiente; }
}
const desde = arr => arr.reduceRight((sig, v) => new Nodo(v, sig), null);
const ver = c => { const r = []; for (; c; c = c.siguiente) r.push(c.valor); return r.join(" -> "); };
function invertir(cabeza) {
let anterior = null, actual = cabeza;
while (actual !== null) {
const siguiente = actual.siguiente; // save the way forward
actual.siguiente = anterior; // flip the arrow
anterior = actual; // move all three
actual = siguiente;
console.log(" flipped:", ver(anterior), "| left:", ver(actual) || "nothing");
}
return anterior;
}
console.log(ver(invertir(desde([1, 2, 3, 4]))));
Each turn the flipped part grows at the front (1, then 2 -> 1, then 3 -> 2 -> 1…) and what's left shrinks. You end with 4 -> 3 -> 2 -> 1.
Merging two sorted lists
If you have two already-sorted lists, joining them into one sorted list is like two lines becoming one: compare the two fronts, take the smaller, and advance in that list. When one runs out, hang the rest of the other at the end.
With a sentinel node at the start, the code stays short. It's O(n + m) and creates no new nodes: it only rearranges arrows. This merge is half of merge sort, which you'll see in recursion.
class Nodo {
constructor(valor, siguiente = null) { this.valor = valor; this.siguiente = siguiente; }
}
const desde = arr => arr.reduceRight((sig, v) => new Nodo(v, sig), null);
const ver = c => { const r = []; for (; c; c = c.siguiente) r.push(c.valor); return r.join(" -> "); };
function mezclar(a, b) {
const falso = new Nodo(null);
let fin = falso;
while (a !== null && b !== null) {
if (a.valor <= b.valor) { fin.siguiente = a; a = a.siguiente; }
else { fin.siguiente = b; b = b.siguiente; }
fin = fin.siguiente;
}
fin.siguiente = a !== null ? a : b; // whatever's left, whole
return falso.siguiente;
}
console.log(ver(mezclar(desde([1, 4, 9]), desde([2, 3, 10, 12]))));
It takes 1, 2, 3, 4, 9; then the first list runs out and "10 -> 12" is hung as is, without comparing.