試述ArrayList和LinkedList性能區別及使用場景

摘 要 ArrayList和LinkedList都是實現了List接口的容器類，用于存儲一系列的對象引用。他們都可以對元素的增刪改查進行操作。本文通過時間復雜度、空間復雜度來說明一下他們性能區別及應用場景。

關鍵詞Java List;ArrayList;LinkedList

概述

List 是一個有序、可重復的集合，集合中每個元素都有其對應的順序索引。它主要有兩個常用的實現類：ArrayList 類和LinkedList 類。

ArrayList 類實現了可變數組的大小，存儲在內的數據稱為元素。使用 ArrayList 創建的集合，允許對集合中的元素進行快速的隨機訪問，不過，向 ArrayList 中插入與刪除元素的速度相對較慢。

LinkedList 類采用鏈表結構保存對象。需要頻繁向集合中插入和刪除元素時，使用 LinkedList 類比 ArrayList 類效果高，但是 LinkedList 類隨機訪問元素的速度則相對較慢。

1時間復雜度

假設我們有一個很大的列表，它里面的元素已經排好序了，這個列表可能是ArrayList類型的也可能是LinkedList類型的，現在我們對這個列表來進行二分查找（binary search），比較列表是ArrayList和LinkedList時的查詢速度，看下面的程序：

public class TestList ...{

public static final int N=50000;

public static List values;

static...{

Integer vals[]=new Integer[N];

Random r=new Random（）;

for（int i=0，currval=0;i

vals=new Integer（currval）;

currval+=r.nextInt（100）+1;

}

values=Arrays.asList（vals）;

}

static long timeList（List lst）...{

long start=System.currentTimeMillis（）;

for（int i=0;i

int index=Collections.binarySearch（lst， values.get（i））;

if（index！=i）

System.out.println（“***錯誤***”）;

}

return System.currentTimeMillis（）-start;

}

public static void main（String args[]）...{

System.out.println（“ArrayList消耗時間：”+timeList（new ArrayList（values）））;

System.out.println（“LinkedList消耗時間：”+timeList（new LinkedList（values）））;

}

}

輸出是：ArrayList消耗時間：15

LinkedList消耗時間：2596

這個結果不是固定的，但是基本上ArrayList的時間要明顯小于LinkedList的時間。因此在這種情況下不宜用LinkedList。

2空間復雜度

在LinkedList中有一個私有的內部類，定義如下：

private static class Entry {

Object element;

Entry next;

Entry previous;

}

每個Entry對象reference列表中的一個元素，同時還有在LinkedList中它的上一個元素和下一個元素。一個有1000個元素的LinkedList對象將有1000個鏈接在一起的Entry對象，每個對象都對應于列表中的一個元素。這樣的話，在一個LinkedList結構中將有一個很大的空間開銷，因為它要存儲這1000個Entity對象的相關信息。

ArrayList使用一個內置的數組來存儲元素，這個數組的起始容量是10。如果沒有足夠的空間來存放新的元素，數組將不得不被重新進行分配以便能夠增加新的元素。對數組進行重新分配，將會導致性能急劇下降。

3ArrayList和LinkedList區別與使用場景

（1）如果應用程序對數據有較多的隨機訪問，ArrayList對象要優于LinkedList對象;

（2）如果應用程序有更多的插入或者刪除操作，較少的數據讀取，LinkedList對象要優于ArrayList對象;

（3）不過ArrayList的插入，刪除操作也不一定比LinkedList慢，如果在List靠近末尾的地方插入，那么ArrayList只需要移動較少的數據，而LinkedList則需要一直查找到列表尾部，反而耗費較多時間，這時ArrayList就比LinkedList要快。

作者簡介

黃明輝（1967-），浙江杭州;副教授，現就職單位：湖北三峽職業技術學院電子信息學院，研究方向：軟件開發。

參考文獻

[1] 耿祥義，張躍平著.Java 2實用教程（第5版）[M].北京：清華大學出版社，2017.

[2] 歐陽桂秀.試談Java中ArrayList類的使用[J].電腦編程技巧與維護，2012，（22）.