Na computação, constantemente se faz necessário armazenar uma grande quantidade de dados em estruturas a fim de realizar algum processamento. Em muitas situações, estruturas mais simples como vetor e matriz não são suficientes ou eficientes a ponto de serem uma boa escolha. Assim, precisamos lançar mão de estruturas mais avançadas.

Neste grupo, entram estruturas como pilhas, filas, listas, árvores, entre outras. Hoje apresentaremos como trabalhar com as listas encadeadas. Seu principal benefício é seu crescimento dinâmico, iniciando vazias e crescendo conforme novos elementos são inseridos.

Uma lista encadeada pode ser representada graficamente como na figura a seguir, uma sequencia de elementos onde cada um aponta para o elemento seguinte, até o final, que não aponta para ninguém.

A primeira coisa que precisamos fazer para trabalhar com uma lista encadeada é criar as estruturas necessárias, neste caso, duas estruturas, uma para a lista propriamente dita e outra para os nós da lista.

A estrutura nó é bem simples, possuindo um campo do tipo inteiro chamado valor (poderia ser qualquer tipo, inclusive outro tipo mais complexo) e um ponteiro para um próximo nó.

typedef struct No {
    int valor;
    struct No *proximo;
} No;

A estrutura lista possui um ponteiro para um nó chamado início, o primeiro nó de nossa lista, e um segundo campo inteiro para guardar o tamanho da lista. Aqui acrescentamos um segundo ponteiro para o fim da lista com a finalidade de facilitar uma inserção de novos elementos no final da lista. Ressaltamos que este segundo ponteiro é opcional e sua inclusão ou não vai depender da finalidade da lista que está sendo construída.

typedef struct {
    No *inicio, *fim;
    int tam;
} Lista;

Na sequência, vamos agora trabalhar na inserção de elementos em nossa lista encadeada. A seguir apresentamos um procedimento para inserir um novo elemento no início de nossa lista.

// inserção no início da lista
void inserirInicio(Lista *lista, int valor) {
    No *novo = (No*)malloc(sizeof(No)); // cria um novo nó
    novo->valor = valor;// (*novo).valor = valor

    if(lista->inicio == NULL) { // a lista está vazia
        novo->proximo = NULL;
        lista->inicio = novo;
        lista->fim = novo;
    } else { // a lista não está vazia
        novo->proximo = lista->inicio;
        lista->inicio = novo;
    }
    lista->tam++;
}

Vamos agora escrever outro procedimento, desta vez para inserir um novo elemento no final da lista.

// inserir no final da lista
void inserirFim(Lista *lista, int valor) {
    No *novo = (No*)malloc(sizeof(No)); // cria um novo nó
    novo->valor = valor;
    novo->proximo = NULL;

    if(lista->inicio == NULL) { // lista vazia
        lista->inicio = novo;
        lista->fim = novo;
    } else { // lista não vazia
        lista->fim->proximo = novo;
        lista->fim = novo;
    }
    lista->tam++;
}

Para saber se tudo isso está funcionando realmente, precisamos também imprimir nossa lista na tela.

// imprimir a lista
void imprimir(Lista *lista) {
    No *inicio = lista->inicio;
    printf("Tamanho da lista: %d\n", lista->tam);
    while(inicio != NULL) {
        printf("%d ", inicio->valor);
        inicio = inicio->proximo;
    }
    printf("\n\n");
}

Veja na videoaula a seguir a construção de uma lista encadeada

Podendo inserir elementos no início e no fim da lista, vamos agora remover um determinado elemento.

// remover um elemento da lista
void remover(Lista *lista, int valor) {
    No *inicio = lista->inicio; // ponteiro para o início da lista
    No * noARemover = NULL; // ponteiro para o nó a ser removido

    if(inicio != NULL && lista->inicio->valor == valor) { // remover 1º elemento
        noARemover = lista->inicio;
        lista->inicio = noARemover->proximo;
        if(lista->inicio == NULL)
            lista->fim = NULL;
    } else { // remoção no meio ou no final
        while(inicio != NULL && inicio->proximo != NULL && inicio->proximo->valor != valor) {
            inicio = inicio->proximo;
        }
        if(inicio != NULL && inicio->proximo != NULL) {
            noARemover = inicio->proximo;
            inicio->proximo = noARemover->proximo;
            if(inicio->proximo == NULL) // se o último elemento for removido
                lista->fim = inicio;
        }
    }
    if(noARemover) {
        free(noARemover); // libera a memória do nó
        lista->tam--; // decrementa o tamanho da lista
    }
}

Veja na videoaula a seguir a remoção de um nó da lista

Uma dúvida postada em um dos vídeos queria sabe como dividir uma lista em duas, inserindo os elementos das posições pares em uma lista e os elementos das posições ímpares em outra lista. Para isso, implementamos uma função que remove e retorna o primeiro nó da lista:

// função que remove e retorna o primeiro nó
No* removerPrimeiroNO(Lista *lista) {
    if(lista->inicio != NULL) {
        No *no = lista->inicio;
        lista->inicio = no->proximo;
        lista->tam--;
        if(lista->inicio == NULL)
            lista->fim = NULL;
        return no;
    } else
        return NULL;
}

E um procedimento para fazer a divisão propriamente dita da lista, alternando a inserção em duas listas, uma para os elementos de posição ímpar e outra para os elementos de posição par.

// procedimento que divide uma lista em duas
void dividirLista(Lista *lista, Lista *listaI, Lista *listaP) {
    No *removido;
    while(lista->inicio != NULL) {
        removido = removerPrimeiroNO(lista);
        inserirFim(listaI, removido->valor);
        free(removido);

        removido = removerPrimeiroNO(lista);
        if(removido != NULL) {
            inserirFim(listaP, removido->valor);
            free(removido);
        }
    }
}

Na videoaula a seguir apresento como dividir uma lista encadeada em duas de acordo com a posição do elemento

Agora, vamos então criar um menu em nosso programa principal com opções de inserção, remoção, divisão e impressão da lista.

int main() {
    Lista lista, listaI, listaP; // criação de 3 listas
    int opcao, valor;

    // inicialização das listas
    lista.inicio = NULL;
    lista.fim = NULL;
    lista.tam = 0;

    listaI.inicio = NULL;
    listaI.fim = NULL;
    listaI.tam = 0;

    listaP.inicio = NULL;
    listaP.fim = NULL;
    listaP.tam = 0;

    do { // menu de opções
        printf("1 - Inserir no inicio\n2 - Imprimir\n3 - Inserir no fim\n4 - Remover\n6 - Dividir lista\n5 - Sair\n");
        scanf("%d", &opcao);

        switch(opcao) {
        case 1:
            printf("Digite um valor a ser inserido: ");
            scanf("%d", &valor);
            inserirInicio(&lista, valor);
            break;
        case 2:
            printf("\nLista original:\n");
            imprimir(&lista);
            printf("\nLista impar:\n");
            imprimir(&listaI);
            printf("\nLista par:\n");
            imprimir(&listaP);
            break;
        case 3:
            printf("Digite um valor a ser inserido: ");
            scanf("%d", &valor);
            inserirFim(&lista, valor);
            break;
        case 4:
            printf("Digite um valor a ser removido: ");
            scanf("%d", &valor);
            remover(&lista, valor);
            break;
        case 5:
            printf("Finalizando...\n");
            break;
        case 6:
            dividirLista(&lista, &listaI, &listaP);
            break;
        default:
            printf("Opcao invalida!\n");
        }
    } while(opcao != 5);

    return 0;
}

Se ficou alguma dúvida faça bom uso dos comentários abaixo, farei o possível para ajudar. Um grande abraço e até a próxima. Bons estudos.