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 4: Pesquisando
As funções de pesquisa em listas duplamente encadeadas são muito simples. Desde que você esteja implementando uma função que busque em apenas uma direção. As que buscam em duas direções simultaneamente envolvem threads e são um tanto maiores e fugiriam do assunto do artigo, então vou usar como exemplo uma função para buscar em apenas um sentido.
Para fazer uma pesquisa você tem apenas um caso:
1. Tem que encontrar o maledito do nó.
Como fazemos isso?
Um simples loop com comparação resolveria tranquilamente o problema.
Agora vamos só imprimir na tela a mensagem: "Achei o maledito!", ou vamos retornar o endereço dele para que a função que ordenou a busca faça alguma coisa com ele. Vamos retornar o endereço, fica muito mais interessante.
Sim, eu sei, grotescamente(!) gigantesca essa função de pesquisa, mas funciona.
O que ela faz é declarar um ponteiro "atual" que passa a conter o mesmo endereço do ponteiro global "inicio". Feito isso podemos entrar no loop de comparação.
while (atual) faz com que o loop aconteça ate o fim da lista (ate que atual seja NULL :)
if (atual->info == info)
ENCONTROU O MALEDITOOOO!
return atual
Retorna o endereço dele.
else
Senão...
atual = atual->prox;
return NULL;
Se a função chegar a esse ponto, significa que TODAS as comparações feitas resultaram em FALSO, ou seja, o elemento não foi encontrado, mas como nossa função precisa retornar alguma coisa, ela retornará NULL, que simbolizará "elemento não encontrado".
Agora que encontramos o tal sujeito "info", falta-nos apenas excluí-lo...
Para fazer uma pesquisa você tem apenas um caso:
1. Tem que encontrar o maledito do nó.
Como fazemos isso?
Um simples loop com comparação resolveria tranquilamente o problema.
Agora vamos só imprimir na tela a mensagem: "Achei o maledito!", ou vamos retornar o endereço dele para que a função que ordenou a busca faça alguma coisa com ele. Vamos retornar o endereço, fica muito mais interessante.
struct no *procurar ( int info )
{
struct no *atual = inicio;
while ( atual )
{
if ( atual->info == info)
return atual;
else
atual = atual->prox;
}
return NULL;
}
{
struct no *atual = inicio;
while ( atual )
{
if ( atual->info == info)
return atual;
else
atual = atual->prox;
}
return NULL;
}
Sim, eu sei, grotescamente(!) gigantesca essa função de pesquisa, mas funciona.
O que ela faz é declarar um ponteiro "atual" que passa a conter o mesmo endereço do ponteiro global "inicio". Feito isso podemos entrar no loop de comparação.
while (atual) faz com que o loop aconteça ate o fim da lista (ate que atual seja NULL :)
if (atual->info == info)
ENCONTROU O MALEDITOOOO!
return atual
Retorna o endereço dele.
else
Senão...
atual = atual->prox;
Se a função chegar a esse ponto, significa que TODAS as comparações feitas resultaram em FALSO, ou seja, o elemento não foi encontrado, mas como nossa função precisa retornar alguma coisa, ela retornará NULL, que simbolizará "elemento não encontrado".
Agora que encontramos o tal sujeito "info", falta-nos apenas excluí-lo...
{
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.