30 de nov de 2012

Lista Duplamente Encadeada em C.

A utilização de encadeamento duplo em uma lista facilita operações onde é necessário percorrer a lista nas duas direções, porém pagamos um preço por isso, pois ela requer mais memória e realiza mais operações.

Vamos ver como fica a implementação das operações básicas para esse tipo de lista...

Para inicio de conversa nossa estrutura vai sofrer uma alteração pois agora teremos um ponteiro para o elemento anterior e um ponteiro para o elemento posterior, fincando assim:

struct no {
    struct no *ant;
    int info;
    struct no *prox;
};

typedef struct no *Lista;

para inserir um elemento no inicio da lista devemos alocar memória para ele e posteriormente devemos atribuir o valor "NULL" ao campo "ant" e ao campo "prox" passamos o endereço do primeiro elemento da lista, assim estaremos incluindo um novo elemento ao inicio da lista.

int insere_elemento(Lista *l, int elem)
{
    //alocando espaco para o novo elemento.
    Lista no;
    no = (Lista)malloc(sizeof(struct no));
    if(no == NULL)
        return 0;

    //atribuindo valores aos campos do novo elemento.
    no->info = elem;
    no->ant = NULL;
    no->prox = (*l);

    //caso a lista nao seja vazia o campo "ant" do primeiro elemento recebe o novo elemento.
    if((*l) != NULL)
        (*l)->ant=no;

    //a nova lista inicia pelo elemento inserido.
    (*l) = no;

    return 1;
}

Para remover um elemento qualquer contido na lista deveremos verificar primeiramente se a mesma está vazia pois neste caso haveria um erro, posteriormente procuramos onde esta o elemento e o removemos:

int remove_elemento(Lista *l, int elem)
{
    Lista aux;
    
    //verificando se a lista esta vazia.
    if(lista_vazia(*l))
        return 0;

    //caso o elemento esteja na primeira posicao...
    if((*l)->info == elem)
    {
        if((*l)->prox == NULL)//se nao ouver mais elementos na lista a mesma fica vazia.
        {
            free(*l);
            (*l) = NULL;
        }
        else//caso haja outros elemento na lista o o segundo elemento passa a ser o primeiro.
        {
            (*l) = (*l)->prox;
            free((*l)->ant);
            (*l)->ant = NULL;
        }
    }
    else//caso o elemento nao esteja na primeira posicao...
    {
        aux = *l;
        //procurando elemento...
        while(aux!= NULL && aux->info != elem)
            aux = aux->prox;
        //se chegarmos ao fim da lista significa que o elemento procurado nao consta na lista.
        if(aux == NULL)
            return 0;
        
        if(aux->prox == NULL)//se for o ultimo elemento da lista...
        {
            aux->ant->prox = NULL;//atribui "NULL" ao campo "ant" do penultimo elemento.
            free(aux);//libera o ultimo elemento.

        }
        else//se o elemento estiver no meio da lista...
        {
            //o campo "prox" do anterior ao elemento recebe o proximo do elemento.
            aux->ant->prox = aux->prox;
            //o campo "ant" do proximo elemento recebe o elemento anterior.
            aux->prox->ant = aux->ant;
            free(aux);//libera o elemento.
        }
    }
    return 1;
}

A partir destas operações básicas é possível ter uma ideia de como a lista duplamente encadeada é poderosa, poderíamos também implementar funções para inserir elemento em uma posição especifica, remover de uma posição especifica, liberar lista entre outras, mais estas eu deixo como desafio para você...

Qual dúvida, crítica construtiva ou comentário podem ser deixados ai nos comentários que serão respondidos.

Veja também...
Lista com alocação estática e acesso sequencial em C.
Lista com alocação dinâmica encadeada em C.
Lista utilizando nó-cabeçalho em C.
Lista com encadeamento circular em C.

Continua:
Pilha em C.

Um comentário:

  1. Há um erro na função inserir, do jeito que está o ponteiro anterior aponta pra null e não pro ultimo elemento da lista.

    ResponderExcluir