c++ - 単方向リスト法を一定時間で表現: O(1)

Question

リストの最後にオブジェクトを挿入する単一リンク リストのメソッドを作成しました。これは、線形時間 O(n) で記述されます。

この同じタスクを実行するにはどうすればよいでしょうか。ただし、コードを一定時間 (O(1)) で記述するにはどうすればよいでしょうか?

リニアタイムコード O(n):

template <class Object>
void List<Object>::insert_back( const Object& data ) {
    ListNode<Object>* newnode = new ListNode<Object>( data, NULL );
    ListNode<Object>* lastNode = head;
    while (lastNode->getNext()!= NULL && lastNode->getNext()->getElement() != data )
        lastNode = lastNode->getNext();
    lastNode->setNext( newnode );

}

Answer 1

通常、リストへのヘッド ポインタがあります。目的を達成するには、テール ポインターが必要です。以下は、ビジュアルを与える試みです。

 [ A -> B -> C -> D ]
   |              |
 (head)         (tail)

したがって、あなたのメソッドは次のようになります（私はc ++を知らないので、間違っている場合は修正してください。ただし、ここのテールはフィールドです。）

void List<Object>::insert_back( const Object& data ) {
    ListNode<Object>* newnode = new ListNode<Object>( data, NULL );
    ListNode<Object>* lastNode = tail;
    lastNode->setNext( newnode );
    tail = newnode;
}