Considerações Finais Sobre Encadeamentos e Nós

Listas encadeadas

Uma lista encadeada é uma representação de uma sequência de objetos na memória do computador. Cada elemento da sequência é armazenado em uma célula da lista: o primeiro elemento na primeira célula, o segundo na segunda e assim por diante.

Estrutura de uma lista encadeada

Uma lista encadeada  (= linked list = lista ligada)  é uma sequência de células; cada célula contém um objeto de algum tipo e o endereço da célula seguinte.   Suporemos nesta página que os objetos armazenados nas células são do tipo int.  A estrutura de cada célula de uma tal lista pode ser definida assim:

struct cel {                                          
       int         conteudo;                                
       struct cel *prox;                                             
    };   
         

conteudo	prox

É conveniente tratar as células como um novo tipo-de-dados e atribuir um nome a esse novo tipo:

   typedef struct cel celula;

Uma célula  c  e um ponteiro  p  para uma célula podem ser declarados assim:

   celula  c;

   celula *p;

Se c é uma célula então  c.conteudo  é o conteúdo da célula e  c.prox  é o endereço da próxima célula. Se  p  é o endereço de uma célula, então  p->conteudo  é o conteúdo da célula e  p->prox  é o endereço da próxima célula.  Se  p  é o endereço da última célula da lista então   p->prox  vale NULL 

Endereço de uma lista encadeada

O endereço de uma lista encadeada é o endereço de sua primeira célula.  Se p é o endereço de uma lista, convém, às vezes, dizer simplesmente

"p é uma lista".

Listas são animais eminentemente recursivos. Para tornar isso evidente, basta fazer a seguinte observação:  se p é uma lista então vale uma das seguintes alternativas:

p == NULL  ou

p->prox  é uma lista.

Listas com cabeça e sem cabeça

Uma lista encadeada pode ser organizada de duas maneiras diferentes, um óbvia e outra menos óbvia.

Lista com cabeça.  O conteúdo da primeira célula é irrelevante: ela serve apenas para marcar o início da lista.  A primeira célula é a cabeça (= head cell = dummy cell) da lista.  A primeira célula está sempre no mesmo lugar na memória, mesmo que a lista fique vazia.  Digamos que ini é o endereço da primeira célula. Então  ini->prox == NULL  se e somente se a lista está vazia. Para criar uma lista vazia, basta dizer:

   celula c, *ini;

   c.prox = NULL;

   ini = &c;

ou

   celula *ini;

   ini = malloc( sizeof (celula));

   ini->prox = NULL;

Lista sem cabeça.  O conteúdo da primeira célula é tão relevante quanto o das demais. Nesse caso, a lista está vazia se o endereço de sua primeira célula é NULL.  Para criar uma lista vazia basta fazer:

   celula *ini;  

   ini = NULL;

[Veja "Alocação dinâmica de memória".]

Suporemos no que segue que nossas listas têm cabeça. O caso de listas sem cabeça será tratado nos exercícios. Eu prefiro listas sem cabeça (porque são mais "puras"), mas a vida do programador fica mais fácil quando a lista tem cabeça.

Exemplos

Eis como se imprime o conteúdo de uma lista encadeada com cabeça:

// Imprime o conteúdo de uma lista encadeada

// com cabeça. O endereço da primeira célula é ini.

void imprima( celula *ini)

{

   celula *p;

   for (p = ini->prox; p != NULL; p = p->prox) 

      printf( "%d\n", p->conteudo);

}

Eis a correspondente função para lista sem cabeça:

// Imprime o conteúdo de uma lista encadeada ini.

// A lista não tem cabeça.

void imprima( celula *ini)

{

   celula *p;

   for (p = ini; p != NULL; p = p->prox) 

      printf( "%d\n", p->conteudo);

}

Busca em uma lista encadeada

Veja como é fácil verificar se um inteiro x pertence a uma lista encadeada, ou seja, se é igual ao conteúdo de alguma célula da lista:

// Esta função recebe um inteiro x e uma lista

// encadeada de inteiros. O endereço da lista é

// ini e ela tem uma celula-cabeça. A função

// devolve o endereço de uma celula que contém x.

// Se tal celula não existe, a função devolve NULL.

celula *busca( int x, celula *ini)

{

   celula *p;

   p = ini->prox;

   while (p != NULL && p->conteudo != x) 

      p = p->prox; 

   return p; 

}

Que beleza! Nada de variáveis booleanas! A função se comporta bem até mesmo quando a lista está vazia.

Eis uma versão recursiva da mesma função:

celula *busca2( int x, celula *ini)

{

   if (ini->prox == NULL) 

      return NULL;

   if (ini->prox->conteudo == x) 

      return ini->prox;

   return busca2( x, ini->prox);

}

Conteúdo extraído de http://www.ime.usp.br/

VAMOS SEGUIR UM TUTORIAL 

Aproveitando e seguindo um tutorial simplificado falando de listas encadeadas para melhor aplicação prática.

Fechando com chave de ouro e bom humor, aqui vai uma importante mensagem:

Recomendo >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

.

  Mais detalhes...

Em homenagem às primeiras aulas do Profº Valente, seguem os ideogramas comentados:

	X 3 =
árvore		floresta

Aqui temos um outro exemplo simples, com o kanji 日、que significa sol ou dia. Se um sol já é brilhante, imagina então três:

	X 3 =
dia, sol		cristalino, claro, brilhante

Por último temos aqui o kanji de mulher. Com várias mulheres temos o que?

	X 3 =
mulher		barulhenta, imoral

Kanji