如何更改我的鏈接列表插入功能從O（N）到O（1）

我實現了我的linkedList函數，它在最後插入，但我使用了蠻力方法，直到結束，然後添加它。我想將其改爲O（1）。如果你們有任何提示會很棒。如何更改我的鏈接列表插入功能從O（N）到O（1）

來源

2015-07-09 Crowning

你可以添加一個名爲'tail'一個成員變量，你會需要照顧你的其他功能。 – scohe001

是的，基本上存儲一個指向列表末尾的指針並將其用於插入。按照慣例，刪除和添加將需要跟蹤此。 –

不要忘記，當調用insertAtEnd（）時，如果列表爲空，那麼'tail'將爲空。 –

做出這個O（1）的唯一方法是保持對List對象中最後一個Object的引用。無論何時在List的末尾插入新對象，指針都會更新爲指向它。

來源

2015-07-09 22:34:21

您的實際問題已經得到解答：存儲一個額外的尾指針，您可以在其中插入而不循環遍歷整個列表。

但也看看你的代碼：

for (node; node->getNext() != NULL && node->getNext()->getElement() != data;) 
    node= node->getNext(); 
node->setNext(insertNode);

在第二個條件的for循環看起來有點怪我。如果你想追加一個元素==數據的新元素，你的循環將停止在任何具有該值的現有元素上，並且你會在它之前附加新分配的元素，並且丟失所有以現有元素開始的舊元素元素==數據的節點。看起來像一個bug走向我。

來源

2015-07-09 22:42:22 nv3

正如其他人所說，你需要一個tail節點添加到列表中，然後你可以使用這個insertAtEnd()實施：

template <class Object> 
void List<Object>::insertAtEnd(const Object& o) 
{  
    ListNode<Object>* insertNode = new ListNode<Object>(o, nullptr); 
    if (!head) head = insertNode; 
    if (tail) tail->setNext(insertNode); 
    tail = insertNode; 
}

來源

2015-07-09 23:30:43

如何更改我的鏈接列表插入功能從O（N）到O（1）

回答

相關問題