LinkedList vs. ArrayList

今天看到的一個(gè)Blog上的內(nèi)容，我把大致內(nèi)容摘錄下來(lái)，作為備忘。

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

 

首先看一下LinkedList和ArrayList的繼承關(guān)系。

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

 

兩者都實(shí)現(xiàn)List接口，前者實(shí)現(xiàn)RandomAccess接口，后者實(shí)現(xiàn)Queue接口。

 

ArrayList

ArrayList其實(shí)是包裝了一個(gè)數(shù)組 Object[]，當(dāng)實(shí)例化一個(gè)ArrayList時(shí)，一個(gè)數(shù)組也被實(shí)例化，當(dāng)向ArrayList中添加對(duì)象是，數(shù)組的大小也相應(yīng)的改變。這樣就帶來(lái)以下有缺點(diǎn)：

快速隨即訪問 你可以隨即訪問每個(gè)元素而不用考慮性能問題，通過(guò)調(diào)用get(i)方法來(lái)訪問下標(biāo)為i的數(shù)組元素。

向其中添加對(duì)象速度慢 當(dāng)你創(chuàng)建數(shù)組是并不能確定其容量，所以當(dāng)改變這個(gè)數(shù)組時(shí)就必須在內(nèi)存中做很多事情。

操作其中對(duì)象的速度慢 當(dāng)你要想數(shù)組中任意兩個(gè)元素中間添加對(duì)象時(shí)，數(shù)組需要移動(dòng)所有后面的對(duì)象。

 

LinkedList

LinkedList是通過(guò)節(jié)點(diǎn)直接彼此連接來(lái)實(shí)現(xiàn)的。每一個(gè)節(jié)點(diǎn)都包含前一個(gè)節(jié)點(diǎn)的引用，后一個(gè)節(jié)點(diǎn)的引用和節(jié)點(diǎn)存儲(chǔ)的值。當(dāng)一個(gè)新節(jié)點(diǎn)插入時(shí)，只需要修改其中保持先后關(guān)系的節(jié)點(diǎn)的引用即可，當(dāng)刪除記錄時(shí)也一樣。這樣就帶來(lái)以下有缺點(diǎn)：

操作其中對(duì)象的速度快 只需要改變連接，新的節(jié)點(diǎn)可以在內(nèi)存中的任何地方

不能隨即訪問 雖然存在get()方法，但是這個(gè)方法是通過(guò)遍歷接點(diǎn)來(lái)定位的所以速度慢。

 

一些結(jié)論：

當(dāng)一些被定義好的數(shù)據(jù)需要放到與數(shù)組對(duì)應(yīng)的List中，ArrayList是很好的選擇，因?yàn)樗梢詣?dòng)態(tài)變化，但是不要在整個(gè)應(yīng)用程序用頻繁的使用。當(dāng)你要很方便的操作其中的數(shù)據(jù)而不用隨即訪問時(shí)LinkList是很好的選擇。如果你要頻繁隨即訪問建議使用數(shù)組。

另外一個(gè)我沒有提到的是關(guān)于Queue。LinkedList的實(shí)現(xiàn)使其具有很好的可擴(kuò)展性，可以方便的在開始和結(jié)尾添加刪除節(jié)點(diǎn)。所以LinkedList很適合用來(lái)實(shí)現(xiàn)Queue和Stack，盡管在Java5種已經(jīng)有了一個(gè)Stack的實(shí)現(xiàn)。

 

 

以上是原文中的觀點(diǎn)，但是在回復(fù)中也有人反對(duì)：

LinkedList有以下缺陷：

對(duì)象分配-每添加一項(xiàng)就分配一個(gè)對(duì)象

回收垃圾-對(duì)象分配的結(jié)果

隨即訪問慢-設(shè)計(jì)上的原因

添加刪除慢-因?yàn)槭紫纫业轿恢?/SPAN>

應(yīng)該使用LinkedList的情況非常少。大多數(shù)的建議使使用LinkedList是錯(cuò)誤的。

JDK的Stack就是用數(shù)組來(lái)實(shí)現(xiàn)的。

在多數(shù)時(shí)間里你并不是向List中間添加數(shù)據(jù)，而是向在結(jié)尾添加，這樣的操作ArrayList表現(xiàn)的很好。

LinkedList在實(shí)現(xiàn)Queue時(shí)很有用。

 

然后是原文作者提供的一些數(shù)據(jù)：

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