加倍鏈接列表C++

Question

我正在創建一個模板雙向鏈表（僅供練習）。

我有2個班，ListClass &結點類別

template < class T > 
class ListClass 
{ 
    private: 
    NodeClass <T> *head; 
    NodeClass <T> *tail; 

    public: 
    //some member functions 
    //my question will deal with the member function called insert(const T &val2Ins 
}; 

template < class T > 
class NodeClass 
{ 
    private: 
    data; 
    NodeClass *next; 
    NodeClass *prev; 

    public: 
    //some member functions (getter functions mostly) 
}; 

我試圖向右插入（常量牛逼& val2Ins）爲ListClass功能。該功能應該具有一定的價值，並按升序「排序」。頭指向第一個節點，它保持最小的值。所以從熱到尾是按升序排列的。

我有一個很難與這些指針工作，並找出如何實際執行鏈接。將節點插入到空列表中並不重要，但是一旦列表被填充，我不知道如何執行指針的鏈接。有人能給我一些建議嗎？

Answer 1

您只需使用指針從頭部（或尾部）走過列表並比較數據即可。請注意，我假設結點類別已宣佈ListClass爲朋友（或你需要設置的getter和setter私有數據成員）：

void insert(const T &val2Ins) 
{ 
    using Node = NodeClass<T>; 
    Node *next = head; 

    while(next) 
    { 
     if(val2Ins < next->data) 
     { 
      Node *n = new Node; 
      n->previous = next->previous; 
      n->next = next; 
      next->previous = n; 
      return; 
     } 

     next = next->next; 
    } 

    if(!next) 
    { 
     Node *n = new Node; 
     n->previous = tail; 

     if(tail) 
      tail->next = n; 
     else 
      tail = n; 

     if(!head) 
      head = n; 
    } 
}