試述ArrayList和LinkedList性能區(qū)別及使用場景

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

關(guān)鍵詞Java List;ArrayList;LinkedList

概述

List 是一個有序、可重復(fù)的集合，集合中每個元素都有其對應(yīng)的順序索引。它主要有兩個常用的實(shí)現(xiàn)類：ArrayList 類和LinkedList 類。

ArrayList 類實(shí)現(xiàn)了可變數(shù)組的大小，存儲在內(nèi)的數(shù)據(jù)稱為元素。使用 ArrayList 創(chuàng)建的集合，允許對集合中的元素進(jìn)行快速的隨機(jī)訪問，不過，向 ArrayList 中插入與刪除元素的速度相對較慢。

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

1時間復(fù)雜度

假設(shè)我們有一個很大的列表，它里面的元素已經(jīng)排好序了，這個列表可能是ArrayList類型的也可能是LinkedList類型的，現(xiàn)在我們對這個列表來進(jìn)行二分查找（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

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

2空間復(fù)雜度

在LinkedList中有一個私有的內(nèi)部類，定義如下：

private static class Entry {

Object element;

Entry next;

Entry previous;

}

每個Entry對象reference列表中的一個元素，同時還有在LinkedList中它的上一個元素和下一個元素。一個有1000個元素的LinkedList對象將有1000個鏈接在一起的Entry對象，每個對象都對應(yīng)于列表中的一個元素。這樣的話，在一個LinkedList結(jié)構(gòu)中將有一個很大的空間開銷，因?yàn)樗鎯@1000個Entity對象的相關(guān)信息。

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

3ArrayList和LinkedList區(qū)別與使用場景

（1）如果應(yīng)用程序?qū)?shù)據(jù)有較多的隨機(jī)訪問，ArrayList對象要優(yōu)于LinkedList對象;

（2）如果應(yīng)用程序有更多的插入或者刪除操作，較少的數(shù)據(jù)讀取，LinkedList對象要優(yōu)于ArrayList對象;

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

作者簡介

黃明輝（1967-），浙江杭州;副教授，現(xiàn)就職單位：湖北三峽職業(yè)技術(shù)學(xué)院電子信息學(xué)院，研究方向：軟件開發(fā)。

參考文獻(xiàn)

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

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