LinkedList vs. ArrayList

今天看到的一個Blog上的內容，我把大致內容摘錄下來，作為備忘。

http://javachaos.crazyredpanda.com/?p=99

 

首先看一下LinkedList和ArrayList的繼承關系。

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable

      

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Queue<E>, Cloneable, Serializable

 

兩者都實現List接口，前者實現RandomAccess接口，后者實現Queue接口。

 

ArrayList

ArrayList其實是包裝了一個數組 Object[]，當實例化一個ArrayList時，一個數組也被實例化，當向ArrayList中添加對象是，數組的大小也相應的改變。這樣就帶來以下有缺點：

快速隨即訪問 你可以隨即訪問每個元素而不用考慮性能問題，通過調用get(i)方法來訪問下標為i的數組元素。

向其中添加對象速度慢 當你創建數組是并不能確定其容量，所以當改變這個數組時就必須在內存中做很多事情。

操作其中對象的速度慢 當你要想數組中任意兩個元素中間添加對象時，數組需要移動所有后面的對象。

 

LinkedList

LinkedList是通過節點直接彼此連接來實現的。每一個節點都包含前一個節點的引用，后一個節點的引用和節點存儲的值。當一個新節點插入時，只需要修改其中保持先后關系的節點的引用即可，當刪除記錄時也一樣。這樣就帶來以下有缺點：

操作其中對象的速度快 只需要改變連接，新的節點可以在內存中的任何地方

不能隨即訪問 雖然存在get()方法，但是這個方法是通過遍歷接點來定位的所以速度慢。

 

一些結論：

當一些被定義好的數據需要放到與數組對應的List中，ArrayList是很好的選擇，因為它可以動態變化，但是不要在整個應用程序用頻繁的使用。當你要很方便的操作其中的數據而不用隨即訪問時LinkList是很好的選擇。如果你要頻繁隨即訪問建議使用數組。

另外一個我沒有提到的是關于Queue。LinkedList的實現使其具有很好的可擴展性，可以方便的在開始和結尾添加刪除節點。所以LinkedList很適合用來實現Queue和Stack，盡管在Java5種已經有了一個Stack的實現。

 

 

以上是原文中的觀點，但是在回復中也有人反對：

LinkedList有以下缺陷：

對象分配-每添加一項就分配一個對象

回收垃圾-對象分配的結果

隨即訪問慢-設計上的原因

添加刪除慢-因為首先要找到位置

應該使用LinkedList的情況非常少。大多數的建議使使用LinkedList是錯誤的。

JDK的Stack就是用數組來實現的。

在多數時間里你并不是向List中間添加數據，而是向在結尾添加，這樣的操作ArrayList表現的很好。

LinkedList在實現Queue時很有用。

 

然后是原文作者提供的一些數據：

addFirst() to array list took 1422

addFirst() to linked list using general methods took 16

addFirst() to linked list using linked list methods took 16

addLast() to array list took 16

addLast() to linked list using general methods took 15

addLast() to linked list using linked list methods took 0

addMiddleTest() to array list took 735

addMiddleTest() to linked list using general methods took 11688

addMiddleTest() to linked list using linked list methods took 8406

removeFirst() to array list took 1422

removeFirst() to linked list using general methods took 0

removeFirst() to linked list using linked list methods took 0

removeLast() to array list took 0

removeLast() to linked list using general methods took 0

removeLast() to linked list using linked list methods took 0

removeMiddle() to array list took 734

removeMiddle() to linked list using general methods took 7594

removeMiddle() to linked list using linked list methods took 7719

fetchFirst() to array list took 0

fetchFirst() to linked list using general methods took 0

fetchFirst() to linked list using linked list methods took 0

fetchLast() to array list took 16

fetchLast() to linked list using general methods took 0

fetchLast() to linked list using linked list methods took 0

fetchMiddle() to array list took 15

fetchMiddle() to linked list using general methods took 9156

fetchMiddle() to linked list using linked list methods took 9234