破坏链表

Question

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

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); 
     } 
    } 
}; 

Answer 1

列表可以递归清除或迭代清除。

除了您的（恕我直言修正）版本，我使用了一个不同的方法–使Node本身“负责任”删除其尾部。这也导致递归清除（但代码更少）。

递归结算：

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测试人员进场时，我改变了主意。在现实世界的项目中，列表很长，递归清除耗尽堆栈内存。 （Yepp – a 堆栈溢出。）我应该知道更好！

因此，我重复地做出了清算–，其中“责任”从Node移回List。 （该API的用户不会注意这个，因为它发生“引擎盖下”。）

迭代结算：

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; 
};