Estruturas de Dados: Alocação Estática e Dinâmica

Alocação Estática de Memória

Lista Estática Sequencial

A lista estática sequencial é uma lista linear implementada como um arranjo (array) de registros, onde estão estabelecidas regras de precedência entre os seus elementos. Configura-se como uma coleção ordenada de componentes do mesmo tipo. Exemplos: Lista de Telefones, Lista de Alunos.

Características da Lista Estática Sequencial

• Os elementos na lista estão ordenados e armazenados fisicamente em posições consecutivas.
• A inserção de um elemento na posição i causa o deslocamento à direita dos elementos de i até o último.
• A eliminação do elemento i requer o deslocamento à esquerda dos elementos (i+1) até o último.
• Uma lista estática sequencial L, ou é vazia ou pode ser descrita como: L =

onde: a1 é o primeiro elemento da lista; ai precede ai+1; an é o último elemento da lista.

Vantagens

• Acesso direto indexado a qualquer elemento da lista.
• Tempo constante para acessar o elemento da posição i.

Desvantagens

• Movimentação de elementos nas operações de inserção e eliminação.
• O tamanho máximo da lista deve ser pré-estimado.

Quando Usar

• Listas pequenas.
• O tamanho máximo da lista for bem definido.
• Manipulação de dados com características de inserção e eliminação no final da lista.

Lista Estática Encadeada

Os elementos de uma lista estática encadeada são registros com um dos componentes (campos) destinados a guardar o endereço do próximo registro, possibilitando o encadeamento dos elementos da lista.

FOTO

Vantagens

• Não requer a movimentação dos elementos nas operações de inserção e eliminação.
• Apenas os campos de ligação são manipulados e alterados.

Desvantagens

• Necessário prever espaço máximo da lista.
• Aumento no tempo de execução.
• Necessidade de gerenciar o campo Dispo.
• Reserva de espaço para Dispo.
• O acesso não é indexado.

Quando Usar

• Quando for possível fazer uma boa previsão do espaço utilizado.
• Quando o ganho dos movimentos dos elementos sobre a perda de acesso direto a cada elemento for compensatório.

Alocação Dinâmica de Memória

Ponteiros

Na alocação estática de memória, como já foi abordada, há a necessidade do programador fazer uma estimativa prévia da quantidade de memória a ser ocupada pelos dados de sua aplicação. Isso se deve ao fato de que as estruturas de dados estáticas necessitam ser declaradas antes do início do código, sendo assim, chamadas de estruturas pré-referenciadas. A partir daí, o programador não tem muita flexibilidade para mudar essa situação.

Em contrapartida, na alocação dinâmica de memória, o programador dispõe de estruturas de dados pós-referenciadas, criando novos registros sob demanda e necessidade da aplicação, ficando a limitação apenas em relação à quantidade de memória física disponível no hardware.

As linguagens de programação modernas tornaram possível explicitar não apenas os dados, mas também os endereços desses dados. Isso é possível com a utilização de ponteiros, que são variáveis de memória que "apontam" para endereços de memória. Esses endereços de memória apontados pelos ponteiros são conhecidos como variáveis dinâmicas.