Double chained list printing in reverse order

Question

Good morning, this is my first post here at Stack Overflow. I was trying to get a double-chained list printed in reverse order. However, after going through this list in reverse, it produced the result unexpectedly. My code is printing more than necessary. Follow the attached print and source code.

I’m counting on your help!

#include <stdio.h>
#include <stdlib.h>

//Exercício: Inserir  células na lista duplamente encadeada e em seguida imprimí-las na ordem inversa


typedef struct cel{

    struct cel* ant;
    int conteudo;
    struct cel* prox;

}celula;


celula* criaLista(){
    return NULL;
}

celula* insereInicioLista(celula* inicio, int valor){

    celula* novo = (celula*)malloc(sizeof(celula));

    //Inicialmente os ponteiros ini e fim apontam para NULL
    celula* ini = inicio;
    celula* fim = inicio;


    if(novo == NULL){
        printf("Memoria insuficiente\n");
        exit(1);

    } else if(verificaListaVazia(inicio)){

        novo->conteudo = valor;
        novo->prox = fim;
        novo->ant = ini;

        fim = novo;
        ini = novo;

        return ini;

    } else {

        novo->conteudo = valor;
        novo->prox = fim;
        fim->ant = novo;
        ini = novo;

        return ini;
    }
}

int verificaListaVazia(celula* lista){
    return lista == NULL;
}


void imprimeLista(celula* lista){

    celula* p = lista;

    for(; p != NULL; p = p->prox){
        printf("%d-> ", p->conteudo);
//      printf("valor: %d\n", p->conteudo);
//      printf("Endereco de p: %p\n", p);
//      printf("Endereco do prox de p: %p\n", p->prox);
//      printf("Endereco anterior a p: %p\n\n", p->ant);
    }

    printf("\n\n");
}

void imprimeListaNaOrdemInversa(celula* inicio){

    celula* p = inicio; //Ponteiro que aponta para o início da lista

    while(p->prox != NULL){
        p = p->prox;
    }

    //Ao final, p passa a apontar para o último nó
    celula* final = p;

    for(; final != NULL; final = final->ant){
        printf(" <- %d", final->conteudo);
    }

    printf("\n\n");
}

int main(int argc, char *argv[]) {

    celula* lista = (celula*)malloc(sizeof(celula));

    if(lista == NULL){
        printf("Memoria insuficiente\n");
        exit(1);

    } else {

        lista = criaLista();

        lista = insereInicioLista(lista, 10);
        lista = insereInicioLista(lista, 20);
        lista = insereInicioLista(lista, 30);
        lista = insereInicioLista(lista, 40);
        lista = insereInicioLista(lista, 50);

        printf("LISTA DUPLAMENTE ENCADEADA\n");
        imprimeLista(lista);

        printf("LISTA DUPLAMENTE ENCADEADA INVERSA\n");
        imprimeListaNaOrdemInversa(lista);
    }

    return 0;
}

Answer 1

The problem is only in function insereInicioLista that has some incorrect things.

The pointer fim it is not necessary since it is inserting itself at the beginning always, and if it were necessary to go through the list to the end to point to the right node.

The main point that makes it fail is not to be assigned the novo->ant in the else, here:

else {

    novo->conteudo = valor;
    novo->prox = fim;
    fim->ant = novo;
    ini = novo;

    return ini;
}

What makes it indefinite, and the navigation goes through the memory outside, accessing random addresses. This should be assigned with NULL, as it was in the if.

There are also some simplifications in the code that can be done, such as in returns:

    ini = novo;

    return ini;

} else {

    ...
    ini = novo;

    return ini;
}

Here we see that the value to be returned is always the novo, then it will be easier to return directly novo and outside the if because it’s the same in both cases.

Correcting and simplifying the function insereInicioLista gets like this:

celula* insereInicioLista(celula* inicio, int valor){

    celula* novo = (celula*)malloc(sizeof(celula));

    //testa logo se conseguiu obter memoria, antes de fazer mais coisas como tinha antes
    if(novo == NULL){ 
        printf("Memoria insuficiente\n");
        exit(1);
    }

    //a construção dos ponteiros do novo não depende se a lista está vazia, logo 
    //pode ser feita fora do if
    novo->conteudo = valor; 
    novo->prox = inicio;
    novo->ant = NULL;

    if (!verificaListaVazia(inicio)){ //ou if (inicio != NULL) que era mais simples
       inicio->ant = novo; //se existe lista colocar o ant do primeiro a apontar para o novo
    }

    return novo;
}

I also take this opportunity to mention that the function creates:

celula* criaLista(){
    return NULL;
}

It doesn’t make much sense, because it always comes back NULL. It would be simpler and clear to change in your main the initialization to:

lista = NULL;