Inserir e remover: só religar ponteiros

O custo de empurrar no vetor

Imagine uma fila de dez pessoas e alguém que precisa entrar entre a terceira e a quarta. Num vetor, as posições são fixas e encostadas, então não há espaço vago no meio: para abrir a vaga, todo mundo da quarta em diante precisa dar um passo à frente. Se a fila tivesse mil pessoas e o novato entrasse no começo, quase mil teriam que se deslocar. Remover é o mesmo drama ao contrário: quando alguém sai do meio, todos atrás dele puxam um passo para trás, para não deixar buraco. Esse empurra-empurra é o custo que o vetor paga por manter tudo encostado e acessível por índice.

Religar em dois passos

Na lista ligada, esse empurra-empurra some. Para inserir um novo nó entre dois nós existentes, digamos entre A e C, você não move ninguém: só ajusta duas ligações. Primeiro, faz a ligação do novo nó apontar para C (o seguinte). Depois, faz a ligação de A apontar para o novo nó. Pronto: A aponta para o novo, o novo aponta para C, e a corrente segue inteira. A ordem desses dois passos é crítica. Se você religar A para o novo primeiro, perde a referência de C, porque era a ligação de A que guardava onde C estava. Por isso a regra é: primeiro prenda o novo nó no resto da corrente, depois solte o anterior nele.

// inserir o no "novo" depois do no "anterior"
// 1) o novo aponta para quem vinha depois do anterior
novo.proximo <- anterior.proximo
// 2) so agora o anterior aponta para o novo
anterior.proximo <- novo
// remover o no depois do anterior:
anterior.proximo <- anterior.proximo.proximo   // pula o no removido

Inserir: religa duas setas na ordem certa. Remover: liga o anterior direto ao seguinte, pulando o nó.

Por que isso é barato

A grande sacada é que religar custa sempre a mesma coisa, não importa o tamanho da lista. Inserir num vetor de mil elementos pode empurrar centenas deles; inserir numa lista ligada de mil elementos mexe em duas ligações, exatamente como numa lista de cinco. O trabalho não cresce com a lista. Existe uma pegadinha honesta: para religar você precisa já estar posicionado no nó anterior, e chegar até ele custa o passeio pela corrente. Ou seja, a religação em si é instantânea, mas achar o ponto certo é sequencial. Quando você já tem em mãos o nó anterior, como acontece ao percorrer a lista de uma vez, a inserção e a remoção são de fato baratíssimas.