我在单链接列表中编写了一个方法,该方法在列表末尾插入一个对象。它是用线性时间写的,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 );
}