Comparação entre listas estáticas e dinâmicas

Estática

Vantagens
● acesso a qualquer elemento com custo O(1), porque os elementos já tem indexação direta
● melhor uso do espaço: só armazena os dados
● não usa apontadores
– implementação mais simples
– menos sujeita a erros

Desvantagens
● custo elevado para inserções e retiradas em qualquer posição: O(n) (porque para inserir numa posição que não seja a última, é preciso deslocar todos os elementos para liberá-la e para retirar, é preciso retornar todos os elementos uma posição)
● redimensionamento é difícil e caro, quando possível - a função realloc() é muito cara.

Dinâmica

Vantagens
● alterar o tamanho da lista é simples
● inserção e retirada têm custo O(1) quando é apontado o item a ser retirado
● não necessita deslocar elementos

Desvantagens 
● acesso aos elementos é apenas seqüencial
● ocupa mais espaço para armazenar o mesmo número de itens
● uso de apontadores

● implementação mais sujeita a erros

Critérios para a escolha da melhor estrutura
Acesso: como será o acesso aos elementos?
– sempre seqüencial, sempre aleatório?

Número de elementos a ser armazenado
– é conhecido? é previsível? ou não?

Inserções e retiradas
– há muitas inserções e retiradas?
– onde são: no início? no fim? posições variáveis?

Demais operações a serem realizadas
– quais são? busca? máximo ou mínimo?
– pesquisa conjugada com inserção? ordenação eventual ou freqüente?
– retornar o elemento de uma posição específica?
– o custo de todas as operações deve ser analisado em relação a sua freqüência

Espaço ocupado

– há restrições? são muitos dados? dados cabem na memória?

Estruturas de Dados Lineares - Estáticas

Uma ED linear estática é implementada por um vetor. Fazem parte da ED: o vetor (dã) e as variáveis de controle (de inserções, retiradas, de quantos elementos tem) - números inteiros representando índices do vetor.
A definição de estrutura vazia pode ser feita via variáveis de controle, sem precisar inspecionar o vetor. Idem para estrutura cheia.
Testes de overflow (erro por tentar inserir elemento na estrutura cheia) e underflow (erro por tentar excluir elemento da estrutura vazia) são essenciais. As posições devem ser verificadas em cada caso de inserção e remoção de elementos.
Exemplo de implementação: pilha
int pilha[MAXTAM]; //a pilha :O
int topo; //a variável de controle, no caso sempre apontando para o topo da pilha

 inicializar a pilha:
topo = 0; //inicializa o controle, não o vetor

 definir a estrutura vazia
se topo = = 0 então a pilha está vazia

 comandos
return topo; //indica o número de elementos da pilha
return (topo = = 0); //indica se a pilha está vazia

 verificar se a estrutura está cheia

se (topo = = MAXTAM) então a pilha está cheia

 empilhar

se a pilha estiver cheia dá erro de overflow, senão adiciona o elemento no topo e incrementa ele

 desempilhar

se a pilha estiver vazia dá erro de underflow, senão decrementa o topo e retira o elemento dele

Estruturas de Dados lineares

Estruturas de dados são construções de dados que podem ser implementadas por uma linguagem de programação. Aprender a projetar EDs genéricas e eficientes é importante para saber escolher a certa para usar no programa: a escolha da ED afeta os algoritmos que podem ser utilizados, sendo mais ou menos eficientes, e para os mesmos dados, a ED pode ocupar mais ou menos espaço.
Nesse período serão estudadas EDs lineares: pilhas, filas e listas.
Definição formal de lista:
seqüência linear de 0 ou mais itens ou elementos cuja principal propriedade estrutural é a posição relativa dos elementos na seqüência:
 xi precede xi+1 para 1 <= i <= n - 1;
 xi sucede xi-1 para 2 <= i <= n;
 xi é o i-ésimo elemento da lista, x1 é o primeiro e xn é o último, sendo n o número de elementos (tamanho da lista).

Alguns tipos de listas:
 FIFO: First In First Out - o primeiro a entrar é o primeiro a sair
 LIFO: Last In First Out - o último a entrar é o primeiro a sair
 LRU: Least Recently Used - ordem dos menos utilizados recentemente
 MRU: Most Recently Used - ordem dos mais utilizados recentemente
 LFU: Least Frequently Used - ordem dos menos frequentemente utilizados
 MFU: Most Frequently Used -  ordem dos mais frequentemente utilizados

Pilhas e filas são variações de listas. Por exemplo, uma lista FIFO funciona como uma fila e uma LIFO, como uma pilha.

Alocação estática e dinâmica de memória:
Alocação estática de memória é gerenciada pelo compilador e alocada na stack memory. Quando você declara um vetor, por exemplo, ele tem o tamanho definido (no programa ou em tempo de execução, mas é sempre AQUELE tamanho) e já é alocado num espacinho contínuo quando seu programa compila. O acesso a cada elemento do vetor é aleatório e tem mesmo custo: basta ir ao vetor[indice] e pronto.
Alocação dinâmica de memória é gerenciada pelo programador e alocada na parte da memória denominada dynamic heap. Por exemplo: numa lista encadeada, não há um número fixo de elementos. O tamanho da lista é limitado apenas pela memória (heap e virtual), sendo, assim, uma estrutura muito versátil. Portanto, a criação E EXCLUSÃO deles deve ser pensada por você. Lembrando que é muito importante excluir elementos "inúteis" senão eles ficam ocupando memória e não são apagados quando seu programa é fechado. O acesso aos elementos da lista encadeada tem custo diferente para cada um, pois é sequencial. Então, se o elemento buscado for o último, a lista vai ter que ser percorrida inteira, cada elemento apontando para o próximo, até chegar no desejado.
Listas estáticas são implementadas com vetores (coleção fixa de elementos do mesmo tipo armazenados de forma contígua e acessíveis por um índice que têm correspondência direta e sequencial com a memória)
Listas dinâmicas, ligadas ou encadeadas são implementadas com ponteiros. Para entender isso basta ir ao resuminho de PC 1!