O nó e a ligação: a corrente de dados

O que é um nó

Até agora, quando você precisava guardar uma sequência de valores, usava o vetor: as casas ficam encostadas na memória e cada uma tem um número, o índice. A lista ligada resolve o mesmo problema por um caminho oposto. Em vez de encostar os valores, ela os espalha pela memória e amarra um no outro. A peça que faz essa amarração é o nó. Cada nó carrega duas informações: o valor propriamente dito e uma ligação, que é a referência apontando para onde está o próximo nó. Pense num trem: cada vagão transporta uma carga (o valor) e tem um engate que o prende ao vagão seguinte (a ligação). Nenhum vagão sabe onde estão os outros; ele só sabe qual é o próximo.

Essa corrente precisa de um começo, e esse começo é a cabeça da lista. A cabeça é apenas uma referência que aponta para o primeiro nó. É o fio da meada: segurando a cabeça, você alcança o primeiro nó; a ligação dele leva ao segundo; a ligação do segundo leva ao terceiro, e assim por diante, até um nó cuja ligação aponta para o nada, o sinal de que a lista acabou. Repare na consequência: você não tem como pular direto para o meio. Para chegar ao quinto valor, precisa passar pelos quatro anteriores, um a um. É o preço de espalhar os dados em vez de enfileirá-los.

Percorrer é seguir a corrente

Como não existe índice, percorrer uma lista ligada é caminhar de nó em nó. Você começa na cabeça, olha o valor daquele nó, pula para o próximo pela ligação e repete, até cair no nada. É um laço, mas guiado pela ligação, não por um contador que vai de 0 até o tamanho. A variável que aponta para o nó da vez costuma se chamar atual: ela começa na cabeça e, a cada volta, avança para atual.proximo. O laço para quando atual vira o nada. Esse padrão de andar pela corrente é a base de quase tudo que se faz com lista ligada: buscar um valor, contar os nós, imprimir todos.

// percorrer a lista, imprimindo cada valor
atual <- cabeca
enquanto atual != nada faca
  escreva(atual.valor)
  atual <- atual.proximo   // pula para o proximo no
fim
// para a lista 10 -> 20 -> 30, imprime 10, 20 e 30

Comeca na cabeça e avança pela ligação (atual.proximo) até bater no nada. Sem índice, só a corrente.

Por que espalhar os dados

Espalhar os valores em vez de enfileirá-los parece só complicar, mas resolve um problema real do vetor. O vetor precisa de um bloco contínuo de memória: dez casas encostadas, todas reservadas de uma vez. Se a lista cresce além do reservado, muitas vezes é preciso copiar tudo para um bloco maior. A lista ligada não pede bloco contínuo: cada nó pode morar em qualquer canto livre da memória, porque a ligação é que amarra a ordem, não a posição física. Crescer é só criar mais um nó e engatá-lo. Essa flexibilidade tem um custo, o acesso sequencial, e é essa troca que as próximas aulas exploram a fundo.