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

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

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

概述

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

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

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

1時(shí)間復(fù)雜度

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

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（“***錯(cuò)誤***”）;

}

return System.currentTimeMillis（）-start;

}

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

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

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

}

}

輸出是：ArrayList消耗時(shí)間：15

LinkedList消耗時(shí)間：2596

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

2空間復(fù)雜度

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

private static class Entry {

Object element;

Entry next;

Entry previous;

}

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

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

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

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

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

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

作者簡(jiǎn)介

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

參考文獻(xiàn)

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

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