Listas Encadeadas

Listas Encadeadas

Uma lista encadeada ou lista ligada é uma estrutura de dados linear e dinâmica. Cada elemento de uma lista encadeada é chamado de célula, e possui dois campos, um para guardar a informação e o outro para guardar o endereço da célula seguinte. A última célula da lista aponta para nulo.

O esquema a seguir representa uma lista ligada/encadeada:

As listas encadeadas são dinâmicas, ou seja, tem a vantagem terem seu tamanho variável. Diferente das Pilhas ou Filas implementadas a partir de vetores, as quais tem um tamanho máximo fixo, limitado pela declaração do tamanho do vetor.

Implementação de listas encadeadas em linguagem C

Na linguagem C, para implementar uma lista encadeada, formada por células, utilizamos para a declaração da célula uma struct com dois campos, um para a informação e um ponteiro que aponta para a próxima célula.

Declaração de uma célula de uma lista encadeada

typedef struct {
       int        conteudo;
       struct CEL *prox;
} CEL;

Fonte:.

Observações:

1. É conveniente tratar as células de uma lista encadeada como um novo tipo de dados, usando typedef, e atribuir um nome a esse novo tipo (ver Estruturas em C).
2. A declaração da estrutura usa recursividade, onde um dos campos da estrutura é do tipo da estrutura sendo declarada.

Exemplo

Declaração de uma lista encadeada em um programa main.

void main(void){
   CEL c;   /*A variável c é do tipo célula*/
   CEL *p; /*A variável p do tipo apontador para CEL*/ 
   c.conteudo = 1;
   p = &c; 
   printf("%d\n", c.conteudo);
   printf("%d\n", p->conteudo); 
}

Neste exemplo, ambas as chamadas à função printf() iriam imprimir o número 1.

Inicialização de uma lista

Uma lista encadeada é toda composta por elementos alocados dinamicamente em memória.

Para criar uma lista é preciso uma base ou raiz, que será sempre a mesma para uma lista. Esta raiz é uma variável ponteiro que aponta para uma lista ou que aponta para uma primeira célula vazia .

Normalmente, para listas, é usada a célula vazia, já para as pilhas e filas dinâmicas é usado o apontador para as respectivas bases.

A função seguinte pode ser usada no main após ser declarada a variável raiz que será do tipo apontador para lista. Esta cria uma célula vazia e faz a raiz a apontar para a mesma:

CEL *cria_lista(){
    CEL *novo, *aux;
    novo = (CEL *) malloc(sizeof(CEL)); /*Aloca memória do tamanho de uma célula*/
    if(novo == NULL) exit(0);           /*Se não alocar hpuver espaço na memória deve sair*/
    novo->prox = NULL;  /*Célula vazia aponta para NULL*/ 
    aux = novo; /*Para retornar o aux com o endereço da célula vazia*/ 
    return (aux); /*Retorna o aux*/
}

Incluindo um elemento no início da lista

A função recebe como parâmetro um ponteiro para a lista e o conteúdo que se deseja incluir:

CEL * inserirNoInicio(CEL * raiz, int numero){
    CEL *novo, *aux;
    aux = raiz;
    novo = (CEL *) malloc(sizeof(CEL)); //Aloca memória para nova célula
    if(novo == NULL) exit(0);           //Se não consegue alocar espaço sai   
    novo->conteudo = numero;
    novo->prox = aux->prox;
    aux->prox = novo;
    return(aux);
}

Referências

---

--Evandro.cantu (discussão) 12h40min de 22 de outubro de 2014 (BRST)

---