Estruturas Lineares: Linked Lists, Pilhas e Filas
Vá além dos arrays e domine Linked Lists para inserções eficientes, Pilhas para o princípio LIFO e Filas para o FIFO. Ferramentas essenciais no seu arsenal.
Por muito tempo, eu me perguntava: "pra que raios eu usaria uma Linked List se já existem Arrays?". Arrays são nativos, parecem mais simples e resolvem quase tudo. Essa dúvida persistiu até eu cair numa entrevista onde o problema era implementar um LRU Cache (Least Recently Used Cache).
Tentei resolver com um Array e a performance da minha solução foi péssima. Cada vez que um item era acessado, eu tinha que movê-lo para o final do array, uma operação O(n). Foi aí que o entrevistador deu a dica: "E se a inserção e remoção no início da lista fossem... instantâneas?".
A ficha caiu. Era um caso de uso clássico para Linked Lists. Esta aula é sobre te dar essas "fichas". Vamos entender essas estruturas que parecem de nicho, mas que são as ferramentas perfeitas para problemas específicos que adoram aparecer em entrevistas.
1. Além dos Arrays: Ferramentas Especializadas
Se Arrays são o seu canivete suíço, pense em Linked Lists, Pilhas e Filas como ferramentas especializadas: uma chave de fenda, um alicate e um martelo. Você não os usa para tudo, mas para a tarefa certa, eles são imbatíveis.
2. Linked Lists (Listas Ligadas): A Corrente de Dados 🔗
Diferente de um Array, que armazena dados em um bloco contínuo de memória, uma Linked List é uma coleção de nós (nodes) espalhados pela memória. Cada nó contém duas informações: o dado em si e um ponteiro (uma referência) para o próximo nó da sequência.
Analogia: Caça ao Tesouro 🗺️
Arrays vs. Linked Lists: Os Trade-offs
| Operação | Array | Linked List |
|---|---|---|
Acesso por Índice (get(i)) | O(1) | O(n) |
| Inserção/Deleção no Início | O(n) | O(1) |
| Inserção/Deleção no Final | O(1) (amortizado) | O(n) (Singly) / O(1) (Doubly) |
Resumo: Use Arrays quando precisar de muito acesso rápido por índice. Use Linked Lists quando precisar fazer muitas inserções ou remoções no início da lista.
3. Pilhas (Stacks): O Princípio LIFO 🥞
Uma Pilha segue o princípio LIFO: Last-In, First-Out (O último a entrar é o primeiro a sair).
Analogia: Pilha de Pratos 🍽️
As operações principais são todas O(1):
Caso de Uso Clássico: Parênteses Balanceados
Um problema comum em entrevistas é verificar se uma string de parênteses, colchetes e chaves está "balanceada". Uma pilha é a solução perfeita para isso.
function ehValido(s) { // s é uma string como "()[]{}"
const stack = [];
const map = {
"(": ")",
"[": "]",
"{": "}",
};
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (map[char]) {
// Se o caractere é de abertura, empilha ele.
stack.push(char);
} else {
// Se é de fechamento...
// 1. Pega o último de abertura que foi empilhado.
const lastOpen = stack.pop();
// 2. Verifica se o caractere atual fecha o último que foi aberto.
if (char !== map[lastOpen]) {
return false;
}
}
}
// 3. No final, a pilha deve estar vazia.
return stack.length === 0;
};
// ehValido("()[]{}") -> true
// ehValido("([)]") -> false
// ehValido("{[]}") -> true4. Filas (Queues): O Princípio FIFO 🛒
Uma Fila, por outro lado, segue o princípio FIFO: First-In, First-Out (O primeiro a entrar é o primeiro a sair).
Analogia: Fila de Supermercado 🛒
As operações principais também são O(1) (com a implementação correta):
Filas são muito usadas em algoritmos de busca em grafos (como o BFS, que veremos mais à frente), no gerenciamento de tarefas assíncronas, e em sistemas de mensageria.
💊 Pílula Devly
Arrays são seu canivete suíço, mas para tarefas específicas, você precisa da ferramenta certa. Linked Lists brilham em inserções/remoções sequenciais. Pilhas são perfeitas para problemas de "ida e volta" ou "último a entrar, primeiro a sair" (LIFO). Filas são para ordem de chegada (FIFO). Saber qual usar é um sinal de que você pensa como um arquiteto de soluções, não apenas como um codificador.