Listas enlazadas y árboles

Listas enlazadas y árboles

Hasta ahora las estructuras se apoyaban en arrays. Estas dos se basan en nodos que se enlazan entre sí mediante referencias.

Lista enlazada

Cada nodo guarda un valor y una referencia al siguiente nodo. La lista solo necesita recordar la cabeza (head).

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

class ListaEnlazada {
  constructor() {
    this.head = null;
    this.longitud = 0;
  }
  agregar(valor) {
    const nuevo = new Nodo(valor);
    if (!this.head) {
      this.head = nuevo;
    } else {
      let actual = this.head;
      while (actual.siguiente) actual = actual.siguiente;
      actual.siguiente = nuevo;
    }
    this.longitud++;
  }
  aArray() {
    const salida = [];
    let actual = this.head;
    while (actual) {
      salida.push(actual.valor);
      actual = actual.siguiente;
    }
    return salida;
  }
}

Ventaja: insertar al inicio es O(1). Inconveniente: acceder por índice es O(n) (hay que recorrer desde la cabeza).

Árbol (introducción)

Un árbol es una estructura jerárquica: cada nodo tiene un valor y una lista de hijos. El nodo superior es la raíz.

class NodoArbol {
  constructor(valor) {
    this.valor = valor;
    this.hijos = [];
  }
  agregarHijo(valor) {
    const hijo = new NodoArbol(valor);
    this.hijos.push(hijo);
    return hijo;
  }
}

Los árboles modelan jerarquías: el DOM, sistemas de archivos, organigramas...

Ejemplos

Recorrer un árbol en profundidad

function recorrer(nodo, nivel = 0) {
  console.log("  ".repeat(nivel) + nodo.valor);
  for (const hijo of nodo.hijos || []) {
    recorrer(hijo, nivel + 1);
  }
}
const raiz = { valor: "raiz", hijos: [
  { valor: "a", hijos: [] },
  { valor: "b", hijos: [{ valor: "b1", hijos: [] }] },
]};
recorrer(raiz);