Skip to content
Ayotl
Español

← Data structures from scratch · Lesson 10/32

Nodes and pointers

✕
1/7

Boxes pointing to each other

An array keeps everything together. A linked list doesn't: each item lives in its own node, anywhere in memory, and each node stores two things: its valor (value) and a reference to the siguiente (next) node. The last one points to null.

This is where the values-and-references lesson pays off: siguiente doesn't hold a copy of the other node, it holds where it is. The whole list is known by its first node, the head.

385null
leccion.js

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

From the head you reach everything by following siguiente: 3, 8, 5 and then null, the end of the list. There are no indexes: to get to the third you have to go through the first two.

Animated linked lists on VisuAlgo ↗

The whole lesson on one page

Boxes pointing to each other

An array keeps everything together. A linked list doesn't: each item lives in its own node, anywhere in memory, and each node stores two things: its valor (value) and a reference to the siguiente (next) node. The last one points to null.

This is where the values-and-references lesson pays off: siguiente doesn't hold a copy of the other node, it holds where it is. The whole list is known by its first node, the head.

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

// 3 -> 8 -> 5 -> null, built by hand
const c = new Nodo(5);
const b = new Nodo(8, c);
const cabeza = new Nodo(3, b);

console.log(cabeza.valor);
console.log(cabeza.siguiente.valor);
console.log(cabeza.siguiente.siguiente.valor);
console.log(cabeza.siguiente.siguiente.siguiente);

From the head you reach everything by following siguiente: 3, 8, 5 and then null, the end of the list. There are no indexes: to get to the third you have to go through the first two.

Walking: follow the arrows

To walk a list you use a pointer actual (current) that starts at the head and jumps to actual.siguiente until it hits null. It's O(n), like an array.

What you lose is direct access: in an array arr[1000] is O(1); in a list, reaching node 1000 takes 1000 hops, O(n). In exchange, you'll see that adding and removing nodes doesn't force anyone to move.

class Nodo {
  constructor(valor, siguiente = null) { this.valor = valor; this.siguiente = siguiente; }
}
const cabeza = new Nodo(3, new Nodo(8, new Nodo(5)));

function imprimir(cabeza) {
  const partes = [];
  let actual = cabeza;
  while (actual !== null) {
    partes.push(actual.valor);
    actual = actual.siguiente;   // jump to the next
  }
  console.log(partes.join(" -> ") + " -> null");
}

function enPosicion(cabeza, i) {
  let actual = cabeza;
  for (let k = 0; k < i && actual; k++) actual = actual.siguiente;
  return actual ? actual.valor : undefined;
}

imprimir(cabeza);
console.log(enPosicion(cabeza, 2));
console.log(enPosicion(cabeza, 7));
  • imprimir follows the arrows to null.
  • enPosicion(cabeza, 2) gives 5 after two hops; asking for position 7 runs out of list and gives undefined.

Adding at the front and at the end

Adding at the front is what a list does best: the new node points to the old head and becomes the head. Nobody moves: O(1). (In an array, unshift was O(n).)

Adding at the end means walking to the last node: O(n). Unless you also keep a reference to the last node, the tail: then it's O(1) too. That's why a Lista class usually keeps cabeza, cola (tail) and its tamano.

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

class Lista {
  constructor() { this.cabeza = null; this.cola = null; this.tamano = 0; }
  alPrincipio(valor) {
    this.cabeza = new Nodo(valor, this.cabeza);   // points to the old head
    if (this.cola === null) this.cola = this.cabeza;
    this.tamano++;
  }
  alFinal(valor) {
    const nodo = new Nodo(valor);
    if (this.cola === null) this.cabeza = this.cola = nodo;
    else { this.cola.siguiente = nodo; this.cola = nodo; }   // no walking
    this.tamano++;
  }
  aArreglo() {
    const r = [];
    for (let n = this.cabeza; n; n = n.siguiente) r.push(n.valor);
    return r;
  }
}

const l = new Lista();
l.alFinal(8);
l.alFinal(5);
l.alPrincipio(3);
l.alPrincipio(1);
console.log(l.aArreglo(), "size:", l.tamano);

The two alPrincipio calls ended up in front in reverse order (1 first, since it went in last) and the alFinal ones at the back. No operation walked the list.