C++链接列表删除所有

Question

所以这是一个概念性的问题.我正在用C++编写一个LinkedList,并且由于Java是我的第一语言,我开始编写我的removeAll函数,以便它只是将尾节点连接到头部(我使用的是Sentinel Nodes btw).但我立即意识到这在C++中不起作用,因为我必须为节点释放内存!

有没有办法绕过整个列表,手动删除每个元素？

Answer 1

您可以使每个节点拥有下一个节点,即负责在它自身被销毁时销毁它.您可以使用智能指针执行此操作,如std::unique_ptr:

struct node {
    // blah blah
    std::unique_ptr<node> next;
};

然后你可以破坏第一个节点,所有其他节点都将被解释:它们将在unique_ptr析构函数的连锁反应中被销毁.

如果这是一个双向链表,则不应unique_ptr在两个方向上使用s.这将使每个节点拥有下一个节点,并由下一个节点拥有!您应该使此所有权关系仅在一个方向上存在.在另一个使用常规非拥有指针:node* previous;

但是,这不会像Sentinel节点那样工作:它不应该被销毁.如何处理这取决于如何识别标记节点和列表的其他属性.

如果您可以轻松区分Sentinel节点,例如检查布尔成员,则可以使用自定义删除器来避免删除标记:

struct delete_if_not_sentinel {
    void operator()(node* ptr) const {
        if(!ptr->is_sentinel) delete ptr;
    }
};

typedef std::unique_ptr<node, delete_if_not_sentinel> node_handle;

struct node {
    // blah blah
    node_handle next;
};

这阻止了哨兵的连锁反应.