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?

You might want to mention this is a *circular* double-linked list (at least it looks to be attempting that, anyway) in the question title. It makes a significant difference in the implementation, as you're no-doubt discovering. If it is not the case, then your constructor for `dl_node` make no sense at all. Further, your "initialization" should not be needed. If it functions properly, the only initialization required is `dl_node *head = nullptr;` then followed by using your `insert_node()` to push your initial data in. — WhozCraig, Aug 23 '13 at 20:38
Oh I meant to implement Doubly Linked List. I do not point the last node back to first. — , Aug 23 '13 at 20:41

score 1 · Accepted Answer · answered Aug 23 '13 at 20:47

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.

answered Aug 23 '13 at 20:47

Jonathan Potter

36,172
4
64
79

Thanks, and you mean change this->prev = this; to this->prev = nullptr? – Aug 23 '13 at 20:53
Yes and the same for this->next. – Jonathan Potter Aug 23 '13 at 20:54
1

@dfsadxsadqwd213 You should be using an [initializer list](http://stackoverflow.com/questions/1598967/benefits-of-initialization-lists) for those regardless. Further, `dl_node` does *not* follow the [Rule of Three](http://en.wikipedia.org/wiki/Rule_of_three_(C%2B%2B_programming)) and as such you should either hide the copy-constructor and assignment operator in a `private:` declaration or if you have a C++11 compliant toolchain use the `=delete;` declaration. – WhozCraig Aug 23 '13 at 20:55

score 0 · Answer 2 · answered Aug 23 '13 at 20:44

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;

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

2 Answers2