0

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?

4

2 回答 2

1

问题是您的默认dl_node构造函数将prev和都设置next为this。

当你打电话给你时，你insert_node(head, 5)会得到以下状态：

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

但是insertion->prev == head->prev，我们知道head->prev == head，所以

insertion->prev->next = insertion

减少为：

head->next = insertion;

因此，您最终会得到一个如下所示的列表：

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

您应该更改默认构造函数以将两者都设置next为prevNULL。同样在您的插入函数中，您应该在取消引用它们之前检查它insertion->prev并且insertion->next是非空的。

于 2013-08-23T20:47:14.823 回答
0

我看到的唯一真正的问题是，当您执行 yoru insert 时，您正在执行以下操作：

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

    head.prev = newnode (missing)

但是您永远不会将 head.prev 设置为 newnode，这会使 head 带有一个空指针。另外我不太确定这段代码的用途是什么，但它可能会错误地改变你的指针。

    insertion->prev->next = insertion;
    insertion->next->prev = insertion;
于 2013-08-23T20:44:27.920 回答