TADs vs Estruturas de dados
É importante entender dois conceitos fundamentais que muitas vezes se confundem:
Tipos abstratos de dados (TADs)
Definem o quê você pode fazer - quais operações existem e seu comportamento esperado. É o contrato da interface, a especificação abstrata. Um TAD diz "você pode empilhar e desempilhar", mas não diz como isso funciona por baixo dos panos.
Estruturas de dados
Definem como fazer - a implementação concreta na memória. É a realização prática do conceito. Uma estrutura de dados mostra exatamente como os bytes são organizados e manipulados.
Uma "stack" (pilha) é um TAD que define comportamento LIFO. Você pode implementá-la usando arrays ou linked lists - estruturas de dados diferentes, mesmo comportamento abstrato. A escolha da estrutura afeta performance, mas o TAD permanece o mesmo.
Organização lógica dos dados
A forma como os elementos se relacionam entre si define o tipo da estrutura:
Estruturas lineares
Estabelecem uma ordem sequencial clara - existe um primeiro elemento, um último, e todos os intermediários possuem exatamente um elemento anterior e um próximo. É como uma fila de pessoas: você sabe quem está à sua frente e quem está atrás.
Arrays, linked lists, stacks e queues são exemplos clássicos. Em uma stack (pilha), você empilha pratos um sobre o outro - só acessa o do topo. Em uma queue (fila), é como uma fila de banco - quem chega primeiro é atendido primeiro. O que importa é a ordem entre elementos, não como estão organizados na memória.
Estruturas não-lineares
Quebram essa ordem única. Aqui, um elemento pode se conectar a vários outros simultaneamente, formando hierarquias ou redes complexas. Como uma árvore genealógica ou rede social.
Trees (árvores) organizam dados hierarquicamente - como pastas e arquivos no seu computador. Graphs (grafos) representam redes arbitrárias - como rotas entre cidades ou conexões em redes sociais. Hash tables usam funções matemáticas para espalhar dados e acessá-los instantaneamente, como um índice de livro turbinado.
Perspectiva de memória
Além da organização lógica, existe a questão física: como os bytes são dispostos na memória RAM?
Memória contígua
Elementos armazenados um do lado do outro na memória. Como uma rua com casas numeradas sequencialmente.
Arrays funcionam assim. Cada elemento ocupa 4 bytes, então o elemento array[2] está matematicamente em endereço_base + (2 × 4). Acesso instantâneo O(1)! Mas inserir no meio? Precisa deslocar todos os elementos seguintes - imagine reorganizar uma estante de livros inteira porque você quer inserir um no meio.
Memória não-contígua
Elementos espalhados em diferentes regiões da memória, conectados por ponteiros. Como uma caça ao tesouro onde cada pista aponta para a próxima.
Linked lists funcionam assim. Cada nó carrega seu dado e um ponteiro para o próximo. Inserir no meio? Fácil - apenas redirecione dois ponteiros. Mas acessar o elemento 100? Precisa seguir 100 pistas sequencialmente - O(n).
O que as torna diferentes
Cada estrutura de dados faz tradeoffs:
- Organização na memória - Contígua (arrays) vs espalhada (linked lists)
- Como você acessa - Acesso direto vs percorrer um por um
- Velocidade das operações - Inserções rápidas mas buscas lentas, ou vice-versa
- Espaço extra usado - Pouca informação adicional vs muitos ponteiros
A escolha certa depende do seu caso de uso específico. Precisa de buscas rápidas? Hash tables. Manter ordem? Binary search trees. Comportamento LIFO? Stacks.