双链表插入无限循环..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。

Answer 2

我看到的唯一真正的问题是，当你插入时，你正在做以下操作：

    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;