Introdução à Lista Ligada (Linguagem C)

Antes de tudo precisamos compreender do que se trata este tipo de implementação mais conhecida como Lista Ligada ou Lista Encadeada, é uma estrutura de dados linear e dinâmica. Podemos guarda apenas o endereço do primeiro elemento, já que, cada um dos elementos (mais conhecidos como nó) apontam para o próximo, tendo o último nó apontado para uma célula nula (representando fim de lista).

Nó 1  >>  Nó 2  >>  Nó 3  >> No n  >>  NULL (nulo)

Vantagem

1. A inserção ou remoção de um determinado nó da lista não implicará na mudança de posição de outros nós.

2. Não precisamos saber qual será o número máximo de nós na lista, portanto não desperdiçaremos espaço na Memória Principal (Memória RAM) do computador.

Desvantagens

1. Se a ligação entre os nós for mal feita poderá acarretar na perda de toda a lista.

2. Para acessar o nó na posição n da lista, deve-se percorrer os n - 1 anteriores.

A partir daqui o leitor deverá ter no mínimo conhecimento sobre a linguagem citada e compreender os conceitos sobre o assunto. Cada um dos códigos abaixo teve suas principais características citadas, no entanto não foram abordados profundamente, o intuito deste guia é auxiliar na compreensão do assunto, portanto esperasse que o leitor já tenha ao menos tentado trabalhar com tal estrutura anteriormente.

Tudo aquilo que vier a seguir não foi copilado, portanto pode conter erros, caso encontre-os apenas deixe um recado nos comentários que procurarei corrigir quando ler.

Estrutura (struct)

struct no
{
    int numero;
    struct no *prox;
};

O campo “int numero;” representa um valor do tipo inteiro, poderíamos sem problemas adicionar outros campos à estrutura, como por exemplo um “char letra;” na linha seguinte. O trecho “struct no *prox;” será o ponteiro para o próximo nó da lista.

Inserção (ordem crescente)

no *inserir(struct no *raiz, int numero)
{
    struct no *novo;
    novo = (struct no*)malloc(sizeof(struct no));
    novo->numero = numero;
    if(raiz == NULL) { 
        raiz = novo;
        novo->prox = NULL;
    } else {
        if(raiz->numero > numero) {
            novo->prox = raiz;
            return (novo);
        } else {
            struct no *aux_antes = raiz, *aux_depois = raiz;
            while(aux_depois->prox != NULL) {
                aux_depois = aux_depois->prox;
                if(aux_depois->numero > numero) {
                    aux_antes->prox = novo;
                    novo->prox = aux_depois;
                    return (raiz);
                }
                aux_antes = aux_antes->prox;
            }
            aux_depois->prox = novo;
            novo->prox = NULL;  
        }
    }
    return (raiz);
}

A função anterior irá inserir um novo nó no inicio se lista for nula ou o seu número for menor que o primeiro valor já existente na lista. Caso contrário será necessário procurar pelo local mais adequado, para isso percorreremos a lista através de um “while”. Portanto o novo elemento será adicionado na posição encontrada ou no final caso não haja valores maiores que o novo nó, retornará o nó inicial da lista.

Remoção (primeira ocorrência de um número)

no *remover(struct no *raiz, int numero)
{
    if(raiz == NULL){
        printf("A lista ja esta vazia.\n");
    } else {
        struct no *aux = raiz;
        if(aux->numero == numero) {
            aux = aux->prox;
            free(raiz);
        } else {
            struct no *aux_antes = raiz, *aux_depois = raiz;
            while(aux->prox != NULL) {
                aux = aux->prox;
                aux_depois = aux->prox;
                if(aux->numero == numero) {
                    aux_antes->prox = aux_depois;
                    free(aux);
                    return (raiz);
                }
            }
        }
    }
    return (raiz);
}

A função anterior irá remover um nó da lista, sendo que este seja a primeira ocorrência de valor informado. Percorrerá a lista desde que não seja nula, retornará o nó inicial da lista.

Impressão (imprimir todos os nós)

void imprimir(struct no *raiz)
{
    int contador = 0;
    if(raiz == NULL){
        printf("A lista esta vazia.\n");
    } else {
        struct no *aux = raiz;
        while(aux->prox != NULL) {
            contador++;
            printf("Valor do no %d: %d\n", contador, aux->numero);
        }
    }
    printf("Numero de nos: %d\n", contador);
}

A função anterior irá imprimir todos os valores da lista informando a qual nó se refere, ao terminar será impresso o número total de elementos. Percorrerá a lista desde que não seja nula.

Procurar por um número

int procurar(struct no *raiz, int numero)
{
    if(raiz == NULL){
        printf("A lista esta vazia.\n");
    } else {
        int posicao = 0;
        struct no *aux = raiz;
        while(aux->prox != NULL) {
            posicao++;
            if(aux->numero == numero) {
                printf("Valor encontrado em: %d\n", posicao);
                return 1;
            }
        }
    }
    printf("Valor nao encontrado.");
    return 0;
}

A função anterior irá procurar por um determinado valor na lista, caso encontre imprimirá a sua posição. Percorrerá a lista desde que não seja nula, retornará 0 caso não encontre e 1 caso tenha encontrado.

Alguns trechos deste artigo foram baseados na leitura desta página.