在常量时间内表达单向链表方法: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;
}