Listas encadeadas

Acrescentar um valor na frente de uma lista encadeada muda dois ponteiros, tenha a lista 4 valores ou 4 milhões.

Valores que apontam para o próximo

Um array guarda os valores lado a lado, e é por isso que a frente é cara de mudar. Uma lista encadeada abandona essa regra. Cada valor vive num pequeno registro próprio chamado nó, e os nós podem ficar em qualquer lugar da memória. As notas do 6.006 do MIT descrevem um nó com dois campos: o item e next, um ponteiro para o nó seguinte. A lista em si só lembra o primeiro nó, chamado head (cabeça). O next do último nó é null, o que marca o fim.

Para ler a lista, você começa em head e segue os ponteiros next um por um, como seguir uma série de bilhetes em que cada um diz onde o próximo está escondido. Isso tem um custo. Não existe fórmula para o endereço do quarto nó, então pegar o valor na posição i exige visitar i + 1 nós. O MIT lista get at(i) de uma lista encadeada como O(n), enquanto o array fazia isso em um passo.

// um nó por valor: { value, next }
let head = null;
for (const v of [4, 30, 7, 12]) head = { value: v, next: head };
// percorrer a lista
for (let n = head; n !== null; n = n.next) console.log(n.value); // 12, 7, 30, 4

Mudando a lista religando os nós

A vantagem aparece quando você muda a lista. Para pôr um valor novo na frente, crie um nó cujo next é o head atual e depois aponte head para o nó novo. Duas mudanças de ponteiro, e nada mais se move. Apagar o nó da frente é uma mudança: aponte head para head.next. Compare com o array, em que as mesmas operações moviam todos os valores.

No meio, o trabalho é achar o lugar. Para inserir na posição i, você anda até o nó logo antes dela (i visitas) e depois faz as mesmas duas mudanças de ponteiro: new.next = prev.next, depois prev.next = new. A ordem importa. Se você mudar prev.next primeiro, o resto da lista se perde, porque nada mais aponta para ele. No laboratório, um passo é um nó visitado ou um ponteiro alterado, então inserir na posição 2 de uma lista de 4 nós custa 2 visitas mais 2 mudanças, 4 passos.

Quando usar

Uma lista encadeada é uma boa escolha quando a maior parte das mudanças acontece num lugar para o qual você já tem um ponteiro, como a frente, e você raramente precisa da posição i. Filas e pilhas podem ser construídas com listas encadeadas, assim como as cadeias dentro de uma tabela hash, na próxima unidade. Há variantes. Uma lista duplamente encadeada dá a cada nó também um ponteiro prev, para que você possa andar para trás e apagar um nó em um passo depois de tê-lo nas mãos. Guardar um ponteiro tail além de head deixa barato acrescentar no fim.

No JavaScript do dia a dia, você raramente escreve uma lista encadeada, porque os arrays são bem otimizados e os caches dos processadores modernos favorecem valores guardados lado a lado. A ideia importa mesmo assim: árvores, grafos e muitas estruturas de bibliotecas são construídos com nós e ponteiros exatamente desse jeito.