爲什麼鏈表刪除和插入操作的複雜度爲O（1）？它不應該是O（n）

Question

據說LinkedList的複雜性刪除和添加操作是O(1)。在ArrayList的情況下，它是O(n)。

計算大小爲「M」的ArrayList：如果我想刪除第N個位置的元素，那麼我可以直接使用索引在第N個位置（我不必遍歷到第N個索引），並且那麼我可以刪除元素，直到這一點的複雜性是O（1），那麼我將不得不移動其餘的元素（MN移位），所以我的複雜性將是線性的，即O（M-N + 1）。因此在最後的刪除或插入會給我最好的性能（如N〜M），並且在開始時的刪除或插入將是最差的（如N〜1）。

現在，大小爲「M」的LisnkedList：因爲我們無法直接到達LinkedList中的第N個元素，所以要訪問第N個元素，我們必須遍歷N個元素，因此LinkedList中的搜索比ArrayList更昂貴。 ..但刪除和添加操作被認爲是O（1）LinkedList的情況下，在LinkedList中沒有涉及Shift，但是涉及rigary的遍歷操作？所以複雜度應該是O（n）的次序，其中最差的性能將在尾節點處，並且最佳性能將會在頭節點處。

任何人都可以請解釋一下爲什麼我們在計算LinkedList刪除操作的複雜度時不考慮遍歷成本？

所以我想了解它如何在java.util包中工作。如果我想在C或C++中實現相同，我將如何實現O（1）用於隨機刪除和插入LinkedList中？

Answer 1

成本

刪除和加操作被稱爲O（1）的情況下爲LinkedList，因爲在LinkedList中沒有涉及該轉移，但是涉及遍歷操作的權利是？

只要您保持對列表兩端的引用，添加到鏈表的任一端都不需要遍歷。這是Java爲其add和addFirst/addLast方法所做的。

同樣適用於無參數remove和removeFirst/removeLast方法 - 它們在列表末端運行。

remove(int)和remove(Object)另一方面，操作不是O（1）。它們需要遍歷，所以你將它們的成本正確地標識爲O（n）。

Answer 2

去除認爲你已經擁有的指針，你要刪除的元素的右邊位置的複雜性......

不認爲你把尋找它

Information on this topic is now available on Wikipedia at: Search data structure 

    +----------------------+----------+------------+----------+--------------+ 
    |      | Insert | Delete | Search | Space Usage | 
    +----------------------+----------+------------+----------+--------------+ 
    | Unsorted array  | O(1)  | O(1)  | O(n)  | O(n)   | 
    | Value-indexed array | O(1)  | O(1)  | O(1)  | O(n)   | 
    | Sorted array   | O(n)  | O(n)  | O(log n) | O(n)   | 
    | Unsorted linked list | O(1)* | O(1)*  | O(n)  | O(n)   | 
    | Sorted linked list | O(n)* | O(1)*  | O(n)  | O(n)   | 
    | Balanced binary tree | O(log n) | O(log n) | O(log n) | O(n)   | 
    | Heap     | O(log n) | O(log n)** | O(n)  | O(n)   | 
    | Hash table   | O(1)  | O(1)  | O(1)  | O(n)   | 
    +----------------------+----------+------------+----------+--------------+ 

* The cost to add or delete an element into a known location in the list (i.e. if you have an iterator to the location) is O(1). If you don't know the location, then you need to traverse the list to the location of deletion/insertion, which takes O(n) time. 
** The deletion cost is O(log n) for the minimum or maximum, O(n) for an arbitrary element. 

Answer 3

是的，如果您一次考慮兩個操作（索引和插入），那麼您是正確的。在這種情況下不是這樣，因爲當您在鏈接列表的中間插入節點時，所採取的假設是您已經在必須插入節點的地址上。

訪問節點的時間複雜度是O（n），而只有插入節點是O（1）。

插入頭部需要添加元素並更新頭部指針。

newnode->next = head; 
head = newnode; 

在尾部插入需要保留一個指向尾部元素的指針，在尾部添加元素並更新尾指針。

tail->next = newnode; 
tail = newnode; 

刪除頭元素需要更新頭和刪除以前的頭元素。所有上述

temp = head; 
head = head->next; 
delete temp; /* or free(temp); */ 

是微不足道的操作和不依賴於鏈表中元素的個數。因此，它們是O（1）

然而，刪除tail元素將是一個O（n）操作，因爲即使您可能有一個尾指針，您仍然需要將設置爲倒數第二個節點新的尾節點（通過更新尾指針並將節點的下一個成員設置爲NULL）。爲此，您需要遍歷整個鏈表。

penultimate_el = find_penultimate_el(head); /* this is O(n) operation */ 
delete tail; /* or free(tail) */ 
tail = penultimate_el; 
tail->next = NULL; 

Answer 4

ArrayList提供了可調整大小的數組和stores "references" or "pointers" to actual storage。如果數組擴展超出其分配的大小，則必須重新創建此數組。換句話說，在開始插入一個節點需要將所有現有的元素向上移動一個，或者如果超出了分配的大小，則重新分配整個列表。這就是爲什麼插入是O(n)。

LinkedList由一系列節點組成;每個節點分開分配。所以在插入時，不需要遍歷所有的節點。這就是爲什麼它具有複雜性O(1)。 但是，如果你在最後插入並且只有第一個節點的引用，那麼你可能不得不遍歷整個列表，因此在這種情況下複雜度將是O（n）。

編輯

如果你看看java.util.LinkedList的源代碼，你可以發現，LinkedList始終保持最後一個元素

的軌道下面是從實際java.util.LinkedList類的一些代碼段。

package java.util; 

... 

public class LinkedList<E> 
    extends AbstractSequentialList<E> 
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable 
{ 
    transient int size = 0; 

    /** 
    * Pointer to first node. 
    */ 
    transient Node<E> first; 

    /** 
    * Pointer to last node. 
    */ 
    transient Node<E> last; 


    ... 
    ... 


    /** 
    * Appends the specified element to the end of this list. 
    */ 
    public boolean add(E e) { 
     linkLast(e); 
     return true; 
    } 



    ... 
    ... 


    /** 
    * Links e as last element. 
    */ 
    void linkLast(E e) { 
     final Node<E> l = last; 
     final Node<E> newNode = new Node<>(l, e, null); 
     last = newNode; 
     if (l == null) 
      first = newNode; 
     else 
      l.next = newNode; 
     size++; 
     modCount++; 
    } 


    ... 
    ... 

} 

特別參見linkLast()方法。它不遍歷整個列表。它只是將元素插入列表的末尾，這就是爲什麼時間複雜度爲O(1)。