Dando continuidade ao estudo da estrutura lista encadeada, vamos nesta aula aprender como inserir no meio de uma Lista Simplesmente Encadeada.

A ideia básica aqui é inserir um novo elemento depois de um determinado valor, por exemplo, inserir o 100 depois do 320. Perceba que agora temos que trabalhar com dois valores, o novo valor a ser inserido e um valor de referência que chamarei aqui de anterior.

Como já vimos nas etapas anteriores, quando a lista estiver vazia teremos uma inserção no início. Neste caso não importa qual o valor anterior, pois não existem elementos na lista. Assim, o próximo do nosso novo nó será nulo e ele se torna o primeiro nó de nossa lista.

        /*
           é o primeiro? Ou, a lista está vazia?
        */
        if(*lista == NULL){
            novo->proximo = NULL;
            *lista = novo;
        }
        else{
            // inserção no meio ou no final
        }

Contudo, na maioria das vezes teremos inserções no meio ou no final da lista. Neste caso precisamos percorrer nossa lista procurando pelo elemento anterior. Se o elemento anterior não for encontrado, então teremos uma inserção no final da lista. Porém, ao encontrar o elemento anterior, encontramos o ponto de inserção do novo nó. O próximo do novo nó irá apontar para o próximo do anterior e este irá apontar para o novo nó.

        /*
           é o primeiro? Ou, a lista está vazia?
        */
        if(*lista == NULL){
            novo->proximo = NULL;
            *lista = novo;
        }
        else{
            // inserção no meio ou no final
            aux = *lista;
            while(aux->valor != ant && aux->proximo)
                aux = aux->proximo;
            novo->proximo = aux->proximo;
            aux->proximo = novo;
        }

Código completo em C para a inserção no meio da lista

/*
     procedimento para inserir no meio da lista
*/
void inserir_no_meio(No **lista, int num, int ant){
    No *aux, *novo = malloc(sizeof(No));

    if(novo){
        novo->valor = num;
        // é o primeiro?
        if(*lista == NULL){
            novo->proximo = NULL;
            *lista = novo;
        }
        else{
            aux = *lista;
            while(aux->valor != ant && aux->proximo)
                aux = aux->proximo;
            novo->proximo = aux->proximo;
            aux->proximo = novo;
        }
    }
    else
        printf("Erro ao alocar memoria!\n");
}