c++ - 删除链表的正确方法

Question

假设，我有一个单链表，它的基本构建 block 是，

struct Node {
  Data d;
  Node *pNext;
  // methods
  ~Node();
};

链表的头部存储为，

Node *m_Head; // member of some class

当我完成列表时，我将通过删除每个节点来清理它，

void Erase()
{
  Node *pIter, *pTemp = m_Head;
  while((pIter = pTemp) != 0)
  {
    pTemp = pIter->pNext;
    delete pIter;
    pIter = pTemp;
  }
}

我想，如果我能简化这个。所以我想出了一个想法，我可以用一条指令清理整个链表!

delete m_Head;

析构函数看起来像:

Node::~Node() { delete this->pNext; }

这里我担心的是，它会导致递归(隐含地由于delete)吗？如果是，那么对于更大的链表来说绝对是一个问题。编译器能否以任何方式帮助优化它？

[注意:不使用任何库设施，如 std::list 或其他。]

Answer 1

我想你要问的问题是，列表中的每个 Node 拥有它的 pNext Node?如果不是，那么它没有必要在其析构函数中删除其 pNext 节点。

在大多数链表实现中，所有节点都属于链表，一个节点并不拥有链表中它之后的所有节点。将节点保持为哑(POD 结构)并让所有逻辑驻留在列表中更有意义。

您的节点具有析构函数但没有复制构造函数或复制赋值运算符，这绝对是一种设计“味道”。我认为当您使用代码实现插入、拼接和删除单个元素功能时，这种方法会导致更多的复杂性，因为在任何情况下您都必须手动管理 pNext 指针，以避免无意中破坏整个尾部的列表。