Programar em C/Listas encadeadas

Listas encadeadas são estruturas de dados lineares e dinâmicas, a grande vantagem que elas possuem em relação ao uso de vetor é o fato de terem tamanho máximo relativamente infinito (o tamanho máximo é o da memória do computador), ao mesmo tempo que podem ter o tamanho mínimo de 1 elemento evitando o desperdício de memória.

Struct

Cada nó de uma lista encadeada irá possuir guardar o valor do nó e o endereço do próximo nó.

struct No{
    char *pString;
    struct No *pProx;
};

Iniciar uma lista

A função abaixo demonstra como iniciar uma lista criando o espaço da raiz na memória.

void criarLista(struct No **pRaiz){
    *pRaiz = NULL;
}

Inserção

Existem 2 tipos de inserção numa lista, pode-se inserir no começo ou no final da lista.

Inserção no início

void inserirNoInicio(struct No **pRaiz, char *pString){
    struct No *pNovo;
    pNovo = (struct No *) malloc(sizeof(struct No));
    pNovo->pString = pString;
   
    if(*pRaiz == NULL){
        *pRaiz = pNovo;
        pNovo->pProx = NULL;
    }else{
        pNovo->pProx = *pRaiz;
        *pRaiz = pNovo;
    }
}

Inserção no fim

void inserirNoFim(struct No **pRaiz, char *pString){
    struct No *pNovo;
    pNovo = (struct No *) malloc(sizeof(struct No));
    pNovo->pString = pString;
    pNovo->pProx = NULL;
    
    if(*pRaiz == NULL){
        *pRaiz = pNovo;
    }else{
        struct No *pAux;
        pAux = *pRaiz;
        
        while(pAux->pProx != NULL){
            pAux = pAux->pProx;
        }
        pAux->pProx = pNovo;
    }
}

Remoção

Assim como na inserção também existem 2 tipos de remoção, no início e no fim da lista.

Remoção no início

void removerNoInicio(struct No **pRaiz){
    if(*pRaiz == NULL) printf("\nA lista ja esta vazia");
    else{
        struct No *pAux;
        pAux = *pRaiz;
         
        *pRaiz = (*pRaiz)->pProx;
        free(pAux);
    }
}

Remoção no fim

void removerNoFim(struct No **pRaiz){
    if(*pRaiz == NULL) printf("\nA lista ja esta vazia");
    else{
        struct No *pAuxFrente, *pAuxTras;
        pAuxFrente = *pRaiz;
        while(pAuxFrente->pProx != NULL){
            pAuxTras = pAuxFrente;
            pAuxFrente = pAuxFrente->pProx;
        }
        pAuxTras->pProx = NULL;
        free(pAuxFrente);
    }
}