Dando continuidade ao estudo da estrutura de dados lista encadeada, vamos aprender nesta aula como inserir de forma ordenada na estrutura de dados lista encadeada. Nesta aula usaremos apenas a estrutura Nó. Na aula seguinte usaremos a estrutura Lista.

O processo para inserir de forma ordenada é composto de várias etapas mas nada muito diferente do que já estudamos até aqui. Após a criação do novo nó, o primeiro passo é verificar se a lista está vazia, neste caso teremos uma inserção no início.

        /*
            a lista está vazia?
        */
        if(*lista == NULL){
            novo->proximo = NULL;
            *lista = novo;
        }
        else{
            // ...
        }

Se a lista não estiver vazia, é possível que o novo elemento a ser inserido seja o menor, então precisamos verificar também esta possibilidade, comparando o elemento a ser inserido com o primeiro elemento da lista.

        /*
            a lista está vazia?
        */
        if(*lista == NULL){
            novo->proximo = NULL;
            *lista = novo;
        }
        else if(novo->valor < (*lista)->valor){ // é menor que o primeiro elemento da lista?
            novo->proximo = *lista;
            *lista = novo;
        }
        else{
            // ...
        }

Por fim, se o novo elemento não é menor que o primeiro elemento da lista, então teremos uma inserção no meio ou no final, neste caso precisamos percorrer a lista procurando pela posição correta para inserir o elemento.

        /*
            a lista está vazia?
        */
        if(*lista == NULL){
            novo->proximo = NULL;
            *lista = novo;
        }
        else if(novo->valor < (*lista)->valor){ // é menor que o primeiro elemento da lista?
            novo->proximo = *lista;
            *lista = novo;
        }
        else{
            aux = *lista;
            while(aux->proximo && novo->valor > aux->proximo->valor)
                aux = aux->proximo;
            novo->proximo = aux->proximo;
            aux->proximo = novo;
        }

A seguir temos o procedimento completo para realizar a inserção de forma ordenada em nossa lista simplesmente encadeada.

/*
      Procedimento para inserir ordenado
*/
void inserir_ordenado(No **lista, int num){
    No *aux, *novo = malloc(sizeof(No));

    if(novo){
        novo->valor = num;
        
        if(*lista == NULL){ // a lista está vazia?
            novo->proximo = NULL;
            *lista = novo;
        }
        else if(novo->valor < (*lista)->valor){ // é o menor?
            novo->proximo = *lista;
            *lista = novo;
        }
        else{ // inserção no meio ou no final da lista
            aux = *lista;
            while(aux->proximo && novo->valor > aux->proximo->valor)
                aux = aux->proximo;
            novo->proximo = aux->proximo;
            aux->proximo = novo;
        }
    }
    else
        printf("Erro ao alocar memoria!\n");
}

Código de exemplo completo em C para a estrutura Lista Encadeada

/*
            Código escrito por Wagner Gaspar
            Agosto de 2021

            Aula 248: Lista Simplesmente Encadeada
            Como inserir de forma ordenada SEM a estrutura lista?
*/

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

// procedimento para inserir no início
void inserir_no_inicio(No **lista, int num){
    No *novo = malloc(sizeof(No));

    if(novo){
        novo->valor = num;
        novo->proximo = *lista;
        *lista = novo;
    }
    else
        printf("Erro ao alocar memoria!\n");
}

// procedimento para inserir no fim
void inserir_no_fim(No **lista, int num){
    No *aux, *novo = malloc(sizeof(No));

    if(novo){
        novo->valor = num;
        novo->proximo = NULL;

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

// procedimento para inserir no meio
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");
}

void inserir_ordenado(No **lista, int num){
    No *aux, *novo = malloc(sizeof(No));

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

void imprimir(No *no){
    printf("\n\tLista: ");
    while(no){
        printf("%d ", no->valor);
        no = no->proximo;
    }
    printf("\n\n");
}

int main(){

    int opcao, valor, anterior;
    No *lista = NULL;

    do{
        printf("\n\t0 - Sair\n\t1 - InserirI\n\t2 - inserirF\n\t3 - InserirM\n\t4 - InserirO\n\t5 - Imprimir\n");
        scanf("%d", &opcao);

        switch(opcao){
        case 1:
            printf("Digite um valor: ");
            scanf("%d", &valor);
            inserir_no_inicio(&lista, valor);
            break;
        case 2:
            printf("Digite um valor: ");
            scanf("%d", &valor);
            inserir_no_fim(&lista, valor);
            break;
        case 3:
            printf("Digite um valor e o valor de referencia: ");
            scanf("%d%d", &valor, &anterior);
            inserir_no_meio(&lista, valor, anterior);
            break;
        case 4:
            printf("Digite um valor: ");
            scanf("%d", &valor);
            inserir_ordenado(&lista, valor);
            break;
        case 5:
            imprimir(lista);
            break;
        default:
            if(opcao != 0)
                printf("Opcao invalida!\n");
        }

    }while(opcao != 0);

    return 0;
}