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

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

关键是不要丢失以后要用到的值。你的第一行代码cur->next = ins;让你失去了原来的价值(cur->next)；此后你真的不知道谁会是next到ins。

使用这个逻辑在中间插入一个新节点。让我们说最初，

cur - cur->next  
    |
  [ins]

做，

ins->next = cur->next;

(cur) (ins) - (cur->next) {假设 - 对于下一个，= 对于下一个和上一个}

cur->next = ins;

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

ins->prev = cur;

cur = ins - (cur->next)

ins->next->prev = ins;

cur = ins = (cur->next)

Answer 2

是的，这里有一个接线错误。来画画吧！

想象一下，最初是这样的：

             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？

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

Have i miswired when trying to insert a new node at the middle of doubly linked list?

c++

pointers

data-structures

doubly-linked-list