免費商店的雙鏈表

Question

我已經編程了大約8個月，所以我對編程頗爲陌生，並且出現在ADT上，包括雙鏈表。

我沒有意識到我見過的雙鏈表實現在免費商店中，它們都在堆棧中。如果從列表中刪除特定節點，您可以立即在所述節點上調用delete，而不是等待整個LinkedList結構超出範圍，否則不會讓自由存儲上的每個節點都具有更高的內存效率。

至少如果我的理解正確，只需使用正常的重新鏈接過程從列表中刪除節點實際上並不釋放節點佔用的內存。

我知道免費商店是關聯新關鍵字，哪裏有新的，刪除應該遵循。我瞭解到，您實際上不應該使用原始指針來管理內存，因爲如果您忘記刪除免費商店中的某個項目，則會發生內存泄漏。幸運的是C++ 11引入了智能指針可以解決這個問題，但問題在於，免費商店中鏈接列表結構中的節點的所有者究竟是誰？

在一個非常基本的LinkedList，我們可能對這個

struct Node 
{ 
    int _value; 
    Node * _next = nullptr; 
    Node * _prev = nullptr; 

    Node(int value) : _value(value) {} 
}; 

class LinkedList 
{ 
    Node * _head = nullptr; 
    Node * _tail = nullptr; 
    int _count = 0; 

public: 
    //ctors & dtor 
    //getters & setters & other methods 
}; 

其中_count是當前存儲在鏈表中元素的個數。考慮到不應該使用原始指針來管理內存，在我看來，我應該將一些原始指針轉移到C++ 11中引入的智能指針。

問題是，1）我真的不知道，誰應該擁有自由商店，即創建的節點。哪些原始指針應該轉換爲智能指針？

2）另一個問題是，將std :: unique_ptr足夠這個實現嗎？即使我使用std :: unique_ptr，一旦我將其從列表中取消鏈接，節點將被刪除嗎？程序如何知道，節點不再使用？

非常感謝您的回覆。

---

編輯：作爲參考，我加入了兩個方法，構造函數和我實現的插入方法。這就是我的意思是在棧上有一個LinkedList。正如你所看到的，我沒有在我的代碼中使用新的任何地方，然而，鏈接列表的作品。

LinkedList(int value) 
{ 
    Node newNode(value); 

    _head = &newNode; 
    _tail = &newNode; 
    _count++; 
} 

void InsertAtEnd(int value) 
{ 
    Node newNode(value); 

    //tail points to nothing, list is empty 
    if (_tail == nullptr) 
    { 
     _head = &newNode; 
     _tail = &newNode; 
     _count++; 
    } 
    //list is not empty 
    else 
    { 
     _tail->_next = &newNode; 
     _tail = &newNode; 
     _count++; 
    } 
} 

Answer 1

想想實現一個智能指針：如果你嚴格按照規則，你需要一個智能指針來實現智能指針。在這種情況下，你有一個例外。同樣，對於鏈接列表，節點之間的指針不代表所有權。而是列表（class LinkedList）擁有所有節點，而在內部它們只是「連接」。

對於所有這些的完整性並且在「ADT」中實現「A」，這些實現細節需要被隱藏。特別是，用戶不應該直接訪問節點。這也意味着列表和節點組成一個單元（通常存在C++ friend關係），並且在內部它們使用原始指針（就像智能指針一樣）。由於這是從外部保護的，規則不使用原始指針的例外是合理的。

注：

• 實現一個鏈表是一個很好的學習經驗，但請不要使用沒有認真考慮，當有std::list。
• 關於所有權管理，我會使用LinkedList中的std::deque<Node>成員來存儲節點。在容器內部，您甚至可以維護已使用和未使用的元素列表。是的，這有點作弊，但它可以讓所有權管理安全（即無內存泄漏），同時還可以讓您學習建立鏈表。
• 請注意，您也可以在C++中嵌套類。在這種情況下，我將節點類嵌套在鏈表類中。畢竟，這個類不應該被需要在鏈表類以外，所以它不必在同一個命名空間中。