爲什麼雙向鏈表的加載前運行時間是O（1）？

Question

在數據結構中，我們說在單鏈表中的節點之前推一個元素是O（n）操作！因爲沒有後向指針，所以我們必須一路走過這些元素，才能到達我們要在新元素之前添加的關鍵點。因此，它具有線性運行時間。 然後，當我們引入雙向鏈表時，我們說這個問題已經解決了，現在因爲我們有兩個方向的指針在之前推動成爲一個常量時間操作O（1）。 我明白邏輯，但仍然有些事情讓我感到困惑！由於我們沒有時間訪問列表中的元素，因此爲了找到我們之前要添加的元素，我們必須遍歷前一個元素才能到達那裏！在雙鏈表中，實現add-before命令現在速度更快，但是，找到感興趣的鍵的操作仍然是O（n）！那麼爲什麼我們用雙鏈表對前面添加的操作變成O（1）？

謝謝，

Answer 1

在C++中，在std ::目錄::插入件（）函數的迭代器，以指示應當發生的插入件。這意味着調用者已經有了這個迭代器，並且插入操作是而不是執行搜索並因此在恆定時間內運行。

但是，find（）算法是線性的，並且是搜索列表元素的常規方法。如果您需要查找+插入，則組合爲O（n）。

但是，插入前不需要進行搜索。例如，如果你有一個緩存的（有效的）迭代器，你可以在它的前面（或刪除）它所對應的元素在不變的時間。