Linguagem C - Listas Duplamente Encadeadas
Neste artigo explicarei o que são listas duplamente encadeadas, como construí-las e suas vantagens e desvantagens. O pré-requisito para compreender bem o artigo é uma boa noção de ponteiros.
Parte 7: Conclusão
Bom, não há muito o que dizer, mas há.
A lista duplamente encadeada é, na minha opinião, o segundo melhor tipo de organização de dados na memória, perdendo apenas para árvores binárias auto-balanceáveis (AVL). Você pode criar algoritmos de organização que diminuem em até 4x (ou mais) o tempo de pesquisa em uma lista, e a construção de uma lista dupla é muito mais simples do que construir uma árvore binária AVL. Então, estude profundamente sobre listas duplamente encadeadas, pois este é um excelente tipo de organização.
O número de comparações que uma função de pesquisa faz em uma lista dupla é:
E está é realmente a única desvantagem (ao meu ver) das listas duplamente encadeadas: o tempo de busca. Notar esta deficiência em programas com apenas algumas centenas de dados é muito difícil, mas depois de adicionar dezenas de milhares de dados você percebe (sim, já fiz o teste).
Mas com os algoritmos certos para seu programa aplicados, você pode reduzir o número de comparações do pior caso para até n/4. :)
E o melhor jeito de estudar um tópico de programação é lendo códigos, e aqui no VOL mesmo existem pelo menos uma dúzia de códigos tratando desse assunto, inclusive postei um a uns dias atrás (do dia que estou escrevendo isso aqui).
E sempre lembrem-se:
O Google é nosso amigo.
[]'s
A lista duplamente encadeada é, na minha opinião, o segundo melhor tipo de organização de dados na memória, perdendo apenas para árvores binárias auto-balanceáveis (AVL). Você pode criar algoritmos de organização que diminuem em até 4x (ou mais) o tempo de pesquisa em uma lista, e a construção de uma lista dupla é muito mais simples do que construir uma árvore binária AVL. Então, estude profundamente sobre listas duplamente encadeadas, pois este é um excelente tipo de organização.
O número de comparações que uma função de pesquisa faz em uma lista dupla é:
- No melhor caso: UMA - o nó procurado é o primeiro nó
- No caso médio: (n/2) - onde "n" é o número total de entradas que você possui na lista
- No pior caso: n - número total de entradas
E está é realmente a única desvantagem (ao meu ver) das listas duplamente encadeadas: o tempo de busca. Notar esta deficiência em programas com apenas algumas centenas de dados é muito difícil, mas depois de adicionar dezenas de milhares de dados você percebe (sim, já fiz o teste).
Mas com os algoritmos certos para seu programa aplicados, você pode reduzir o número de comparações do pior caso para até n/4. :)
E o melhor jeito de estudar um tópico de programação é lendo códigos, e aqui no VOL mesmo existem pelo menos uma dúzia de códigos tratando desse assunto, inclusive postei um a uns dias atrás (do dia que estou escrevendo isso aqui).
E sempre lembrem-se:
O Google é nosso amigo.
[]'s
{
int info;
struct LDE *prox;
struct LDE *ante;
};
Não ocupa 12 bytes?
Você está enganado!
Toda a vez que for criado um elemento desta estrutura, ela ocupará UM espaço para um inteiro e DOIS espaços para ponteiros.
Se considerar o GCC 32 bits, ambos, inteiro e ponteiro, tem 4 bytes. Logo, NESTE CASO, Gcc32 bits, a estrutura ocupará SIM 12 bytes de tamanho.
Para 10 elementos de vetores de inteiros se ocupará exatos 40 bytes (em archs e compiladores 32 bits).
Se for uma lista encadeada dos mesmos 10 elementos, se ocupará 120 bytes (10x o tamanho de uma estrutura e cada estrutura ocupa 4 bytes para o info, 4 bytes para o ponteiro prox e 4 bytes para o ponteiro ante).
As vantagens/desvantagens de uma lista encadeada não tem a ver com economia de espaço, mas sim com a flexibilidade. Uma lista encadeada pode crescer até o limite de memória disponível e sempre eu posso "alocar mais um". Um vetor eu preciso previamente decidir o tamanho. Se 10, serão 10 e ponto! Precisei de 11? Não dá para aumentar o vetor em tempo de execução (ops, até dá com realloc, mas ai e outro tiro no pé).
Outra vantagem das listas encadeadas é a possibilidade de inserir ordenado ou remover no meio. Imagine um vetor de 15000 posições, 10mil delas ocupadas (de 0 a 9999). Ele está ORDENADO e preciso inserir o valor X que pela ordenanação ele deve ser inserido em vet[15]. Como é vetor, eu preciso:
(a) mover [9999] para [10000], [998] para [999], ..., [15] para [16] para inserir o novo elemento em [15].
(b) ou inserir no final [10000] e executar algum algoritmo de ordenamento como o quick sort
Se for lista encadeada, basta inserir na posição e ajustar os ponteiros ante e prox corretamente.
Listas encadeadas e suas derivações (duplamente, circular, com header, etc) são estrutura de dados muito úties, resolvem um monte de problemas, mas em comparação com vetores simples são mais complicados de manipular e consomem mais memória por elemento SIM.