删除正向链表

Question

有两种已知的删除正向链表的方法（只有两种？）

一种方法是递归函数，它效率低下，如果列表太大会导致堆栈溢出

另一种方式（高效）是一个迭代和删除节点的函数，如下所示：

class Forward_list {
public:
   // Constructor...

   ~Forward_list() { if(head) destroy(); }

   void destroy() {
        node* prev = nullptr;
        while (head) {
            prev = head;
            head = head->next;
            delete prev;
        }
    }

    // functions...
private:
    // data members...
    node* head;
};

现在这样做怎么样：

class Forward_list {
public:
    // Constructor...

    ~Forward_list() { if(head) delete this->head; }

    // functions...
private:
    struct node {
        ~node() { delete this->next; } // <- this way
        type data;
        node* next;
    };
    node* head;
    // data members...
};

我测试了它，它工作正常......我发现这种方式更干净，但不确定是否会有副作用？

Answer 1

你的解决方案在技术上是正确的，我能想到的唯一问题是你不能删除一个节点而不删除后面的所有节点。

Answer 2

~node() { delete this->next; } // <- this way
I find this way cleaner but not sure if there would be side effects ?

好吧，"side effect" 将是，您不能从列表中删除任何节点，除非删除整个列表的其余部分，因为 ~node() 在那里被递归调用。

这可能不是您想要做的。

Answer 3

因为之前没有提到：当使用

delete this->next;

注意析构函数被递归调用，即delete析构函数中的下一个节点的方法等同于[=11的递归方法=]列出一个清单。递归只是不那么直接和明显。

删除正向链表

Deleting forward linked list

c++

linked-list

forward-list