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.

Primitivas

Não existe nenhuma normalização quanto as primitivas usadas para a manipulação de uma lista.
Abaixo você pode ver uma lista com algumas delas .

• Colocar o índice sobre o primeiro elemento da lista.
• Colocar o índice sobre o último elemento da lista .
• Colocar o índice sobre o elemento que segue o elemento atual .
• Colocar o índice sobre o elemento que precede o elemento atual .
• Verificar se a lista está vazia : Se a lista estiver vazia retorna verdadeiro, se não, falso.
• Verificar se é o primeiro elemento : Retorna verdadeiro se o elemento atual é o primeiro, se não, falso.
• Verificar se é o último elemento  : Retorna verdadeiro se o elemento atual é o último, se não, falso.
• Verificar o número de elementos da lista : Retorna o número de elementos da lista.
• Adicionar um elemento no início : Adicionar um elemento antes do primeiro elemento da lista .
• Adicionar um elemento no fim : Adicionar um elemento depois do último elemento da lista .
• Inserção : Inserir um elemento antes do elemento atual .
• Troca : Trocar o elemento atual .
• Remoção : Remover o elemento atual .
• Listar todos os elementos da lista .

Lista encadeada linear

Cada nó ou elemento de uma lista encadeada irá possuir o valor do nó e o endereço do próximo nó. Em uma lista encadeada linear o ultimo elemento aponta para NULL .

struct No{
    char *p_dados;
    struct No *p_prox;
};

Iniciar uma lista

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

void criar_Lista(struct No **p_Raiz){
    *p_Raiz = NULL;
}

Inserção

Existem 3 tipos de inserção em uma lista, pode-se inserir no começo, no final ou entre dois elementos da lista.

Inserção no início

int inserir_No_Inicio (struct No **p_Raiz, char *p_String){
    struct No *p_Novo;
         /** Alocação dinâmica da memoria */
    p_Novo = (struct No *) malloc(sizeof(struct No));  
    if( p_Novo == NULL ){
        printf( "Falta Memoria\n");
        return -1 ;
    }
     
    p_Novo->p_dados = p_String;
 
    p_Novo->p_prox = *p_Raiz;
    *p_Raiz = p_Novo;
}

Inserção no fim

int inserir_No_Fim(struct No **p_Raiz, char *p_String){
    struct No *p_Novo; 
    struct No *e_atual;

    p_Novo = (struct No *) malloc(sizeof(struct No));
    if(p_Novo == NULL){
        printf("Falta Memoria\n");
        return -1 ;
    }
    p_Novo->p_dados = p_String;
    p_Novo->p_prox = NULL;
    
    if(*p_Raiz == NULL)  //Lista vazia
        *p_Raiz = p_Novo;
    else{
        e_atual = *p_Raiz;   /*@ Primeiro elemento*/
        
        while(e_atual->p_prox != NULL){
            e_atual = e_atual->p_prox;
        }
        e_atual->p_prox = p_Novo;
    }
}

Remoção

Assim como na inserção também existem 3 tipos de remoção, no início, no fim ou entre dois elementos da lista.

Remoção no início

void remover_No_Inicio(struct No **p_Raiz){
    if(*p_Raiz == NULL) printf("\nA lista ja esta vazia\n");
    else{
        struct No *p_atual;
        p_atual = *p_Raiz;
         
        *p_Raiz = (*p_Raiz)->p_prox;
        free(p_atual);
    }
}

Remoção no fim

void remover_No_Fim(struct No **p_Raiz){
    if(*p_Raiz == NULL) printf("\nA lista ja esta vazia");
    else{
        struct No *p_atual, *p_anterior ;
        p_atual = *p_Raiz;
        while(p_atual->p_prox != NULL){
            p_anterior = p_atual ;
            p_atual    = p_atual->p_prox;
        }
        p_anterior->p_prox = NULL;
        free(p_atual);
    }
}

Exibição

Do fim para a raiz

void mostrar_Do_Fim_Para_Raiz(struct No *p_Raiz){
    if(p_Raiz == NULL) printf("\nLista vazia");
    else{
        struct No *p_Atual_Corredor, *p_Atual_Fim;
        p_Atual_Corredor = p_Raiz;
        p_Atual_Fim = p_Raiz;
        while(p_Atual_Fim->p_prox != NULL){ //ir para o ultimo elemento
            p_Atual_Fim = p_Atual_Fim->p_prox;
        }
        while(p_Atual_Corredor != p_Atual_Fim){
            if(p_Atual_Corredor->p_prox == p_Atual_Fim){
                printf(" <- %s", p_Atual_Fim->p_dados);
                p_Atual_Fim = p_Atual_Corredor;
                p_Atual_Corredor = p_Raiz;
            }
            else p_Atual_Corredor = p_Atual_Corredor->p_prox;
        }
        printf(" <- %s", p_Atual_Fim->p_dados);
    }
}

Da raiz para o fim

void mostrar_Da_Raiz_Para_Fim(struct No *p_Raiz){
    if(p_Raiz == NULL) printf("\nLista vazia");
    else{
        struct No *p_atual;
        p_atual = *p_Raiz;
        while(p_atual != NULL){
            printf("%s", p_atual->p_dados);
            p_atual = p_atual->p_prox;
                 
        }
    }
}