1. O limite do vetor
O capítulo 2 mostrou que vetores são ótimos para acesso direto por índice, mas caros para inserir e remover no início ou no meio — porque exigem deslocar todos os itens seguintes em memória contígua. Quando o padrão de uso de uma coleção é o oposto — muita inserção e remoção nas pontas, pouco acesso por posição aleatória — existe uma família de estruturas mais adequada. É o assunto deste capítulo.
2. Lista encadeada
Uma lista encadeada (linked list) não guarda seus itens em blocos contíguos de memória. Em vez disso, cada item é um nó independente, guardado em qualquer posição livre da memória, contendo duas coisas: o valor e uma referência (ponteiro) para o próximo nó da lista.
Fig. 1 — Lista encadeada: nós ligados por referência, não por posição contígua em memória.
Isso muda os custos: inserir ou remover um nó no início da lista é O(1) — basta criar o novo nó e apontar sua referência para o antigo primeiro nó, sem deslocar nada. Em compensação, não existe acesso direto por índice: para chegar ao quinto nó, é preciso percorrer os quatro anteriores, seguindo as referências uma a uma — isso é O(n).
| Operação | Vetor | Lista encadeada |
|---|---|---|
| Acessar por índice | O(1) | O(n) |
| Inserir/remover no início | O(n) | O(1) |
| Inserir/remover no final | O(1) | O(n) ou O(1)* |
| Percorrer tudo | O(n) | O(n) |
* O(1) se a lista mantiver uma referência direta ao último nó; O(n) se precisar percorrer até lá.
3. Pilha (Stack) — o princípio LIFO
Uma pilha é uma estrutura em que só é possível adicionar ou remover itens por uma única extremidade, chamada de topo. O princípio é LIFO — Last In, First Out ("o último a entrar é o primeiro a sair"). Pense numa pilha de pratos: você só consegue tirar o de cima; para chegar no de baixo, precisa tirar todos os de cima primeiro.
As duas operações fundamentais de uma pilha são empilhar (
push, adiciona no topo) e desempilhar (
pop, remove e retorna o item do topo). Ambas são O(1).
Fig. 2 — Pilha: inserções e remoções sempre pelo topo, LIFO.
Um exemplo de pilha que você já usa todos os dias sem perceber: a funcionalidade de "desfazer" (Ctrl+Z) de praticamente qualquer editor. Cada ação realizada é empilhada; ao desfazer, a ação mais recente (o topo) é a primeira a ser revertida. Outro exemplo, fundamental para entender o próximo capítulo: toda vez que uma função chama outra função, o programa empilha essa chamada numa estrutura chamada pilha de chamadas (call stack) — e desempilha conforme cada função termina e retorna.
4. Fila (Queue) — o princípio FIFO
Uma fila é o espelho da pilha: itens entram por uma extremidade e saem pela outra. O princípio é FIFO — First In, First Out ("o primeiro a entrar é o primeiro a sair") — exatamente como uma fila de pessoas no mundo real.
As operações fundamentais são enfileirar (enqueue,
adiciona no final da fila) e desenfileirar (dequeue,
remove e retorna o item do início da fila). Ambas são O(1) quando a fila é implementada com
referências para início e fim (como uma lista encadeada) — numa implementação ingênua sobre
vetor, desenfileirar pode custar O(n), pelo mesmo motivo do capítulo 2: remover do início de
um vetor exige deslocar tudo.
Fig. 3 — Fila: entra por um lado, sai pelo outro, FIFO.
Exemplos reais de fila: uma fila de impressão (o primeiro documento enviado é o primeiro impresso), ou uma fila de mensagens entre sistemas (um serviço publica mensagens, outro processa na ordem em que chegaram). Esse último exemplo — filas de mensagens — é um padrão extremamente comum em sistemas distribuídos, e se apoia exatamente no mesmo princípio FIFO explicado aqui.
5. Comparando as três estruturas
| Estrutura | Regra de acesso | Quando usar |
|---|---|---|
| Vetor | Qualquer posição, por índice | Acesso aleatório frequente, tamanho previsível |
| Lista encadeada | Sequencial, seguindo referências | Muitas inserções/remoções no início, pouco acesso por posição |
| Pilha (LIFO) | Só pelo topo | Desfazer ações, controle de chamadas de função, análise de expressões aninhadas (parênteses, por exemplo) |
| Fila (FIFO) | Entra num lado, sai do outro | Processar tarefas na ordem de chegada: impressão, mensagens, filas de atendimento |
Em JavaScript, tanto pilha quanto fila costumam ser implementadas usando um array comum:
push()/pop() para pilha, e
push()/shift() para fila. Vale
lembrar da seção 4 do capítulo 2: shift() é O(n), então uma fila
implementada dessa forma tem uma operação mais cara do que uma implementação baseada em
lista encadeada — na prática, para filas grandes e de alto volume, isso importa.