Programar em C/Listas encadeadas

Origem: Wikilivros, livros abertos por um mundo aberto.

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.

Tabela de conteúdo

[editar] Primitivas

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

  • Colocar o índice sobre o primeiro elemento da lista.
  • Colocar o índice sobre o ultimo 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 ultimo elemento  : Retorna verdadeiro se o elemento atual é o ultimo, se não falso.
  • Verificar o numero de elementos da lista : Retorna o numero de elementos da lista.
  • Adicionar um elemento no inicio : Adicionar um elemento antes do primeiro elemento da lista .
  • Adicionar um elemento no fim : Adicionar um elemento depois do ultimo 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 . Tem mais ?

[editar] Lista encadeada linear

Cada nó ou elemento de uma lista encadeada irá possuir guardar 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;
};

[editar] 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;
}

[editar] 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.

[editar] 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 */
    if((p_Novo = (struct No *) malloc(sizeof(struct No))) == NULL ){
        puts( "Falta Memoria\n");  return -1 ;
      }
 
    p_Novo->p_dados = p_String;
 
    if(*p_Raiz == NULL){
        *p_Raiz = p_Novo;
        p_Novo->p_prox = NULL;
    }else{
        p_Novo->p_prox = *p_Raiz;
        *p_Raiz = p_Novo;
    }
}

[editar] Inserção no fim

int inserir_No_Fim(struct No **p_Raiz, char *p_String){
    struct No *p_Novo;
    if(( p_Novo = (struct No *) malloc(sizeof(struct No))) == NULL ){
        puts( "Falta Memoria\n");  return -1 ;
      }
    p_Novo->p_dados = p_String;
    p_Novo->p_prox = NULL;
 
    if(*p_Raiz == NULL)
        *p_Raiz = p_Novo;
    else{
        struct No *e_atual;  /*@ Elemento atual*/
        e_atual = *p_Raiz;   /*@ Primeiro elemento*/
 
        while(e_atual->p_prox != NULL){
            e_atual = e_atual->p_prox;
        }
        e_atual->p_prox = p_Novo;
    }
}

[editar] 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.

[editar] 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);
    }
}

[editar] 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);
    }
}

[editar] Exibição

[editar] 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;
            }
            p_Atual_Corredor = p_Atual_Corredor->p_prox;
        }
        printf(" <- %s", p_Atual_Fim->p_dados);
    }
}

[editar] 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;
        }
    }
}
Obtido em "http://pt.wikibooks.org/wiki/Programar_em_C/Listas_encadeadas"