Ir al contenido
Ayotl
English

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

Nodos y punteros

✕
1/7

Cajitas que se apuntan

Un arreglo pone todo junto. Una lista enlazada no: cada elemento vive en su propio nodo, en cualquier parte de la memoria, y cada nodo guarda dos cosas: su valor y una referencia al siguiente nodo. El último apunta a null.

Aquí es donde sirve la lección de valores y referencias: siguiente no guarda una copia del otro nodo, guarda dónde está. La lista entera se reconoce por su primer nodo, la cabeza.

385null
leccion.js

$ node leccion.js

Pulsa CORRER (o Ctrl+Enter).

Qué mirar

Desde la cabeza se llega a todo siguiendo siguiente: 3, 8, 5 y luego null, el fin de la lista. No hay índices: para llegar al tercero hay que pasar por los dos primeros.

Listas enlazadas animadas en VisuAlgo ↗

Toda la lección en una página

Cajitas que se apuntan

Un arreglo pone todo junto. Una lista enlazada no: cada elemento vive en su propio nodo, en cualquier parte de la memoria, y cada nodo guarda dos cosas: su valor y una referencia al siguiente nodo. El último apunta a null.

Aquí es donde sirve la lección de valores y referencias: siguiente no guarda una copia del otro nodo, guarda dónde está. La lista entera se reconoce por su primer nodo, la cabeza.

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

// 3 -> 8 -> 5 -> null, armada a mano
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);

Desde la cabeza se llega a todo siguiendo siguiente: 3, 8, 5 y luego null, el fin de la lista. No hay índices: para llegar al tercero hay que pasar por los dos primeros.

Recorrer: seguir las flechas

Para recorrer una lista se usa un puntero actual que empieza en la cabeza y salta a actual.siguiente hasta caer en null. Es O(n), como en un arreglo.

Lo que se pierde es el acceso directo: en un arreglo arr[1000] es O(1); en una lista, llegar al nodo 1000 son 1000 saltos, O(n). A cambio, vas a ver que meter y sacar nodos no obliga a mover a nadie.

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;   // salta al siguiente
  }
  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 sigue las flechas hasta null.
  • enPosicion(cabeza, 2) da 5 después de dos saltos; pedir la posición 7 se queda sin lista y da undefined.

Meter al principio y al final

Meter al principio es lo que mejor hace una lista: el nodo nuevo apunta a la cabeza vieja y pasa a ser la cabeza. Nadie se mueve: O(1). (En un arreglo, unshift era O(n).)

Meter al final obliga a caminar hasta el último: O(n). A menos que guardes también una referencia al último nodo, la cola (*tail*): entonces es O(1) también. Por eso una clase Lista suele guardar cabeza, cola y su 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);   // apunta a la cabeza vieja
    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; }   // sin caminar
    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(), "tamaño:", l.tamano);

Los dos alPrincipio quedaron adelante en orden inverso (primero el 1, que entró al último) y los alFinal atrás. Ninguna operación recorrió la lista.