Organização, representação e operações
Fundamentos de estruturas de dados
Uma estrutura de dados organiza informações para que operações como acessar, inserir, remover e buscar possam ser realizadas de maneira definida e eficiente.
Três perguntas diferentes
- O que é guardado? Números, textos ou registros com vários campos.
- Como é organizado? Em posições contíguas de um array ou em nós ligados por referências.
- Quais operações existem? Acessar, inserir, remover, buscar, consultar o topo ou consultar as pontas.
Tipo abstrato de dados
Pilha, fila e deque definem regras de acesso. Uma pilha exige LIFO; uma fila exige FIFO. Essas regras não obrigam uma única representação na memória.
Uma pilha pode ser implementada com array ou lista encadeada. O comportamento continua sendo LIFO.
O que alguns cursos chamam de “lista estática”
Normalmente é uma lista sequencial implementada sobre um array de capacidade fixa. O array guarda elementos em posições indexadas. Uma célula comum não possui o campo next: a próxima posição é obtida pelo índice seguinte.
Array fixo
tamanho usado = 3 · capacidade = 5
Array redimensionável
Ele também usa posições indexadas, mas pode solicitar um bloco maior quando a capacidade acaba. O tamanho lógico e a capacidade reservada são valores diferentes.
Exemplo conceitual após crescer
len = 4 · capacidade = 8
Em C++, std::vector usa armazenamento contíguo e mantém uma capacidade que pode ser maior que o tamanho lógico. Quando essa capacidade termina, uma realocação move os elementos para um bloco maior.
Lista encadeada
Aqui os elementos são nós. Como os nós não precisam estar em posições contíguas, cada nó guarda explicitamente uma referência para o próximo.
Os IDs do desenho representam referências didáticas. Eles não são índices e não tentam reproduzir endereços reais da memória.
Comparação das representações
| Operação | Array fixo | Array redimensionável | Lista encadeada |
|---|---|---|---|
| Acessar pelo índice | O(1) | O(1) | O(n) |
| Buscar um valor sem índice auxiliar | O(n) | O(n) | O(n) |
| Inserir no início | O(n), por deslocamentos | O(n), por deslocamentos | O(1), alterando head |
| Adicionar no final | O(1), se houver espaço | O(1) amortizado | O(1), se tail for mantido |
| Capacidade | Fixa | Ajustada por realocação | Um nó por inserção |
Um elemento pode ter vários campos
A estrutura organiza elementos. Cada elemento pode ser um objeto completo, e não apenas um inteiro.
#include <memory>
struct No {
int valor;
std::unique_ptr<No> proximo;
explicit No(int valor)
: valor(valor), proximo(nullptr) {}
};
int main() {
auto inicio = std::make_unique<No>(10);
inicio->proximo = std::make_unique<No>(20);
}Referências usadas
- NIST — data structure: definição de estrutura e operações associadas.
- NIST — array: elementos acessados por índices.
- NIST — linked list: itens ligados ao próximo.
- cppreference — std::vector: armazenamento contíguo, tamanho e capacidade.