Deleting Node from Circular Doubly Linked List

Question

I've written code to insert elements into a circular doubly linked list and to display these elements. I'm supposed to also be able to delete the tail node from the the list, as well as search the list for a specific element.

This is my working code for add and print:

void Circular_DLList::add_to_tail(int a)
{
    DLLNode *temp = new DLLNode;
    temp->info = a;
    if (is_empty()) {   
        tail = temp;
        temp->next = tail;
        temp->prev = tail;
    }
    else {
        temp->next = tail->next;
        temp->prev = tail;
        tail = temp;
        tail->prev->next = temp;
    }
}

void Circular_DLList::print_list()
{
    DLLNode *ptr;
    ptr = tail->next;
    do {
        cout<< ptr->info << endl;
        ptr = ptr->next;
    }
    while(ptr != tail->next);
}

No matter what I write for the delete_from_tail function, it causes a segmentation fault:11. This is my attempt for the function (which throws the error).

int Circular_DLList::delete_from_tail()
{
    int a = tail->info;
    if(tail == tail->next) {
        delete tail;
        tail = NULL;
    }
    else {
        tail = tail->prev;
        delete tail->next;
        tail->next = NULL;
    }
    return a;
}

Any advice as to how to fix this would be fantastic. I've tried debugging but I can't seem to figure out the issue or where exactly it's even related to. Thanks

Answer 1

The issue is pretty obvious if you look at it closely. Your delete function is breaking the circular chain of the Link list. How so? See your delete function below:

int Circular_DLList::delete_from_tail()
{
    int a = tail->info;
    DLLNode *temp;

    if(tail == tail->next) {
        delete tail;
        tail = NULL;
    }
    else {
        tail = tail->prev;
        delete tail->next;
        tail->next = NULL;
    }
    return a;
}

In the else-condition you are setting tail->next = NULL which is actually the bug and hence breaks the chain. So when print is called it assumes that circular chain is intact and hence accidently tries to access a NULL pointer which in turn leads to segmentation fault.

The Fix is very simple see the below code:

int Circular_DLList::delete_from_tail()
{
    int a = tail->info;
    if(tail == tail->next) {
        delete tail;
        tail = NULL;
    }
    else {
        temp = tail;
        tail = tail->prev;
        tail->next = temp->next;        // To maintain the circular chain
        tail->next->previous = tail;    // Since this element's previous also point to the node about to be deleted
        delete temp;
        temp = NULL;
    }
    return a;
}