對于通過索引訪問和更新元素，LinkedList實現的性能開銷略大一點，因為訪問任意一個索引都要求跨越多個節點。插入元素時除了有跨越多個節點的性能開銷之外，還要有另外一個開銷，即創建節點對象的開銷。在優勢方面，LinkedList實現的插入和刪除操作沒有其他開銷，因此，插入-刪除開銷幾乎完全依賴于插入-刪除點離集合末尾的遠近。
三、性能測試
這些類有許多不同的功能可以進行測試。LinkedList應用比較頻繁，因為人們認為它在隨機插入和刪除操作時具有較好的性能。所以，下面我分析的重點將是插入操作的性能，即，構造集合。我測試并比較了LinkedList和ArrayList，因為這兩者都是非同步的。
插入操作的速度主要由集合的大小和元素插入的位置決定。當插入點的位置在集合的兩端和中間時，最差的插入性能和最好的插入性能都有機會出現。因此，我選擇了三個插入位置(集合的開頭、末尾和中間)，三種典型的集合大�。褐械�(100個元素)，大型(10,000個元素)，超大型(1,000,000個元素)。
在本文的測試中，我使用的是JAVA SDK 1.2.0和1.3.0系列的SUN JVM。此外，我還用HOTSPOT JVM 2.0進行了測試，這個版本可以在1.3.0 SDK找到。在下面的表格中，各個測量得到的時間都以其中一次SDK 1.2 VM上的測試時間(表格中顯示為100%的單元)為基準顯示。測試期間使用了默認的JVM配置，即啟用了JIT編譯，因此對于所有JVM，堆空間都必須進行擴展，以避免內存溢出錯誤。表格中記錄的時間是多次測試的平均時間。為了避免垃圾收集的影響，在各次測試之間我強制進行了完全的內存清理(參見測試源代碼了解詳情)。磁盤監測確保磁盤分頁不會在測試過程中出現(任何測試，如果它顯示出嚴重的磁盤分頁操作，則被丟棄)。所有顯示出數秒應答時間的速度太慢的測試都重復進行，直至記錄到一個明顯合理的時間。 表1：構造一個中等大小的集合(100個元素)。括號中的數字針對預先確定大小的集合。
1.2 JVM1.3 JVMHotSpot 2.0 JVM
總是插入到ArrayList的開頭100% (48.0%)184.9% (152.0%)108.0% (66.7%)
總是插入到LinkedList的開頭135.5%109.1%85.3%
總是插入到ArrayList的中間130.0% (40.6%)187.4% (158.0%)84.7% (46.0%)
總是插入到LinkedList的中間174.0%135.0%102.3%
總是插入到ArrayList的末尾63.3% (20.7%)65.9% (25.0%)60.3% (29.3%)
總是插入到LinkedList的末尾106.7%86.3%80.3%
對于規模較小的集合，ArrayList和LinkedList的性能很接近。當元素插入到集合的末尾時，即追加元素時，ArrayList的性能出現了突變。然而，追加元素是ArrayList特別為其優化的一個操作：如果你只想要一個固定大小的靜態集合，Java數組(例如Object[])比任何集合對象都具有更好的性能。除了追加操作，測量得到的時間數據差別不是很大，它們反映了各個JVM的優化程度，而不是其他什么東西。
例如，對于把元素插入到集合的開始位置來說(表1的前兩行)，HotSpot 2.0 JVM加LinkedList具有最好的性能(85.3%)，處于第二位的是 1.2 JVM加ArrayList(100%)。這兩個結果顯示出，1.2中簡單的JIT編譯器在執行迭代和復制數組等簡單的操作時具有很高的效率。在HotSpot中復雜的JVM加上優化的編譯器能夠改進復雜操作的性能，比如對象創建(創建LinkedList節點)，并能夠利用代碼內嵌(code-inlining)的優勢。1.3 JVM的結果似乎顯示出，在簡單操作方面它的性能有著很大的不足，這一點很可能在以后的JVM版本中得到改進。
文章來源于領測軟件測試網 http://www.kjueaiud.com/
