c++ - 尝试在双向链表的中间插入新节点时我是否连接错误？

Question

结构看起来像:

class DList{
private:
        struct Elem {
        Elem *prev, *next;
        };
        Elem *_head, *_tail;
}

现在我有两个现有节点:cur 和 cur->next，我想在它们之间插入一个新节点。这是我所做的:

    cur->next = ins;//step-1-1 cur
    ins->prev = cur;//step-1-2 cur

    ins->next = cur->next;//step-2-1 cur->next
    cur->next->prev = ins;//step-2-2 cur->next 

问题是在我的程序的进一步遍历循环中，我的指针无法再到达 _tail。我是不是在我的插入部分弄错了什么？ (一旦我在上面的中间代码处评论插入，循环就完美地工作了)

Answer 1

是的，这里有一个接线错误。让我们画画吧!

想象一下事情看起来像这样，最初:

             curr
              |
              v
         +----------+                         +----------+
         |   next   | ----------------------> |   next   | --> ...
         +----------+                         +----------+
 ... <-- |   prev   | <---------------------- |   prev   | <-- ...
         +----------+                         +----------+
                           +----------+
                           |   next   |
                           +----------+
                           |   prev   |
                           +----------+
                                ^
                                |
                                ins

首先，您执行 cur->next = ins;，它会执行以下操作:

             curr
              |
              v
         +----------+                         +----------+
         |   next   | -----------+            |   next   | --> ...
         +----------+            |            +----------+
 ... <-- |   prev   | <----------+----------- |   prev   | <-- ...
         +----------+            v            +----------+
                           +----------+
                           |   next   |
                           +----------+
                           |   prev   |
                           +----------+
                                ^
                                |
                                ins

请注意，我们不再有指向原先位于 curr 之后的元素的指针 - 糟糕!这将是一个问题。

现在，我们执行 ins->prev = curr;，如下所示:

             curr
              |
              v
         +----------+                         +----------+
         |   next   | -----------+            |   next   | --> ...
         +----------+            |            +----------+
 ... <-- |   prev   | <----------+----------- |   prev   | <-- ...
         +----------+            v            +----------+
               ^           +----------+
               |           |   next   |
               |           +----------+
               +---------- |   prev   |
                           +----------+
                                ^
                                |
                                ins

现在，我们编写 ins->next = curr->next;。但是哎呀!注意 curr->next 指向 ins，所以我们只是在这里添加了一个循环:

             curr
              |
              v
         +----------+                         +----------+
         |   next   | -----------+            |   next   | --> ...
         +----------+            |            +----------+
 ... <-- |   prev   | <----------+----------- |   prev   | <-- ...
         +----------+            v            +----------+
               ^           +----------+
               |           |   next   | --+
               |           +----------+   |
               +---------- |   prev   | <-+
                           +----------+
                                ^
                                |
                                ins

最后，您编写 cur->next->prev = ins; 但是哎呀! curr->next 仍然是 prev，所以我们得到另一个循环:

             curr
              |
              v
         +----------+                         +----------+
         |   next   | -----------+            |   next   | --> ...
         +----------+            |            +----------+
 ... <-- |   prev   | <----------+----------- |   prev   | <-- ...
         +----------+            v            +----------+
                           +----------+
                       +-> |   next   | --+
                       |   +----------+   |
                       +-- |   prev   | <-+
                           +----------+
                                ^
                                |
                                ins

这里的问题是，在第一次赋值后，您无法跟踪 curr->next 指向的单元格，因此您无法找到正确的位置。

如果你开始写这样的东西会怎样？

DList* next = curr->next;

然后在某些上下文中使用 next 而不是 curr->next？