Uma estrutura de dados é uma forma de organizar e armazenar dados na memória para que possam ser acessados e modificados de forma eficiente. Um tipo de dados abstrato (ADT) é o modelo lógico — as operações e seu comportamento — independentemente de como é implementado.
O ADT descreve operações existem; a estrutura de dados decide elas são armazenadas e quão rápidas são.
ADT: Stack → push, pop, peek (LIFO behavior)
Implementations: → array-backed OR linked-list-backed
ADT: List → get(i), insert, remove
Implementations: → dynamic array OR linked list
# Both satisfy the "Stack" ADT, but have different cost profiles
stack = [] # list-backed stack
stack.append(10) # push -> amortized O(1)
top = stack[-1] # peek -> O(1)
stack.pop() # pop -> O(1)
| Preocupação | Pergunta a fazer |
|---|---|
| Padrão de acesso | Acesso aleatório ou sequencial? |
| Mutações | Inserção/exclusão frequente no meio? |
| Pedido | Classificado, FIFO, LIFO ou nenhum? |
| Pesquisas | Por índice ou por chave? |
A escolha certa é aquela cujas operações comuns são baratas para sua carga de trabalho.
Escolher a estrutura errada transforma uma operação O(1) em O(n), o que pode tornar o código milhares de vezes mais lento em escala.
Pensar em termos de ADT permite que você primeiro raciocine sobre comportamento, depois troque implementações sem reescrever os chamadores.