当我试图在双链接列表的中间插入一个新节点时，我是否丢失了连接？

Question

结构如下：

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

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

    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 - oops之后的元素的指针了！以后就会有问题了。

现在，我们来做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;，但是oops！curr->next仍然是prev，所以我们得到了另一个循环：

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

这里的问题是，在第一次赋值之后，您丢失了curr->next所指向的单元格的跟踪，因此您失去了查找正确位置的能力。

如果你从写这样的东西开始呢？

DList* next = curr->next;

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

Answer 2

关键是不要丢失以后将要使用的值。您的第一行代码cur->next = ins;使您失去了原始值(cur->next)；此后，您真的不知道谁将是ins的next。

使用此逻辑在中间插入一个新节点。我们一开始说，

cur - cur->next  
    |
  [ins]

做,

ins->next = cur->next;

(cur) (ins) - (cur-> next ) { next和=next和prev}

cur->next = ins;

(cur) - (ins) - (cur->next)

ins->prev = cur;

cur = ins - (cur->next)

ins->next->prev = ins;

cur = ins = (cur->next)