c++ - 递归删除链表会导致堆栈溢出吗？

Question

我有一个由 Node 对象构建的链表:

class Node {
   public:
      Node(string data);
      Node* GetNext() const;
      void SetNext(Node* nextNode);
      ~Node();
   private:
      string data;
      Node* next;
};

析构函数定义如下:

Node::~Node() {
   delete next;
}

析构函数应该在头部 Node 上调用的地方。

我的问题是:像这样删除单向链表是否会导致大列表出现堆栈溢出(它在小列表上工作正常，即 < 10 大小的列表)。如果是这样，使用迭代解决方案会更好吗，比如

while (head->GetNext() != 0) {
   Node* temp = head->GetNext();
   head->SetNext(temp->GetNext());
   delete temp;
}
delete head;

Node 没有定义的构造函数？

Answer 1

您的解决方案的问题在于，每次调用 ~Node() 方法时，堆栈帧都会不断地在堆栈上堆积。以 3 个 Node 对象为例，从 0x01 开始。删除这些具有以下堆栈帧回溯(我假设每个 Node 对象包含 1 位信息，这不是真的，但它使列表更整洁):

 (0) Node (0x01): ~Node
 (1) Node (0x02): ~Node
 (2) Node (0x03): ~Node

因此，对于一百万个 Node 对象，您将拥有一百万个堆栈帧，甚至在第一个堆栈帧完成之前。每个堆栈帧都会占用堆栈空间，因此，是的，您可能会用完堆栈空间。

迭代解决方案不会遇到此问题，因为对于每次迭代，删除 Node 的调用在下一个 Node之前 完成 删除例程运行。这意味着在每次迭代期间您在堆栈上有一个函数调用(加上或减去完成该函数调用所需的数量，但特别是，它不是递归)。

除了这个问题之外，还有另一个问题，那就是您没有任何方法可以只删除一个 Node 对象。您可以删除整个列表或列表的一部分。想象一下，如果客户端在前面的示例中引用了 Node (0x02) 并调用了 delete node 会发生什么。在这种情况下，Node (0x02) 和 Node (0x03) 将被删除，但 Node (0x01) 仍将引用指向 Node (0x02) 的内存指针。取消引用它会导致崩溃。