時間複雜度，同時刪除最後一個元素從ArrayList和LinkedList

第1部分： -時間複雜度，同時刪除最後一個元素從ArrayList和LinkedList

我正在讀的書 - 「數據結構與算法變得容易在Java中」，對於刪除從LinkedList的最後一個元素的時間複雜度和Arraylist是O（n）。但是Linkedlist在內部實現了DoublyLinkedlist，所以時間複雜度應該是O（1），對於Arraylist來說它的內部實現類似於Array，它應該是O（1）。

第2部分： -

它還說，一個元件中的一個LinkedList的結尾插入有O（n）的時間複雜度，但LinkedList的無論是在年底和前維持指針。那麼這個陳述是否正確？此外，它說最後在ArrayList中插入元素的時間複雜度爲O（1），如果數組不滿，則O（n）如果數組已滿，則爲O（n）。爲什麼O（n）如果數組已滿？

感謝您回答第一部分。任何人都可以請解釋第二部分。謝謝:)

來源

2017-03-31 user3747182

書是錯誤列表，可以實現，你是正確的。在亞馬遜上有16％的評論認爲這本書有很多錯誤，並給它一兩顆星。我認爲現在是一個讓自己更好的書的好時機。 – dasblinkenlight

本書是否引用帶有這些名稱的java.util類，或者書中提供的具有相同名稱但不同實現的數據結構？ –

這取決於你打電話給什麼方法。

在執行掃視表明，如果你調用LinkedList.removeLast()，這是O（1）。 LinkedList維護指向列表中第一個和最後一個節點的指針。所以它不必遍歷列表以到達最後一個節點。

調用LinkedList.remove(index)與最後一個元素的索引也O（1），因爲它遍歷從最近端的列表。 [請注意用戶@andreas在下面的註釋中。]

但是，如果您打電話給LinkedList.remove(Object)，那麼會有第一個匹配節點的O（n）搜索。

同樣，對於ArrayList中，如果您使用的最後一個元素的索引調用ArrayList.remove(index)，那麼這就是O（1）。對於所有其他指數，有一個System.arrayCopy()調用可以是O（n） - 但完全跳過最後一個元素。

但是，如果你打電話ArrayList.remove(Object)，然後再有第一個匹配節點爲O（n）的搜索。

來源

2017-03-31 16:27:19

即使'linkedList.remove（lastIndex）'是_O（1）_，因爲['LinkedList']（https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html）將向後搜索索引：*索引到列表中的操作將從開始**或結束**遍歷列表，以較接近指定索引爲準。* – Andreas

@Andreas：好點;在上面的答案中加入了歸屬地。 –

@AndyThomas你也可以解釋我的問題的第二部分。謝謝 – user3747182

刪除鏈表的最後一個元素將採取爲O（n），如果它具有遍歷所有記錄，以到達終點。但是雙鏈接的java.util.LinkedList的實現並不僅僅保持頭部的引用，而且還保留尾部的引用並允許您刪除O（1）中的最後一個。它是在一個巧妙的方法來遍歷從開始或結束時，取其更接近指定索引

來源

2017-03-31 16:30:12

您的意思是「允許您刪除O（1）中的最後一個」？ – Andreas

這意味着它不會從頭開始遍歷列表，因爲它保留了尾部的引用，並且可以直接刪除它。 –

你的答案是誤導，因爲理論並沒有說刪除鏈表的最後一個元素需要O（n）。理論（和事實）說刪除任何元素需要O（1）。 *定位*要刪除的元素可能需要_O（n）_，這取決於定位方法以及鏈接列表是單連接還是雙連接，但答案中的第一條語句對此沒有提及，因此不正確，或者位於至少，誤導。 – Andreas

時間複雜度，同時刪除最後一個元素從ArrayList和LinkedList

回答

相關問題