如何从内存中"删除"此链接列表？

Question

我已经创建了用于构建链表的类.类声明如下:

class LinkedList
{
    private:
      int data;
      LinkedList *next;
      static int count;

     public:
      LinkedList(void);
      ~LinkedList(void);

      int insert(int arg);
      int remove(int arg);
      bool find(int arg);
};

如何确保删除此链接列表的所有节点？析构函数负责删除一个节点.我曾经像以前一样制作链表,但从未考虑过清理内存.

Answer 1

天真的实施

~LinkedList() {delete next;}

将做正确的事情 - delete将在下一个元素上调用析构函数,这将删除它后面的元素,依此类推,删除整个列表.

但是,这意味着递归调用析构函数,因此删除非常长的列表可能会导致堆栈溢出.迭代可能会更好:

~LinkedList() {
    while (LinkedList * head = next) {
        next = head->next;
        head->next = nullptr;
        delete head;
    }
}

正如评论中所指出的,拥有负责内存管理的单独List和Node类List以及Node包含数据和链接的简单聚合可能更合适.然后析构函数中的错误范围较小,因为它不需要使任何指针无效以防止递归:

struct Node {
    int data;
    Node * next;
};

struct List {
    Node * head;

    ~List() {
        while (Node * victim = head) {
            head = victim->next;
            delete victim;
        }
    }
};