ArrayList和LinkedList區(qū)別、擴(kuò)容機(jī)制及底層實(shí)現(xiàn)

ArrayList

ArrayList的底層實(shí)現(xiàn)為數(shù)組存儲(chǔ)在內(nèi)存中，線程不同步。可通過(guò)數(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)的，沒(méi)有初始化大小，也沒(méi)有擴(kuò)容的機(jī)制。

ArrayList和LinkedList（常用方法、底層結(jié)構(gòu)及擴(kuò)容機(jī)制）

1.ArrayList解說(shuō)

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方法來(lái)擴(kuò)容（每次擴(kuò)容為1.5倍）

總的來(lái)說(shuō)：

ArrayList初始大小為10，每次1.5倍進(jìn)行擴(kuò)容；它的底層是用數(shù)組實(shí)現(xiàn)的，所以查詢速度相對(duì)LinkedList要快。

2.LinkedList解說(shuō)

（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支持序列化，能通過(guò)序列化去傳輸。

* LinkedList 是非同步的。

由于它的底層是用雙向鏈表實(shí)現(xiàn)的，所以它對(duì)元素的增加、刪除效率要比ArrayList好；它是一個(gè)雙向鏈表，沒(méi)有初始化大小，也沒(méi)有擴(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è)參考，也希望大家多多支持腳本之家。

最新評(píng)論