ArrayList和LinkedList的區(qū)別、擴(kuò)容機(jī)制以及底層的實(shí)現(xiàn)方式
ArrayList和LinkedList區(qū)別、擴(kuò)容機(jī)制及底層實(shí)現(xiàn)
ArrayList
ArrayList的底層實(shí)現(xiàn)為數(shù)組存儲(chǔ)在內(nèi)存中,線程不同步??赏ㄟ^數(shù)組下標(biāo)的形式進(jìn)行查找,所以在查詢方面的效率較為出色,常用在查詢較多的情景下。
LinkedList
LinkedList的底層實(shí)現(xiàn)為鏈表形式,也為線程不同步。而鏈表的底層也決定了它在查詢方面不如數(shù)組底層的ArrayList而在指定位置插入等修改操作下,性能優(yōu)于ArrayList。
Vestor
另外還有Vestor,Vestor也是和ArrayList、LinkedList一樣實(shí)現(xiàn)了java.util.List接口。最大的區(qū)別在于Vestor是線程同步的,所以在效率方面不如另外兩者,適用于多線程項(xiàng)目中。
ArrayList的擴(kuò)容機(jī)制
/** ? ? ?* Constructs an empty list with the specified initial capacity. ? ? ?*/ ? ? public ArrayList(int initialCapacity) { ? ? super(); ? ? ? ? if (initialCapacity < 0) ? ? ? ? ? ? throw new IllegalArgumentException("Illegal Capacity: "+ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?initialCapacity); ? ? this.elementData = new Object[initialCapacity]; ? ? } ? ? /** ? ? ?* Constructs an empty list with an initial capacity of ten. ? ? ?*/ ? ? public ArrayList() { ? ? this(10); ? ? }
翻閱源碼會(huì)發(fā)現(xiàn)ArrayList初始化如果不指定大小的時(shí)候 初始大小為10。
? ? public void ensureCapacity(int minCapacity) { ? ? modCount++; ? ? int oldCapacity = elementData.length; ? ? if (minCapacity > oldCapacity) { ? ? ? ? Object oldData[] = elementData; ? ? ? ? int newCapacity = (oldCapacity * 3)/2 + 1; ? ? ? ? ? ? if (newCapacity < minCapacity) ? ? ? ? newCapacity = minCapacity; ? ? ? ? ? ? // minCapacity is usually close to size, so this is a win: ? ? ? ? ? ? elementData = Arrays.copyOf(elementData, newCapacity); ? ? } ? ? }
擴(kuò)容的規(guī)則也在源碼中有體現(xiàn),擴(kuò)容后的大小= 原始大小+原始大小/2 + 1。在進(jìn)行插入等操作的時(shí)候,如果判斷出大小不夠,會(huì)依據(jù)此方法進(jìn)行擴(kuò)容。(以上是JDK1.6版本的源碼,在JDK1.7中擴(kuò)容規(guī)則進(jìn)行了修改,改為了擴(kuò)容后的大小= 原始大小+原始大小/2)
LinkedList的擴(kuò)容機(jī)制
由于它的底層是用雙向鏈表實(shí)現(xiàn)的,沒有初始化大小,也沒有擴(kuò)容的機(jī)制。
ArrayList和LinkedList(常用方法、底層結(jié)構(gòu)及擴(kuò)容機(jī)制)
1.ArrayList解說
ArrayList初始長(zhǎng)度為0(這里以jdk1.8為例),是一個(gè)Object類型的空數(shù)組,如下
當(dāng)?shù)谝淮握{(diào)用add后,長(zhǎng)度變?yōu)?0
當(dāng)數(shù)組首次擴(kuò)容的10個(gè)空間用完需要擴(kuò)容后,會(huì)第二次走grow方法來擴(kuò)容(每次擴(kuò)容為1.5倍)
總的來說:
ArrayList初始大小為10,每次1.5倍進(jìn)行擴(kuò)容;它的底層是用數(shù)組實(shí)現(xiàn)的,所以查詢速度相對(duì)LinkedList要快。
2.LinkedList解說
(1)
* LinkedList 是一個(gè)繼承于AbstractSequentialList的雙向鏈表。它也可以被當(dāng)作堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行操作。
* LinkedList 實(shí)現(xiàn) List 接口,能對(duì)它進(jìn)行隊(duì)列操作。
* LinkedList 實(shí)現(xiàn) Deque 接口,即能將LinkedList當(dāng)作雙端隊(duì)列使用。
* LinkedList 實(shí)現(xiàn)了Cloneable接口,即覆蓋了函數(shù)clone(),能克隆。
* LinkedList 實(shí)現(xiàn)java.io.Serializable接口,這意味著LinkedList支持序列化,能通過序列化去傳輸。
* LinkedList 是非同步的。
由于它的底層是用雙向鏈表實(shí)現(xiàn)的,所以它對(duì)元素的增加、刪除效率要比ArrayList好;它是一個(gè)雙向鏈表,沒有初始化大小,也沒有擴(kuò)容的機(jī)制,就是一直在前面或者后面新增就好。
(2)LinkedList底層的數(shù)據(jù)結(jié)構(gòu)是基于雙向循環(huán)鏈表的,且頭結(jié)點(diǎn)中不存放數(shù)據(jù),如下:
private transient Entry<E> header = new Entry<E>(null, null, null); private transient int size = 0;
header是雙向鏈表的頭節(jié)點(diǎn),它是雙向鏈表節(jié)點(diǎn)所對(duì)應(yīng)的類Entry的實(shí)例。Entry中包含成員變量: previous, next, element。其中,previous是該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn),next是該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn),element是該
節(jié)點(diǎn)所包含的值。size是雙向鏈表中節(jié)點(diǎn)實(shí)例的個(gè)數(shù)。
總之,addBefore(E e,Entry<E> entry)實(shí)現(xiàn)在entry之前插入由e構(gòu)造的新節(jié)點(diǎn)。而add(E e)實(shí)現(xiàn)在header節(jié)點(diǎn)之前插入由e構(gòu)造的新節(jié)點(diǎn)。為了便于理解,下面給出插入節(jié)點(diǎn)的示意圖。
總結(jié)
以上為個(gè)人經(jīng)驗(yàn),希望能給大家一個(gè)參考,也希望大家多多支持腳本之家。
相關(guān)文章
java文件下載設(shè)置中文名稱的實(shí)例(response.addHeader)
下面小編就為大家分享一篇java文件下載設(shè)置中文名稱的實(shí)例(response.addHeader),具有很好的參考價(jià)值,希望對(duì)大家有所幫助2017-12-12Spring?this調(diào)用當(dāng)前類方法無法攔截的示例代碼
這篇文章主要介紹了Spring?this調(diào)用當(dāng)前類方法無法攔截,通過debug 查看這個(gè)proxyService1 和this的區(qū)別,本文通過示例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-03-03IntelliJ IDEA中使用mybatis-generator的示例
這篇文章主要介紹了IntelliJ IDEA中使用mybatis-generator,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-04-04Java面試題 從源碼角度分析HashSet實(shí)現(xiàn)原理
這篇文章主要介紹了Java面試題 從源碼角度分析HashSet實(shí)現(xiàn)原理?,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-07-07Java批量向PDF文件中添加圖像水印實(shí)現(xiàn)細(xì)節(jié)
這篇文章主要為大家介紹了Java批量向PDF文件中添加圖像水印實(shí)現(xiàn)細(xì)節(jié),有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-05-05