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++，所以如果我错了请纠正我，但这里的 tail 是一个字段。)

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