二重のリンクリストC++

Question

私はテンプレート付きの二重リンクリストを作成しています（練習用です）。

私はListClassのためのインサート（のconst T & val2Ins）機能を右しようとしています2クラス、ListClass & NodeClass

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

を持っています。この関数はある値をとり、昇順にソートします。ヘッドは、最小の値を保持する最初のノードを指します。熱から尾までは昇順である。

私はこれらのポインタで作業して実際にリンクを実行する方法を理解するのに非常に苦労しています。空のリストにノードを挿入するのは簡単ですが、リストにデータが入力されると、ポインタのリンクを実行する方法がわかりません。誰かが私にこれに関するアドバイスをくれますか？

Answer 1

ポインタを使用して頭（または尾）からリストを歩き、データを比較するだけです。

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