破壞鏈表

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