双链表无限循环？

Question

如果我要创建一个节点类，如下所示，并且如果在双向链表中使用它，那么它会在双向链表解构时创建无限循环吗？或者它会很好地终止吗？

class Node
{
    Node(  );

    ~Node(  )
    {
       delete mNext; //deallocs next node
    }

    Contact mContact;
    Node* mPrevious;
    Node* mNext;
}; 

编辑：如果我将代码修改为这样，它会起作用吗？

~Node(  )
{
   mPrevious = NULL;
   if (mNext->mPrevious != NULL)
   {
      delete mNext; //deallocs next node
   }
}

编辑2：或者这样效果最好吗？

~Node(  )
{
   if (mPrevious != NULL)
   {
      mPrevious = NULL;
      delete mNext; //deallocs next node
   }
}

Answer 1

如果考虑到 mNext 指针，节点正在形成一个循环，那么任何节点的破坏实际上可能会形成无限递归循环，并且它将通过炸毁来终止程序堆栈。

可能会发生的是

1. 第一个“外部”delete node; 被发出。
2. 当进入节点析构函数时，还没有执行任何操作，因为代码析构函数是销毁过程中执行的“第一件事”（销毁过程本身非常复杂，包括析构函数代码、类更改、成员销毁、基类销毁，按以下顺序：参见此答案以获得更详细的解释）。
3. 第一个析构函数指令 fill 执行delete mNext;，从而在循环中的下一个节点上触发相同的过程。
4. 因为节点正在形成一个循环，所以该链将“从后面”再次到达node，从而使第一次调用成为永远不会结束的递归。
5. 尽管如此，每次调用都会为激活记录分配堆栈空间，因此一段时间后，允许用于堆栈的所有内存都将耗尽，操作系统将终止该进程。删除调用不是“尾部调用”，因为析构函数代码完成后，必须释放内存，因此无法轻松优化此递归...而 delete mNext; 是析构函数上的最后一个语句仍然有一些操作必须在删除操作完成后执行。

但请注意，根据我的经验，除非使用特殊的编译器选项，否则不会检查堆栈溢出，因此程序终止将非常“异常”。另请注意，在 Windows 下，有一些可怕的代码，在某些情况下，如果程序终止时发生段错误，它们会隐藏段错误，因此 Windows 程序很可能在退出事件循环后完成的此操作中明显地正常终止。

假设通常不考虑堆栈溢出，实际上任何行为都是可能的，包括明显的“无限循环”（请注意，这个无限循环可能不是递归析构函数之一，而是运行时系统内部的某个地方由于堆栈溢出而变得疯狂） 。

为什么我使用“可能”这个词？原因是C++标准规定对象的多次销毁是未定义行为。如果您将这一点添加到 C++ 中无法在未完成销毁的情况下退出析构函数的事实，您将了解编译器理论上可以将对象标记为“正在销毁”并使守护进程飞出您的对象。如果您两次输入同一个对象的析构函数，则会出现问题。然而，检查此错误不是强制性的，编译器编写者通常很懒（这不是对程序员的侮辱），因此不太可能出现此检查（除非启用了某些特殊的额外调试选项）。

总结一下：它可以永远循环吗？是的。能崩溃吗？当然。它能停止告诉我一个对象被销毁两次吗？当然。它可以很好地终止程序吗（即不设置任何错误代码）？是的，也是如此。

任何事情都可能发生。墨菲说，任何对你造成最大伤害的事情都会发生……例如，当你开发它时，程序每次都会很好地终止……并且在演示日期间，它会在你面前严重崩溃。面对一千名潜在客户。

只是不要这样做:-)

Answer 2

它无法知道何时停止，因此它可能会无限运行。
您可能应该编写一个 List 类，它有一个指向（或实际的）Node 的指针。 Node 的 d'tor 应该只处理它自己的字段，在本例中为 mContact。 List 的 d'tor 应该迭代列表中的所有节点（记住何时停止），并删除每个节点（仅删除一次）。

Answer 3

假设你将 mNext 初始化为 null，它不会无限运行。当Delete遇到空指针时，不会执行任何操作。因此它会在你期望的时候结束。

我不确定您正在使用“如果是先前”选项做什么。这些行不通。这要么是一个有效节点，因此有一个前一个节点，要么它不是一个有效节点，检查前一个节点将得到未定义的结果。坚持简单的答案：

class Node 
{ 
Node(  mNext = NULL; ); 

~Node(  ) 
{ 
   delete mNext; //deallocs next node 
} 

Contact mContact; 
Node* mPrevious; 
Node* mNext; 
};  

澄清：此解决方案有效，但前提是满足两个条件：
1) 没有节点在列表中出现两次。
2) 该列表不是循环的。
如果你能保证这些条件，这就是你最简单的答案。如果你不能，你需要做一些更复杂的事情。

Answer 4

就我个人而言，我认为 Node 的析构函数应该与其他节点有任何关系，这有点奇怪。

如果设计由我决定，我将创建一个 List 类，其中包含指向 Node 对象（first 和 last< /代码>）。 List 类的析构函数将负责迭代列表中的所有节点并销毁它们。

Answer 5

这其实很简单。
假设
1）它是一个双向链表，而不是循环链表
2）链表中没有循环：这是一个双链表
3) 实现类只有一个 Node 实例 可能称为 HeadNode 或 LinkList ;) 这是显式销毁的节点

---

示例：LinkList 为 1->2->3->4->5-> ;6->NULL
HeadNode 的析构函数调用（参考第三个假设）将导致递归调用，如下所示：
删除(1)->删除(2)->删除(3)->删除(4)->删除(5)->删除(6)->NULL
所以请检查 if (mNext != NULL) 删除 mNext
它可以工作:)

---

但是：如果你想专门删除一个节点：假设我们只想删除上面示例中的 4 个节点，所有节点都将被删除直到 NULL，所以在删除之前请确保将 Mnext 设置为 NULL。

---

最佳实践是使用 STL 库或使用自动指针类来解决问题的破坏部分