Getting unhandled exception in double linked list in C++

Question

I created a doubly-linked list in C++. Everything works great if I insert a node at the beginning of the list or if I just insert a node at the end of the list; but, when I insert a node at the beginning and then try to insert a node at the end, I get a null pointer error!

Here is the code and the problem is in the InserAtEnd function

#include <iostream>

using namespace std;

struct Node {
    int data;
    Node* prev;
    Node* next;
};

struct MyList {
    Node* head;
    Node* tail;
};

bool IsEmpty(MyList list) {
    if (list.head == nullptr) return true;
    else return false;
}

void Insert(MyList& list, int data) {
    Node* node = new Node();

    node->data = data;
    node->prev = nullptr;
    node->next = list.head;   //node->next points to NULL

    if (list.head == nullptr) {
        list.head = node;
        node->prev = nullptr;
    }
    else {
        //insert the new node at the beginning of the list
        list.head->prev = node;
        list.head = node;
        node->prev = nullptr;
    }
}

// Insert node at end of list
void InsertAtEnd(MyList& list, int data) {
    Node* node = new Node();

    node->data = data;
    node->next = nullptr;
    node->prev = nullptr;

    if (list.head == nullptr) { // Empty list
        list.head = node;
        list.tail = node;
    }
    else {
        list.tail->next = node;
        node->prev = list.tail;
        list.tail = node;
    }
}


//Traverse the list from the head
void PrintAll(const MyList& list) {
    Node* temp = list.head;

    if (temp == nullptr) {
        cout << "list is empty" << endl;
    }
    else {
        while (temp != nullptr)
        {
            cout << temp->data << endl;
            temp = temp->next;
        }

        cout << "*************************************" << endl;
    }
}

Node* Search(const MyList& list, int key) {
    Node* temp = list.head;

    while (temp != nullptr && temp->data != key)
    {
        temp = temp->next;
    }

    return temp;
}

void Delete(MyList& list, int key) {
    Node* temp = Search(list, key); //call search() 

    if (temp != nullptr)
    {
        if (temp->prev != nullptr)
        {
            temp->prev->next = temp->next;
        }
        else
        {
            list.head = temp->next;
        }

        if (temp->next != nullptr)
        {
            temp->next->prev = temp->prev;
        }
    }
}

int main() {

    MyList list;

    list.head = nullptr;    //initialize the linked-list
    list.tail = nullptr;

    if (IsEmpty(list)) 
        cout << "List is empty" << endl;



    Insert(list, 10);
    PrintAll(list);
    /*
    Insert(list, 20);

    Insert(list, 30);

    Insert(list, 40);
    */

    // Insert at end
    cout << "Now insert at end" << endl;
    InsertAtEnd(list, 70);

    InsertAtEnd(list, 45);

    InsertAtEnd(list, 59);

    InsertAtEnd(list, 12);

    InsertAtEnd(list, 33);
    PrintAll(list);
    

    /*
    int x = 24;
    Node* result = Search(list, x);

    if (result == nullptr) cout << "Cannot find " << x << endl;
    else cout << "Found " << result->data << endl;

    Delete(list, 200);
    PrintAll(list);

    Delete(list, 10);
    PrintAll(list);

    Delete(list, 40);
    PrintAll(list);

    Delete(list, 20);
    PrintAll(list);

    Delete(list, 30);
    PrintAll(list);
    */
    return 0;
}

*Can anyone help?* -- [What is a debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). And please [read this](https://idownvotedbecau.se/nodebugging/). — PaulMcKenzie, Jun 06 '22 at 02:15
If you use your debugger to look what happens when `Insert()` or `InsertAtEnd()` gets called, and what's different about the end results (after all, if the list is empty then the results should be same), then the bug in the shown code should be very obvious. This is exactly what a debugger is for. It [runs your program, one line at a time, and shows you what's happening](https://stackoverflow.com/questions/25385173/), this is something that's every C++ developer must know how to do. With your debugger's help you'll able to quickly find all problems in this and all future programs you write. — Sam Varshavchik, Jun 06 '22 at 02:22
I have been trying to debug in Visual Studio, but it locks up when I get the breakpoint. — Bill Moran, Jun 06 '22 at 02:23
What does "it locks up when I get the breakpoint" mean? What breakpoint? Where do you set it? — Sam Varshavchik, Jun 06 '22 at 02:24
I reinstalled Visual Studio and the debugger worked. Thank you all for your help. — Bill Moran, Jun 06 '22 at 02:42

score 0 · Accepted Answer · answered Jun 06 '22 at 02:24

the problem is in the InserAtEnd function

How do you know?

In fact the problem isn't in InserAtEnd but in Insert:

You never set list.tail.

Tip: use Node **tail = &head; for a more efficient MyList and add member initializers and a Constructor.

This is C++ with classes. Use member functions.

Getting unhandled exception in double linked list in C++

1 Answers1