Doubly Linked List insertion infinite loop... C++

Question

I am implementing doubly linked list in C++. Before insertion, my printing node function works well but after I do the insertion to the front, the printing goes forever.

for example, I have nodes of 1, 2, 3 data and I insert the data to front with 5. Then I try to print, and it only shows 5, 1, INFINITE LOOP without even going to the third node 2.

Here is my structure.

    struct dl_node
    {
        int               data;
        struct dl_node*   prev;
        struct dl_node*   next;

        dl_node(dl_node* prev, dl_node* next, int data)
        {
            // here, prev is the parameter
            // this->prev is from an object
            this->prev = prev;
            this->next = next;
            this->data = data;
        }

        // constructor, without pointer parameter
        explicit dl_node(int data)
        {
            this->prev = this;
            this->next = this;
            this->data = data;
        }
    };

Here is my insertion function.

    // "push-front" operation
    dl_node* insert_node(dl_node* head, int data)
    {
        if (nullptr == head)
                    return new dl_node(data);

            auto insertion
            = new dl_node(head->prev, head, data);
            // previous node of this insertion is head's prev
            // next node of this insertion is head

            insertion->prev->next = insertion;
            insertion->next->prev = insertion;

            return insertion;
    }

Here is my initialization.

    struct dl_node* head   = new dl_node(NULL);
    struct dl_node* node_1 = new dl_node(NULL);
    struct dl_node* node_2 = new dl_node(NULL);

    head  ->data = 1;
    head  ->next = node_1;
    node_1->prev = head;

    node_1->data = 2;
    node_1->next = node_2;
    node_2->prev = node_1;

    node_2->data = 3;
    node_2->next = nullptr;

Here is my insertion.

    // we insert to FRONT
    head = insert_node(head, 5);

Here is my printing loop.

struct dl_node* current_node_2 = head;
while ( current_node_2 != nullptr )
    {
            cout << current_node_2->data << ", ";
            current_node_2 = current_node_2->next;
    }
    // 5, 1, I get infinite loop from here....

Could anybody have any idea?

Answer 1

The problem is that your default dl_node constructor sets both prev and next to this.

When you call insert_node(head, 5) you end up with the following state:

insertion->prev = head->prev;  // assigned in constructor, but head->prev == head
insertion->next = head;
insertion->prev->next = insertion;
insertion->next->prev = insertion;

But insertion->prev == head->prev, and we know head->prev == head, so

insertion->prev->next = insertion

reduces to:

head->next = insertion;

So you end up with a list that looks like this:

insertion -> head -> insertion -> ...

You should change your default constructor to set both next and prev to NULL. Also in your insert function, you should check that insertion->prev and insertion->next are non-NULL before dereferencing them.

Answer 2

The only real issue I see with what you have there is when you are doing yoru insert you are doing the following:

    newnode.next = head
    newnode->prev = head.prev
    newnode->data = 5

    head.prev = newnode (missing)

but you are never setting the head.prev to newnode, which is leaving the head with a null pointer. Also I'm not too sure what this code is in there for but it may be altering your pointers incorrectly.

    insertion->prev->next = insertion;
    insertion->next->prev = insertion;