Error Segmentation fault (core dumped) Circular double list

Question

I’ve been trying to make a double circular list for hours. I’ve tried to fix all the bugs but got a 'Segmentation fault (core dumped) error that I have no idea what it is. Can someone please help me?

Below follows my code:

//Arquivo circDuplList.c
#include <stdio.h>
#include <stdlib.h>
#include "cdlist.h"


struct cdlst{
int info;
cdLst* ant;
cdLst* prox;
};

/*Create an empty circ dupl list*/
cdLst* create_empty(void)
{
    return NULL;
}

/*Insert a node to the front of the circular list*/
cdLst* insert_front(cdLst* cdl, int info)
{
cdLst* p = (cdLst*)malloc(sizeof(cdLst));
p->info = info;
p->prox = cdl;
if(cdl != NULL){
    cdLst* aux = cdl;
    while(aux->prox != cdl){
        aux = aux->prox;
    }
    cdl->ant = p;
    p->ant = aux;
    aux->prox = p;
}else{
    p->prox = p->ant;
    p->ant = p->prox;
}
cdl = p;
return cdl;
}

/*Insert a node to the end of the circular list*/
cdLst* insert_end(cdLst* cdl, int info)
{
    cdLst* n = (cdLst*) malloc(sizeof(cdLst));
    n->info = info;
    if(cdl != NULL){
        cdLst* p = cdl;
        while(p->prox != NULL){
            p = p->prox;
        }
        p->prox = n;
        n->prox = cdl;
        n->ant = p;
        cdl->ant = n;
    }
    else{
        n->ant = n->prox = NULL;
        return n;
    }
    return cdl;
}

/*Remove a node from the list*/
void retira(cdLst* cdl,int info)
{
    if(cdl == NULL){
        printf("The list is empty");
        exit(1);
    }
    cdLst* p = cdl;
    while(p->prox != cdl && p->info != info)
        p = p->prox;
    if(p->prox == cdl && p->info != info){
        exit(1);
    }
    if(p == cdl){
        cdl = cdl->prox;
        cdl->ant = p->ant;
    }
    p->ant->prox = p->prox;
    free(p);
}

/*Print the list*/
void cdl_print(cdLst* cdl)
{
    cdLst* p = NULL;
    printf("\n%d",p->info);
    p = p->prox;
    while(p != cdl)
        printf("\n%d",p->info);
}

/*Print the list in the reverse order*/
//void cdl_print_rev(cdLst* cdl);

/*Verify if the list is empty*/
int empty(cdLst* cdl)
{
    return cdl == NULL;
}

/*Free memory of the list*/
//void cdl_free();

//Arquivo main.c
#include <stdio.h>
#include <stdlib.h>
#include "cdlist.h"

int main(void){
    cdLst* l = create_empty();
    int v = empty(l);
    printf("%d",v);
    l = insert_front(l,3);
    v = empty(l);
    printf("%d",v);
    l = insert_front(l,2);
    l = insert_front(l,3);
    l = insert_front(l,8);
    l = insert_front(l,65);
    l = insert_front(l,3);
    cdl_print(l);
}

Answer 1

If the list is circular, then you don’t need to scroll to the end of it on insert_front because it means that her "end" is just before the beginning. Therefore, in the insert_front, in the case of cdl not to be NULL, you can do just that:

    p->prox = cdl;
    p->ant = cdl->ant;
    p->ant->prox = p;
    p->prox->ant = p;

That is, connects the new element the cdl and the element preceding cdl and links these two elements to p.

Similarly, if the list is circular then it makes no sense to have either the insert_front to insert at the beginning how much the insert_end to insert at the end. The beginning and the end of the list are exactly the same places. So you only need one of them.

When trying to insert the first node, cdl is NULL. The insert_front does that:

cdLst* insert_front(cdLst* cdl, int info)
{
cdLst* p = (cdLst*)malloc(sizeof(cdLst));
p->info = info;
p->prox = cdl;
if(cdl != NULL){
    // ...
}else{
    p->prox = p->ant;
    p->ant = p->prox;
}

Note the order of how the pointers of p will be defined:

p->prox = cdl;
p->prox = p->ant;
p->ant = p->prox;

The second line (p->prox = p->ant;) will copy trash from p->ant to the p->prox, overwriting the cdl. At that time, the p->ant is junk because it has not been set anywhere. The third line will not produce any effect.

What you need in case the cdl was NULL that’s what:

p->prox = p;
p->ant = p;

The reason is that the list is circular, so when it starts with a single element, that very element has itself as next and previous.

Still in the insert_front, you have it:

return cdl;

The first time, cdl is NULL, it will create the first node of the list and return NULL. Return NULL means that you create a node and lose it right away. That way, you can never create anything! What you wanted to return is p.

In function cdl_print, This can’t work for obvious reasons:

cdLst* p = NULL;
printf("\n%d",p->info);

Still in the cdl_print, see this code:

p = p->prox;
while(p != cdl)
    printf("\n%d",p->info);

Note that as p is never changed within the while, so this is an infinite loop.

I didn’t check the function retira and disregarded the insert_end. I also removed the create_empty and the empty because I consider them unnecessary, since create_empty just returns NULL always doing nothing and empty just check if something is NULL or not and you don’t need a function to do this.

Your code went like this:

//Arquivo circDuplList.c
#include <stdio.h>
#include <stdlib.h>

typedef struct cdLst{
    int info;
    struct cdLst* ant;
    struct cdLst* prox;
} cdLst;

/*Insert a node to the front of the circular list*/
cdLst* insert_front(cdLst* cdl, int info) {
    cdLst* p = (cdLst*)malloc(sizeof(cdLst));
    p->info = info;
    if (cdl != NULL) {
        p->prox = cdl;
        p->ant = cdl->ant;
        p->ant->prox = p;
        p->prox->ant = p;
    } else {
        p->prox = p;
        p->ant = p;
    }
    cdl = p;
    return p;
}

/*Print the list*/
void cdl_print(cdLst* cdl) {
    printf("\n%d",cdl->info);
    for (cdLst *p = cdl->prox; p != cdl; p = p->prox) {
        printf("\n%d",p->info);
    }
}

int main(void){
    cdLst* l = NULL;
    l = insert_front(l,3);
    l = insert_front(l,2);
    l = insert_front(l,3);
    l = insert_front(l,8);
    l = insert_front(l,65);
    l = insert_front(l,3);
    cdl_print(l);
}

Here’s the way out:

3
65
8
3
2
3

See here working on ideone.