c++ - 双向链表插入无限循环... C++

Question

我正在用 C++ 实现双向链表。在插入之前，我的打印节点功能运行良好，但在我插入到前面之后，打印永远不会结束。

例如，我有节点 1, 2, 3 数据，我将数据插入到前面 5。然后我尝试打印，它只显示 5, 1, INFINITE LOOP 甚至没有去第三个节点 2 .

这是我的结构。

    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;
        }
    };

这是我的插入函数。

    // "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;
    }

这是我的初始化。

    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;

这是我的插入。

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

这是我的打印循环。

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....

有人知道吗？

Answer 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 和 prev 都设置为 NULL。同样在您的插入函数中，您应该在取消引用之前检查 insertion->prev 和 insertion->next 是否为非 NULL。