一般大家都知道ArrayList和LinkedList的大致區別
ArrayList是實現了基於動態數組的數據結構LinkedList基於鏈表的數據結構
對於隨機訪問get和setArrayList覺得優於LinkedList因為LinkedList要移動指針
對於新增和刪除操作add和removeLinedList比較占優勢因為ArrayList要移動數據
ArrayList和LinkedList是兩個集合 類用於存儲一系列的對象引用(references)例如我們可以用ArrayList來存儲一系列的String或者Integer那麼 ArrayList和LinkedList在性能上有什麼差別呢？什麼時候應該用ArrayList什麼時候又該用LinkedList呢？
一．時間復雜度
首先一點關鍵的是ArrayList的內部實現是基於基礎的對象數組的因此它使用get方法訪問列表中的任意一個元素時 (random access)它的速度要比LinkedList快LinkedList中的get方法是按照順序從列表的一端開始檢查直到另外一端對 LinkedList而言訪問列表中的某個指定元素沒有更快的方法了
假設我們有一個很大的列表它裡面的元素已經排好序了這個列表可能是ArrayList類型 的也可能是LinkedList類型的現在我們對這個列表來進行二分查找(binary search)比較列表是ArrayList和LinkedList時的查詢速度看下面的程序
Java代碼
package commangocitytest;
import javautilLinkedList;
import javautilList;
import javautilRandom;
import javautilArrayList;
import javautilArrays;
import javautilCollections;
public class TestList {
public static final int N=;
public static List values;
static{
Integer vals[]=new Integer[N];
Random r=new Random();
for(int i=currval=;i<N;i++){
vals=new Integer(currval);
currval+=rnextInt()+;
}
values=ArraysasList(vals);
}
static long timeList(List lst){
long start=SystemcurrentTimeMillis();
for(int i=;i<N;i++){
int index=CollectionsbinarySearch(lst valuesget(i));
if(index!=i)
Systemoutprintln(***錯誤***);
}
return SystemcurrentTimeMillis()start;
}
public static void main(String args[]){
Systemoutprintln(ArrayList消耗時間+timeList(new ArrayList(values)));
Systemoutprintln(LinkedList消耗時間+timeList(new LinkedList(values)));
}
}
我得到的輸出 是ArrayList消耗時間
LinkedList消耗時間
這個結果不是固定的但是基本上ArrayList的 時間要明顯小於LinkedList的時間因此在這種情況下不宜用LinkedList二分查找法使用的隨機訪問(random access)策略而LinkedList是不支持快速的隨機訪問的對一個LinkedList做隨機訪問所消耗的時間與這個list的大小是成比例 的而相應的在ArrayList中進行隨機訪問所消耗的時間是固定的
這是否表明ArrayList總是比LinkedList性能要好呢？這並不一定在某些情況 下LinkedList的表現要優於ArrayList有些算法在LinkedList中實現時效率更高比方說利用 Collectionsreverse方法對列表進行反轉時其性能就要好些
看這樣一個例子加入我們有一個列表要對其進行大量的插入和刪除操作在這種情況下 LinkedList就是一個較好的選擇請看如下一個極端的例子我們重復的在一個列表的開端插入一個元素
Java代碼
package commangocitytest;
import javautil*;
public class ListDemo {
static final int N=;
static long timeList(List list){
long start=SystemcurrentTimeMillis();
Object o = new Object();
for(int i=;i<N;i++)
listadd( o);
return SystemcurrentTimeMillis()start;
}
public static void main(String[] args) {
Systemoutprintln(ArrayList耗時+timeList(new ArrayList()));
Systemoutprintln(LinkedList耗時+timeList(new LinkedList()));
}
}
這時我的輸出結果是ArrayList耗時
LinkedList耗時
這和前面一個例子的結果截然相反當一個元素被加到ArrayList的最開端時所有已經存在的元素都會後 移這就意味著數據移動和復制上的開銷相反的將一個元素加到LinkedList的最開端只是簡單的未這個元素分配一個記錄然後調整兩個連接在 LinkedList的開端增加一個元素的開銷是固定的而在ArrayList的開端增加一個元素的開銷是與ArrayList的大小成比例的
二．空間復雜度
在LinkedList中有一個私有的內部類定義如下
Java代碼
private static class Entry {
Object element;
Entry next;
Entry previous;
}
每個Entry對象 reference列表中的一個元素同時還有在LinkedList中它的上一個元素和下一個元素一個有個元素的LinkedList對象將 有個鏈接在一起的Entry對象每個對象都對應於列表中的一個元素這樣的話在一個LinkedList結構中將有一個很大的空間開銷因為 它要存儲這個Entity對象的相關信息
ArrayList使用一個內置的數組來存儲元素這個數組的起始容量是當數組需要增長時新的容量按 如下公式獲得新容量=(舊容量*)/+也就是說每一次容量大概會增長%這就意味著如果你有一個包含大量元素的ArrayList對象 那麼最終將有很大的空間會被浪費掉這個浪費是由ArrayList的工作方式本身造成的如果沒有足夠的空間來存放新的元素數組將不得不被重新進行分 配以便能夠增加新的元素對數組進行重新分配將會導致性能急劇下降如果我們知道一個ArrayList將會有多少個元素我們可以通過構造方法來指定 容量我們還可以通過trimToSize方法在ArrayList分配完畢之後去掉浪費掉的空間
三．總結
ArrayList和LinkedList在性能上各 有優缺點都有各自所適用的地方總的說來可以描述如下
．對ArrayList和LinkedList而言在列表末尾增加一個元素所花的開銷都是固定的對 ArrayList而言主要是在內部數組中增加一項指向所添加的元素偶爾可能會導致對數組重新進行分配而對LinkedList而言這個開銷是 統一的分配一個內部Entry對象
．在ArrayList的 中間插入或刪除一個元素意味著這個列表中剩余的元素都會被移動而在LinkedList的中間插入或刪除一個元素的開銷是固定的
．LinkedList不 支持高效的隨機元素訪問
．ArrayList的空 間浪費主要體現在在list列表的結尾預留一定的容量空間而LinkedList的空間花費則體現在它的每一個元素都需要消耗相當的空間
可以這樣說當操作是在一列 數據的後面添加數據而不是在前面或中間並且需要隨機地訪問其中的元素時使用ArrayList會提供比較好的性能當你的操作是在一列數據的前面或中 間添加或刪除數據並且按照順序訪問其中的元素時就應該使用LinkedList了
From:http://tw.wingwit.com/Article/program/Java/hx/201311/26293.html
