Linguagem C - Listas Duplamente Encadeadas

EnzoFerber

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.

[ Hits: 110.039 ]

Por: Enzo de Brito Ferber em 07/01/2009 | Blog: http://www.maximasonorizacao.com.br

7 0

Denuncie Favoritos Indicar Impressora

Inserindo dados

#define MALLOC(a) (a *) malloc ( sizeof(a) )

struct no
{
   int info;

   struct no *prox;
   struct no *ant;
};

// não vou usar typedef - complica a vida de quem está começando

struct no *inicio;
struct no *fim;

Bom, definida nossa estrutura, nossos ponteiros globais e nossa simplificação da malloc(), vamos começar a pensar em quais seriam os possíveis casos que uma função de inserção teria que analisar:

O novo nó passará a ser o novo primeiro nó (inicio).
O novo nó ocupará uma posição entre dois outros nós.
O novo nó passará a ser o novo último nó (fim).

Considerações:

As setas pretas GRANDES representam o ponteiro "inicio".
As setas azuis GRANDES representam o ponteiro "fim".
As demais "setinhas" representam as ligações dos ponteiros "prox" e "ant".

Bom, mostrada a teoria de como inserir um dado, podemos construir nossa função para inserir.

void inserir ( int info )
{
   struct no *novo = MALLOC ( struct no );
   struct no *atual;

   if ( !novo )
   {
      perror ( "Malloc: " );
      return ;
   }

   // atribuição do novo valor...
   novo->info = info;

   // MARCAÇÃO 1 - NÃO HÁ ELEMENTOS NA LISTA.
   if ( !inicio )
   {
      novo->prox = NULL;
      novo->ant  = NULL;

      inicio = novo;
      fim = novo;

      return ;
   }

   // se não for o primeiro elemento da lista...
   // MARCAÇÃO 2 - CASOS DE INSERÇÃO
   atual = inicio;

   while ( atual )
   {
       if ( atual->info < info )
          atual = atual->prox;
       else
       {
          // MARCAÇÃO 3 - caso 2
          if ( atual->ant )
          {
             novo->prox = atual;
             novo->ant = atual->ant;
             atual->ant->prox = novo;
             atual->ant = novo;

             return ;
          }
          // MARCAÇÃO 4 caso 1
          novo->prox = atual;
          novo->ant = NULL;
          atual->ant = novo;
          inicio = novo;

          return ;
       }
   }
   // MARCAÇÃO 5 - caso 3
   fim->prox = novo;
   novo->prox = NULL;
   novo->ant = fim;
   fim = novo;

   return ;
}

MARCAÇÃO 1:

A função inserir() primeiro certifica-se de que há uma lista para poder entrar em um loop de procura. Se não houver uma lista ( !inicio), elá criará uma.

if ( !inicio)
Se não há uma lista...

novo->prox = NULL;
novo->ant = NULL;

O ponteiro para o próximo nó do novo nó será nulo, assim como o ponteiro para o nó anterior, pois este será o único nó da lista atualmente.

inicio = novo;
fim = novo;

Isso "cria" a lista: toda vez que a função inserir() for chamada, ela fara a comparação "if(!inicio)", e como agora o ponteiro inicio terá um valor, esta comparação será falsa e a função executará a próxima parte. O ponteiro fim tem que ser iniciado também, pois se por algum motivo for usado sem nenhum valor por qualquer outra função, provavelmente causará quebra do programa.

MARCAÇÃO 2:

atual = inicio;

Esta atribuição garante que possamos varrer a lista conservando o endereço original do ponteiro inicio. "atual" é um ponteiro auxiliar de varredura. Para todas as função que varram a lista você precisará de um, a não ser que reconstrua a lista depois de todas as vezes que usar o ponteiro "inicio" ou "fim".

while (atual)

É auto-explicativo, mas vamos lá. Toda vez que o loop voltar ao inicio, ele fará uma comparação para checar se não chegou ao final da lista (ou ao inicio, dependendo da direção de sua varredura). Se atual for NULL (ou seja, fim da lista), o loop é cancelado.

if ( atual->info < info)

Este é o responsável por toda a função de inserção (Tá, exagerei um pouco...). Mas o que isso faz é comparar se a nova informação é maior do que a informação do nó atualmente sendo testado (note que ordem crescente foi a ordem escolhida para ordenação - certifique-se sempre de usar sinais/funções certas de comparação para a ordenação escolhida, errar aqui quase sempre significa quebra do programa).

atual = atual->prox;

Caso o if acima seja verdadeiro, ou seja, a nova informação é maior do que a informação atualmente sendo testada, esta linha faz com que 'atual' passe a ser o próximo item (Atribuições de endereço...).

Obs.: Note também que podemos nos referenciar ao elemento 'atual' da figura de 'atual->prox->ant'.

else {

Bom, isto é o que vai acontecer se a comparação der falsa (A nova informação é menor que o item atualmente sendo comparado - o que significa: inserção).

MARCAÇÃO 3:

if ( atual->ant )

Esta linha certifica-se de que o nó "atual" não é o primeiro nó da lista. Sim, qual o único nó da lista que possui um ponteiro "ant" com valor NULL? Sim, o primeiro nó. Então, se esta comparação for VERDADEIRA, significa que o valor de "atual->ant" NÃO É NULL, logo, não é o primeiro nó.

novo->prox = atual;
novo->ant = atual->ant;
atual->ant->prox = novo;
atual->ant = novo;
return ;

Bom, não tem como explicar isso melhor do que uma figura explicaria, então é só olhar como é feita a inserção na figura no início da página - CASO 2. Na figura, o ponteiro "atual" seria o quadrado INFO da direita. Soltem a imaginação!!!

MARCAÇÃO 4:

Estas próximas linhas poderiam estar dentro de um "else" do "if" da marcação 3... Sim, pois isto aqui só acontecerá se o "atual->ant" for NULL, ou seja, se o nó atual for o primeiro nó! Então vá lá ver na figura o caso 1 e novamente solte a imaginação...

MARCAÇÃO 5:

Se o programa sair do loop while(), significa que "atual" chegou ao último elemento e ainda assim, a nova informação era maior do que a informação atualmente sendo testada. Então é só inserir o elemento no final da lista. Bora pra figura ver o caso 3... e de novo, outra vez, novamente: solte a imaginação. O bom entendimento de listas encadeadas, árvores e afins está na visualização mental do negócio todo, quando conseguir ver as setinhas movimentando de uma lado para o outro para remover elementos ou inserí-los, você fará as funções de olhos fechados.

É, agora que inserimos os elementos não queremos eles lá mais não... vamos procurar e excluir esses @#$*%!

Página anterior Próxima página

Páginas do artigo

   1. Introdução
   2. Listas encadeadas
   3. Inserindo dados
   4. Pesquisando
   5. Removendo dados
   6. Código completo
   7. Conclusão

Outros artigos deste autor

Linguagem C - Funções Variádicas

Linguagem C - Árvores Binárias

Leitura recomendada

Algoritmo... como fazer?

Dicas para aprender programação

Otimização de algoritmos

Tutorial SDL

Linguagem C - Árvores Binárias

Comentários

[1] Comentário enviado por elgio em 07/01/2009 - 11:21h

struct LDE
{
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.

1 0

[2] Comentário enviado por elgio em 07/01/2009 - 11:53h

Sobre tamanhos de tipos.

Como exemplo ao que disse anteriormente, o tamanho dos dados varia de acordo com a arquitetura. Ponteiro para qualquer coisa tem sempre o mesmo tamanho (isto é, não será maior se for ponteiro para double), mas não é certo dizer que o tamanho dele é 4 bytes. Isto é verdade apenas para arquiteturas e COMPILADORES de 32 bits, onde o endereçamento é por 32 bits e um inteiros também o é!

Mas em uma arquiteutra de 64 bits, com kernel e compilador 64 bits, será diferente.

Coloquei em minha página um código simples para obter o tamanho de cada dado, dependendo da estrutura (o mais comum é 32 bits, mas se alguem tiver um Linux de 64 bits, vai poder comprovar o que estou dizendo).

http://gravatai.ulbra.tche.br/~elgio/disciplinas/?DISC=outras&MAT=VOL
(veja o "Codigo simples para imprimir tamanhos de dados")

0 0

[3] Comentário enviado por EnzoFerber em 07/01/2009 - 12:07h

@ elgio

Obrigado pelos comentários antes de mais nada ;)
Desculpe o equívoco, li uma vez sobre isso (tamanho por elemento), e também achei plausível (já que o sizeof() mostrou isso...). Obrigado por colaborar e mostrar que eu estava enganado! ;)

Agora, quanto a inserção em vetores: não mencionei no artigo nada sobre isso, tudo isso é pré-requisito. As vantagens que você citou no comentário acho que estão subentendidas nas funções que mostrei... Se quem estiver lendo souber sobre vetores e conseguir entender o codigo, vai perceber tudo o que você falou, então achei irrelevante colocar...

Sempre fui péssimo para ensinar, mas já que não tinha nenhum artigo sobre Listas aqui no VOL, decidi fazer um, é vivendo e aprendendo! ;)

Agora uma pergunta: você notou que não coloquei nenhuma função para desalocar a lista no final do programa certo? Uma vez perguntei em uma comunidade de programação em linux se era necessário fazer tal função, me responderam que era por uma questão de estilo, mas que o sistema operacional faria isso mesmo sem minha função. Esta informação esta correta?

[]'s
Slackware_10

0 0

[4] Comentário enviado por EnzoFerber em 07/01/2009 - 12:14h

Hmm, vi seu código, sei disso.

Sei que os ponteiros ocupam espaço, só que sempre achei (desde que li sobre) que quando você atribuía endereços eles "passavam a ser" o elemento (como disse no artigo), sendo assim, paravam de ocupar o espaço do ponteiro propriamente dito e passavam a ocupar o espaço do elemento a qual foram atribuídos. E é por isso que coloquei o sizeof(novo1) por exemplo, mesmo com os 2 ponteiros não nulos presentes, a estrutura continua a apresentar tamanho 4 bytes. Isso achei estranho, deve ser bug da função :P

E sim, agora vendo o que você falou, vejo que o tamanho é realmente 12 bytes por uma única coisa:

struct LDE *novo = MALLOC(struct LDE);

Isso vai alocar sizeof(struct LDE) de memória, e esse tamanho é 12. Sim, coloquei uma informação errada no artigo. :(
Mais deu pra entender o porque eu assumi isso? sizeof() maledito!

Obrigado pela colaboraçao mais uma vez.

[]'s
Slackware_10

0 0

[5] Comentário enviado por elgio em 07/01/2009 - 12:23h

Sobre DESALOCAR espaço, não é uma questão de estilo.

Isto é uma das coisas que fazem parte do que chamo "Manual do bom programador", entre outras:
a) sempre testar se realmente alocou
b) sempre testar arquivos
c) sempre fechar arquivos.

eu EXIJO isto dos meus alunos!

Explicando melhor...

Seu amigo está certo ao dizer que o Sistema Operacional desaloca tudo, fecha tudo, limpa e deixa a casa em ordem quando o seu programa encerra. Mas esquecer de fazer a limpeza pode trazer SÉRIOS PROBLEMAS.

Se o teu programa é do tipo que inicia, faz algo e termina, OK. É desnecessário este cuidado.
Mas se tu estiver programando algo que nunca termina? Um serviço do SO, por exemplo, como um servidor http? Hmmm...

Se tu fica alocando, alocando, alocando e nunca desaloca, chegará um ponto que não terás mais memória. O servidor apache teve um BUG deste tipo certa vez. Era necessário reinicar ele periodicamente para ele "se limpar" :-D

O mesmo para arquivos abertos. Se abriu, usou, FECHA! Mas o So não fecha automaticamente? Sim, quando o programa encerrar e SE ENCERRAR CORRETAMENTE! (um kill -9 poderá resultar em perdas de dados).

Logo, nada melhor do que se acostumar a fazer do jeito certo, o jeito que sempre funciona, seguindo o que chamo de manual do bom programador:

- alocou? desaloca
- abriu? fecha
- tentou alocar? testa se conseguiu.
- tentou abrir arquivo? testa se conseguiu.

SEMPRE!

0 0

[6] Comentário enviado por EnzoFerber em 07/01/2009 - 12:30h

Bom, tudo isso eu faço,

A única coisa que realmente não faço, é destruir a lista encadeada, pois o programa vai acabar, e desaloca apenas para deletar.
Mas vou passar a fazer isso. :)

Obrigado denovo!!!
[]'s

0 0

[7] Comentário enviado por elgio em 07/01/2009 - 12:32h

"E é por isso que coloquei o sizeof(novo1) por exemplo, mesmo com os 2 ponteiros não nulos presentes, a estrutura continua a apresentar tamanho 4 bytes. Isso achei estranho, deve ser bug da função :P"

Não é BUG.

Tem que entender o que realmente aconteceu.

novo, novo1 e novo2 NÃO SÃO ESTRUTURAS!
São ponteiros.
Seus conteúdos são endereços de memória, ou seja, para onde eles apontam. E será SEMPRE de 4 bytes (no caso de archs 32 bits) não importanto se para onde eles apontam tem um inteiro ou estrutura.

Veja este exemplo:

struct LIXO {
int d1, d2, d3; // 3x 4 = 12 bytes
double d4[10]; // 10x 8 bytes = 80 bytes
}

Bom, a estrutura terá 92 bytes (no mínimo! compiladores como o gcc sempre alocam multiplos de 8, podendo variar)

struct LIXO a; // isto é uma variável DO TIPO struct LIXO. Ocupará SIM 92 bytes
struct LIXO *p; // p NÃO É DO TIPO scruct LIXO. É do tipo PONTEIRO e ponteiros sempre tem 4 bytes. eles apontam para algo

printf("%d\n", sizeof(a)); // deverá imprimir no mínimo 92
printf("%d\n", sizeof(p)); // imprimirá 4 em 32 bits e 8 em 64 bits

}

To vendo se tenho algum exemplo já preparado para alunos para postar aqui.

0 0

[8] Comentário enviado por EnzoFerber em 07/01/2009 - 12:49h

Aaaaaaaaahhhhhhhhhh!

Nossa, agora eu me envergonhei, meu deus, cade o buraco pra eu enfiar a cabeça? auhauhauhauah

Como escrevi uma bobagem dessas no artigo?? o.O

Deve ser o tempo parado...
Bom, agora voltando à ativa e com pessoas colaborando as coisas vão melhorar....

Sinceramente, me desculpem.

Obrigado elgio,
[]'s
Slackware_10

0 0

[9] Comentário enviado por elgio em 07/01/2009 - 12:54h

???
Enzo...

Seria bom que você apagasse ou editasse o comentário acima.

Idiotisse? Asneira?

Só erra quem tenta. Teu artigo não está errado, apenas levemente incompleto e isto não lhe tira o mérito.

E se você olhar bem o meu perfil verás que eu só intervenho em artigos que valham a pena. Eu realmente não perco mais meu tempo comentando os artigos que eu realmente considere "idiotisse" :-D

0 0

[10] Comentário enviado por EnzoFerber em 07/01/2009 - 12:59h

Tudo bem, asneira e idiotice podem ter sido um pouco pesadas, mas acho que corretas, pois escrevi que uma boa noção de ponteiros seria necessária, e não foi isso que demonstrei ;)

Mas convenhamos, a primeira página do artigo poderia ser totalmente reformulada apresentando os conceitos que você expos aqui, por exemplo. Obrigado pelo apoio,

[]'s
Slackware_10

0 0

[11] Comentário enviado por cesperanc@ em 08/01/2009 - 01:43h

Parabéns pelo artigo. Apesar dos pequenos erros (eu só me apercebi pelos pertinentes comentários do elgio), o artigo está bastante bom e explica bastante bem os conceitos pretendidos. Os comentários apresentaram uma discussão interessante.

0 0

[12] Comentário enviado por removido em 09/01/2009 - 10:58h

Parabéns pelo seu artigo, fora alguns detalhes, está bem completo! Agradeço também ao Elgio pelos complementos! É importante saber bem estes conceitos, principalmente para as aulas de Projetos de Sistemas Operacionais que deve ser lecionadas pelo Prof. Roland aí em Gravataí :) Um abraço! Alex.

0 0

[13] Comentário enviado por psfdeveloper em 25/08/2010 - 13:22h

Parabéns pelo artigo, Enzo.

Acredito que os erros apontados nos comentários são normais, afinal, todo mundo erra. Não seria interessante você escrever um artigo transformando esse seu programa de listas duplamente-encadeadas em uma biblioteca C (evitando o uso das variáveis globais inicio e fim, por exemplo, colocando funções que recebam as listas, criando um tipo para receber listas como variáveis e coisas do tipo) ou um artigo a respeito de árvores binárias balanceadas ou mesmo de outros tipos de estruturas em árvore?

0 0

[14] Comentário enviado por EnzoFerber em 14/04/2015 - 13:28h

Obrigado a todos pelos comentários, em especial ao Elgio, que me fez ver erros grosseiros que havia cometido na introdução do artigo. Esse ano (2015), entrei em contato com o Fábio (administrador do VoL) e expliquei a situação (artigo incorreto). Perguntei se havia algum modo de corrigi-lo e ele prontamente se dispôs a receber uma correção por email e fazer a atualização no site.

Hoje, 14 de abril de 2015, a página da introdução foi trocada por uma outra que contém informações corretas. Então, a todos que virem os comentários anteriores, trata-se de uma discussão sobre alguns conceitos errôneos da antiga "Introdução".
Obrigado Fábio, pela chance de consertar um erro e manter a qualidade do VoL.

Enzo Ferber
[]'s

0 0