Listas encadeadas e árvores

Listas encadeadas e árvores

Até agora as estruturas se apoiavam em arrays. Estas duas se baseiam em nós que se ligam entre si por meio de referências.

Lista encadeada

Cada nó guarda um valor e uma referência ao próximo nó. A lista só precisa lembrar a cabeça (head).

class No {
  constructor(valor) {
    this.valor = valor;
    this.proximo = null;
  }
}

class ListaEncadeada {
  constructor() {
    this.head = null;
    this.comprimento = 0;
  }
  adicionar(valor) {
    const novo = new No(valor);
    if (!this.head) {
      this.head = novo;
    } else {
      let atual = this.head;
      while (atual.proximo) atual = atual.proximo;
      atual.proximo = novo;
    }
    this.comprimento++;
  }
  paraArray() {
    const saida = [];
    let atual = this.head;
    while (atual) {
      saida.push(atual.valor);
      atual = atual.proximo;
    }
    return saida;
  }
}

Vantagem: inserir no início é O(1). Desvantagem: acessar por índice é O(n) (é preciso percorrer desde a cabeça).

Árvore (introdução)

Uma árvore é uma estrutura hierárquica: cada nó tem um valor e uma lista de filhos. O nó do topo é a raiz.

class NoArvore {
  constructor(valor) {
    this.valor = valor;
    this.filhos = [];
  }
  adicionarFilho(valor) {
    const filho = new NoArvore(valor);
    this.filhos.push(filho);
    return filho;
  }
}

As árvores modelam hierarquias: o DOM, sistemas de arquivos, organogramas...

Exemplos

Percorrer uma árvore em profundidade

function percorrer(no, nivel = 0) {
  console.log("  ".repeat(nivel) + no.valor);
  for (const filho of no.filhos || []) {
    percorrer(filho, nivel + 1);
  }
}
const raiz = { valor: "raiz", filhos: [
  { valor: "a", filhos: [] },
  { valor: "b", filhos: [{ valor: "b1", filhos: [] }] },
]};
percorrer(raiz);