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
No CPython, list usa um array redimensionável de referências e reserva espaço adicional para reduzir a frequência de realocações. Isso é detalhe da implementação CPython, não uma promessa sobre o layout interno de toda implementação de Python.
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.
from dataclasses import dataclass
# dataclass cria automaticamente o construtor que recebe os três campos.
@dataclass
class Aluno:
matricula: int
nome: str
nota: float
# Cada posição da lista guarda um objeto Aluno completo.
turma = [
Aluno(31, "Lia", 8.5),
Aluno(44, "Rui", 7.0),
]
# Ao percorrer a lista, acessamos separadamente os campos de cada objeto.
for aluno in turma:
print(aluno.matricula, aluno.nome, aluno.nota)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.
- CPython — listobject.c: redimensionamento e reserva adicional de capacidade.