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 ou nó, e possui dois campos, um para guardar a informação e o outro para guardar o endereço do nó seguinte. O último nó 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

Como as listas encadeadas utilizam alocação dinâmica de variáveis, é importante ver como este recurso funciona na linguagem C:

• Alocando Variáveis Dinâmicas

Na linguagem C, para implementar uma lista encadeada, formada por nós, utilizamos para a declaração do nó uma struct com dois campos, um para a informação e um ponteiro que aponta para o próximo nó.

Além disto, precisamos de um ponteiro externo que aponta para o primeiro nó da lista, o qual será utilizado no programa principal para acessar a lista.

Declaração de um nó de uma lista encadeada

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

Observações:

1. É conveniente tratar os nós 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.

Funções para criação e manipulação de listas

Os exemplos a seguir foram adaptados da referência .

Inicialização de uma lista

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

Para criar uma lista é preciso um ponteiro externo, que será sempre o mesmo para uma lista. Este ponteiro aponta para o endereço da lista na memória.

A função seguinte pode ser usada no main após ser declarada a variável ponteiro externo para lista. Esta função cria um nó vazio e faz o campo *prox da raiz a apontar para NULL:

node *cria_lista(){
    node *novo = (node *) malloc(sizeof(node)); /*Aloca memória para o nó*/
    if(novo == NULL) exit(0);                   /*Se não houver espaço sai*/
    novo->prox = NULL;
    return (novo);
}

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:

void inserirInicio(node *lista, int numero){
    node *novo = (node *) malloc(sizeof(node));
    if(novo == NULL) exit(0);
    novo->conteudo = numero;
    novo->prox = lista->prox;
    lista->prox = novo;
}

Sequência de operações para inserir nó no início da lista:

1. Novo nó é criado;
2. Novo nó recebe conteúdo;
3. Como o novo será inserido no início, fazemos ele apontar para o primeiro nó da lista atual;
4. Finalmente mudamos o ponteiro externo da lista para que aponte para o novo nó.

Extraindo um elemento do início da lista

A função recebe como parâmetro um ponteiro para a lista e retorna o conteúdo da primeira posição.

Atenção: Para usar esta função a lista não pode estar vazia.

int removerInicio(node *lista){
    node *aux;
    int num;
    aux = lista->prox;
    num = aux->conteudo;
    lista->prox = aux->prox;
    free(aux);   //Libera memória alocada 
    return(num);
}

Extraindo um elemento do final da lista

A função recebe como parâmetro um ponteiro para a lista e retorna o conteúdo da primeira posição.

Atenção: Para usar esta função a lista não pode estar vazia.

int removerFim(node *lista){
    int num;
    node *ult, *penult;
    ult    = lista->prox;
    penult = lista;
    while(ult->prox != NULL){
            penult = ult;
            ult = ult->prox;
    }
    num = ult->conteudo;
    penult->prox = NULL;
    free(ult);   //Libera memória alocada
    return(num);
}

Imprimindo os elementos da lista

A função para imprimir o conteúdo da lista:

void imprime(node *lista)
{
        node *aux;
        aux = lista->prox;
        while(aux != NULL){
             printf("%5d", aux->conteudo);
             aux = aux->prox;
        }
        printf("\n\n");
}

Exemplo de uso no main

void main(void){
    node *lista;
    int num;
    int num1=11;
    int num2=22;
    int num3=33;
    int num4=44;
    lista = cria_lista();
    inserirInicio(lista, num1);
    inserirInicio(lista, num2);
    inserirInicio(lista, num3);
    inserirInicio(lista, num4);
    imprime(lista);
    num = removerInicio(lista);
    printf("Removido: %d\n", num);
    imprime(lista);
    num = removerFim(lista);
    printf("Removido: %d\n", num);
    imprime(lista);

}

Exercícios

1. Baseado nos exemplos do professor, adaptados da referência , construa funções para inserirFim, removerFim.
2. Implementar uma pilha (LIFO), e suas funções pertinentes, utilizando listas encadeadas.
3. Implementar uma fila (FIFO), e suas funções pertinentes, utilizando listas encadeadas.
4. Implementar uma lista encadeada cujos nós sejam estruturas contendo o cadastro de pessoas, incluindo nome, sexo, ano de nascimento e cidade natal. Incluir funções para incluir no início e no final da lista, assim como remover do início e final da lista.

Exemplo de lista encadeada implementadas em C

Exemplo de lista completa implementada em C

Outras referências

Referências

---

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

---