销毁链表 [英] Destructing a linked list

问题描述

我试图实现一个链表来解决算法问题.
基本上可以正常工作，但是事实证明，我使用了过多的内存.
如果有人指出以下析构函数设计的缺陷，我将不胜感激.

I was trying to implement a linked list for solving an algorithm problem.
It basically worked, however, it turned out that I was using too much memory.
I would appreciate if someone point out defects of following destructor design.

template<typename T>
struct Node {
    Node(): item(0),next(0) {}
    Node(T x): item(x),next(0) {}
    T item;
    Node* next;
};

template <typename T>
struct List {
    List() : head(0),tail(0) {}
    Node<T>* head;
    Node<T>* tail;
    void insert(T x) {
        Node<T>* newNode = new Node<T>(x);
        if(head == NULL) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            tail = tail->next;
        }
    }

    void clearRecur(Node<T>* h) {
        if(h) {
            clearRecur(h->next);
            delete h;
        }
    }

    void clear() {
        if(head) {
            clearRecur(head);
        }
    }
};

推荐答案

可以递归或迭代地清除列表.

A list can be cleared recursively or iteratively.

或者，对于您的版本(恕我直言正确的版本)，我使用略有不同的方法–使Node本身负责"以删除其尾部.这也会导致递归清除(但使用更少的代码).

Alternatively to your (IMHO correct) version, I use a slight different approach – make the Node itself "responsible" to delete its tail. This leads to recursive clearing as well (but with less code).

递归清除:

template<typename T>
struct Node {
    Node(): item(), next(nullptr) {}
    Node(T x): item(x), next(nullptr) {}

    ~Node() { delete next; } // <== recursive clearing

    T item;
    Node* next;

    // Using the default copy ctor would corrupt the memory management.
    // Deleting it lets the compiler check for accidental usage.
    Node(const Node&) = delete;
    // Deleting assignment operator as well.
    Node& operator=(const Node&) = delete;
};

template <typename T>
struct List {
    List() : head(nullptr), tail(nullptr) {}
    ~List() { clear(); }
    Node<T>* head, tail;
    void insert(T x) {
        Node<T>* newNode = new Node<T>(x);
        if (head == nullptr) head = tail = newNode;
        else {
            tail->next = newNode;
            tail = tail->next;
        }
    }

    void clear() {
        delete head;
        head = tail = nullptr;
    }

    // Using the default copy ctor would corrupt the memory management.
    // Deleting it lets the compiler check for accidental usage.
    List(const List&) = delete;
    // Delete assignment operator as well.
    List& operator=(const List&) = delete;
};

这是方法，我在当前项目中做到了.乍一看，它看起来很简单，而且运行良好.当我们的Beta测试人员开始工作时，我改变了主意.在现实世界的项目中，列表是如此之长，以至于递归清除用尽了堆栈内存. (是的堆栈溢出.)我应该知道得更多！

This is the way, I did it in our current project. At the first glance, it seemed enjoying simple and worked fine. I changed my mind when our beta-testers came into play. In real world projects, the lists were such long that the recursive clearing ran out of stack memory. (Yepp – a stack overflow.) I should've known better!

因此，我反复进行清算–从而将责任"从Node移回List. (API用户不会注意到这一点，因为它发生在幕后".)

Thus, I made the clearing iteratively – whereby the "responsibility" is moved back from Node to List. (The API user will not note this as it happens "under the hood".)

反复清除:

template<typename T>
struct Node {
    Node(): item(), next(nullptr) {}
    Node(T x): item(x), next(nullptr) {}
    T item;
    Node* next;
};

template <typename T>
struct List {
    List() : head(nullptr), tail(nullptr) {}
    ~List() { clear(); }
    Node<T>* head, tail;
    void insert(T x) {
        Node<T>* newNode = new Node<T>(x);
        if (head == nullptr) head = tail = newNode;
        else {
            tail->next = newNode;
            tail = tail->next;
        }
    }

    void clear() {
        while (head) {
            Node<T> *p = head; head = head->next;
            delete p;
        }
        tail = nullptr;
    }

    // Using the default copy ctor would corrupt the memory management.
    // Deleting it lets the compiler check for accidental usage.
    List(const List&) = delete;
    // Delete assignment operator as well.
    List& operator=(const List&) = delete;
};

这篇关于销毁链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！