ArrayList和LinkedList如何實(shí)現(xiàn)的？我看你還有機(jī)會！
前言
說真的，在 Java 使用最多的集合類中，List 絕對占有一席之地的，它和 Map 一樣適用于很多場景，非常方便我們的日常開發(fā)，畢竟存儲一個列表的需求隨處可見。盡管如此，還是有很多同學(xué)沒有弄明白 List 中 ArrayList 和 LinkedList 有什么區(qū)別，這簡直太遺憾了，這兩者其實(shí)都是數(shù)據(jù)結(jié)構(gòu)中的基礎(chǔ)內(nèi)容，這篇文章會從基礎(chǔ)概念開始，分析兩者在 Java 中的具體源碼實(shí)現(xiàn)，尋找兩者的不同之處，最后思考它們使用時(shí)的注意事項(xiàng)。
這篇文章會包含以下內(nèi)容。
介紹線性表的概念，詳細(xì)介紹線性表中數(shù)組和鏈表的數(shù)據(jù)結(jié)構(gòu)。
進(jìn)行 ArrayList 的源碼分析，比如存儲結(jié)構(gòu)、擴(kuò)容機(jī)制、數(shù)據(jù)新增、數(shù)據(jù)獲取等。
進(jìn)行 LinkedList 的源碼分析，比如它的存儲結(jié)構(gòu)、數(shù)據(jù)插入、數(shù)據(jù)查詢、數(shù)據(jù)刪除和 LinkedList 作為隊(duì)列的使用方式等。
進(jìn)行 ArrayList 和 LinkedList 的總結(jié)。
?
線性表
要研究 ArrayList 和 LinkedList ，首先要弄明白什么是線性表，這里引用百度百科的一段文字。
線性表是最基本、最簡單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表（linear list）是數(shù)據(jù)結(jié)構(gòu)的一種，一個線性表是n個具有相同特性的數(shù)據(jù)元素的有限序列。
你肯定看到了，線性表在數(shù)據(jù)結(jié)構(gòu)中是一種最基本、最簡單、最常用的數(shù)據(jù)結(jié)構(gòu)。它將數(shù)據(jù)一個接一個的排成一條線（可能邏輯上），也因此線性表上的每個數(shù)據(jù)只有前后兩個方向，而在數(shù)據(jù)結(jié)構(gòu)中，數(shù)組、鏈表、棧、隊(duì)列都是線性表。你可以想象一下整整齊齊排隊(duì)的樣子。
看到這里你可能有疑問了，有線性表，那么肯定有非線性表嘍？沒錯。二叉樹和圖就是典型的非線性結(jié)構(gòu)了。不要被這些花里胡哨的圖嚇到，其實(shí)這篇文章非常簡單，希望同學(xué)耐心看完點(diǎn)個贊。
數(shù)組
既然知道了什么是線性表，那么理解數(shù)組也就很容易了，首先數(shù)組是線性表的一種實(shí)現(xiàn)。數(shù)組是由相同類型元素組成的一種數(shù)據(jù)結(jié)構(gòu)，數(shù)組需要分配一段連續(xù)的內(nèi)存用來存儲。注意關(guān)鍵詞，相同類型，連續(xù)內(nèi)存，像這樣。
不好意思放錯圖了，像這樣。
上面的圖可以很直觀的體現(xiàn)數(shù)組的存儲結(jié)構(gòu)，因?yàn)閿?shù)組內(nèi)存地址連續(xù)，元素類型固定，所有具有快速查找某個位置的元素的特性；同時(shí)也因?yàn)閿?shù)組需要一段連續(xù)內(nèi)存，所以長度在初始化長度已經(jīng)固定，且不能更改。Java 中的 ArrayList 本質(zhì)上就是一個數(shù)組的封裝。
鏈表
鏈表也是一種線性表，和數(shù)組不同的是鏈表不需要連續(xù)的內(nèi)存進(jìn)行數(shù)據(jù)存儲，而是在每個節(jié)點(diǎn)里同時(shí)存儲下一個節(jié)點(diǎn)的指針，又要注意關(guān)鍵詞了，每個節(jié)點(diǎn)都有一個指針指向下一個節(jié)點(diǎn)。那么這個鏈表應(yīng)該是什么樣子呢？看圖。
哦不，放錯圖了，是這樣。
上圖很好的展示了鏈表的存儲結(jié)構(gòu)，圖中每個節(jié)點(diǎn)都有一個指針指向下一個節(jié)點(diǎn)位置，這種我們稱為單向鏈表；還有一種鏈表在每個節(jié)點(diǎn)上還有一個指針指向上一個節(jié)點(diǎn)，這種鏈表我們稱為雙向鏈表。圖我就不畫了，像下面這樣。
可以發(fā)現(xiàn)鏈表不必連續(xù)內(nèi)存存儲了，因?yàn)殒湵硎峭ㄟ^節(jié)點(diǎn)指針進(jìn)行下一個或者上一個節(jié)點(diǎn)的，只要找到頭節(jié)點(diǎn)，就可以以此找到后面一串的節(jié)點(diǎn)。不過也因此，鏈表在查找或者訪問某個位置的節(jié)點(diǎn)時(shí)，需要**O(n)的時(shí)間復(fù)雜度。但是插入數(shù)據(jù)時(shí)可以達(dá)到O(1)**的復(fù)雜度，因?yàn)橹恍枰薷墓?jié)點(diǎn)指針指向。
?
ArratList
上面介紹了線性表的概念，并舉出了兩個線性表的實(shí)際實(shí)現(xiàn)例子，既數(shù)組和鏈表。在 Java 的集合類 ArrayList 里，實(shí)際上使用的就是數(shù)組存儲結(jié)構(gòu)，ArrayList 對 Array 進(jìn)行了封裝，并增加了方便的插入、獲取、擴(kuò)容等操作。因?yàn)?ArrayList 的底層是數(shù)組，所以存取非常迅速，但是增刪時(shí)，因?yàn)橐苿雍竺娴脑匚恢茫栽鰟h效率相對較低。那么它具體是怎么實(shí)現(xiàn)的呢？不妨深入源碼一探究竟。
ArrayList 存儲結(jié)構(gòu)
查看 ArrayList 的源碼可以看到它就是一個簡單的數(shù)組，用來數(shù)據(jù)存儲。
/**
?*?The?array?buffer?into?which?the?elements?of?the?ArrayList?are?stored.
?*?The?capacity?of?the?ArrayList?is?the?length?of?this?array?buffer.?Any
?*?empty?ArrayList?with?elementData?==?DEFAULTCAPACITY_EMPTY_ELEMENTDATA
?*?will?be?expanded?to?DEFAULT_CAPACITY?when?the?first?element?is?added.
?*/
transient?Object[]?elementData;?//?non-private?to?simplify?nested?class?access
/**
?*?Shared?empty?array?instance?used?for?default?sized?empty?instances.?We
?*?distinguish?this?from?EMPTY_ELEMENTDATA?to?know?how?much?to?inflate?when
?*?first?element?is?added.
?*/
private?static?final?Object[]?DEFAULTCAPACITY_EMPTY_ELEMENTDATA?=?{};
/**
?*?Default?initial?capacity.
?*/
private?static?final?int?DEFAULT_CAPACITY?=?10;
通過上面的注釋了解到，ArrayList 無參構(gòu)造時(shí)是會共享一個長度為 0 的數(shù)組 DEFAULTCAPACITY_EMPTY_ELEMENTDATA. 只有當(dāng)?shù)谝粋€元素添加時(shí)才會第一次擴(kuò)容，這樣也防止了創(chuàng)建對象時(shí)更多的內(nèi)存浪費(fèi)。
ArrayList 擴(kuò)容機(jī)制
我們都知道數(shù)組的大小一但確定是不能改變的，那么 ArrayList 明顯可以不斷的添加元素，它的底層又是數(shù)組，它是怎么實(shí)現(xiàn)的呢？從上面的 ArrayList 存儲結(jié)構(gòu)以及注釋中了解到，ArrayList 在初始化時(shí)，是共享一個長度為 0 的數(shù)組的，當(dāng)?shù)谝粋€元素添加進(jìn)來時(shí)會進(jìn)行第一次擴(kuò)容，我們可以想像出 ArrayList 每當(dāng)空間不夠使用時(shí)就會進(jìn)行一次擴(kuò)容，那么擴(kuò)容的機(jī)制是什么樣子的呢?
依舊從源碼開始，追蹤 add() 方法的內(nèi)部實(shí)現(xiàn)。
/**
?*?Appends?the?specified?element?to?the?end?of?this?list.
?*
?*?@param?e?element?to?be?appended?to?this?list
?*?@return?true?(as?specified?by?{@link?Collection#add})
?*/
public?boolean?add(E?e)?{
????ensureCapacityInternal(size?+?1);??//?Increments?modCount!!
????elementData[size++]?=?e;
????return?true;
}
//?開始檢查當(dāng)前插入位置時(shí)數(shù)組容量是否足夠
private?void?ensureCapacityInternal(int?minCapacity)?{
????//?ArrayList?是否未初始化，未初始化是則初始化?ArrayList?，容量給?10.
????if?(elementData?==?DEFAULTCAPACITY_EMPTY_ELEMENTDATA)?{
????????minCapacity?=?Math.max(DEFAULT_CAPACITY,?minCapacity);
????}
????ensureExplicitCapacity(minCapacity);
}
//?比較插入?index?是否大于當(dāng)前數(shù)組長度，大于就?grow?進(jìn)行擴(kuò)容
private?void?ensureExplicitCapacity(int?minCapacity)?{
????modCount++;
????//?overflow-conscious?code
????if?(minCapacity?-?elementData.length?>?0)
????????grow(minCapacity);
}
/**
?*?Increases?the?capacity?to?ensure?that?it?can?hold?at?least?the
?*?number?of?elements?specified?by?the?minimum?capacity?argument.
?*
?*?@param?minCapacity?the?desired?minimum?capacity
?*/
private?void?grow(int?minCapacity)?{
????//?overflow-conscious?code
????int?oldCapacity?=?elementData.length;
????//?擴(kuò)容規(guī)則是當(dāng)前容量?+?當(dāng)前容量右移1位。也就是1.5倍。
????int?newCapacity?=?oldCapacity?+?(oldCapacity?>>?1);
????if?(newCapacity?-?minCapacity?0)
????????newCapacity?=?minCapacity;
????//?是否大于?Int?最大值，也就是容量最大值
????if?(newCapacity?-?MAX_ARRAY_SIZE?>?0)
????????newCapacity?=?hugeCapacity(minCapacity);
????//?minCapacity?is?usually?close?to?size,?so?this?is?a?win:
????//?拷貝元素到擴(kuò)充后的新的?ArrayList
????elementData?=?Arrays.copyOf(elementData,?newCapacity);
}
通過源碼發(fā)現(xiàn)擴(kuò)容邏輯還是比較簡單的，整理下具體的擴(kuò)容流程如下：
開始檢查當(dāng)前插入位置時(shí)數(shù)組容量是否足夠 ArrayList 是否未初始化，未初始化是則初始化 ArrayList ，容量給 10. 判斷當(dāng)前要插入的下標(biāo)是否大于容量 不大于，插入新增元素，新增流程完畢。 如果所需的容量大于當(dāng)前容量，開始擴(kuò)充。 擴(kuò)容規(guī)則是當(dāng)前容量 + 當(dāng)前容量右移1位。也就是1.5倍。 int newCapacity = oldCapacity + (oldCapacity >> 1);如果擴(kuò)充之后還是小于需要的最小容量，則把所需最小容量作為容量。 如果容量大于默認(rèn)最大容量，則使用 最大值 Integer 作為容量。 拷貝老數(shù)組元素到擴(kuò)充后的新數(shù)組 插入新增元素，新增流程完畢。
ArrayList ?數(shù)據(jù)新增
public?boolean?add(E?e)?{
????ensureCapacityInternal(size?+?1);??//?Increments?modCount!!
????elementData[size++]?=?e;?//?直接賦值
????return?true;
}
/**
?*?Inserts?the?specified?element?at?the?specified?position?in?this
?*?list.?Shifts?the?element?currently?at?that?position?(if?any)?and
?*?any?subsequent?elements?to?the?right?(adds?one?to?their?indices).
?*
?*?@param?index?index?at?which?the?specified?element?is?to?be?inserted
?*?@param?element?element?to?be?inserted
?*?@throws?IndexOutOfBoundsException?{@inheritDoc}
?*/
public?void?add(int?index,?E?element)?{
????rangeCheckForAdd(index);
????ensureCapacityInternal(size?+?1);??//?Increments?modCount!!
?????//?指定下標(biāo)開始所有元素后移一位
????System.arraycopy(elementData,?index,?elementData,?index?+?1,size?-?index);
????elementData[index]?=?element;
????size++;
}
ArrayList 數(shù)據(jù)獲取
public?E?get(int?index)?{
????rangeCheck(index);
????return?elementData(index);
}
E?elementData(int?index)?{
????return?(E)?elementData[index];
}
?
LinkedList
LinkedList 存儲結(jié)構(gòu)
transient?int?size?=?0;
/**
?*?Pointer?to?first?node.
?*?Invariant:?(first?==?null?&&?last?==?null)?||
?*????????????(first.prev?==?null?&&?first.item?!=?null)
?*/
transient?Node?first;
/**
?*?Pointer?to?last?node.
?*?Invariant:?(first?==?null?&&?last?==?null)?||
?*????????????(last.next?==?null?&&?last.item?!=?null)
?*/
transient?Node?last;
/**
?*?Constructs?an?empty?list.
?*/
public?LinkedList()?{
}
private?static?class?Node<E>?{
????E?item;
????Node?next;
????Node?prev;
????Node(Node?prev,?E?element,?Node ?next)?{
????????this.item?=?element;
????????this.next?=?next;
????????this.prev?=?prev;
????}
}
LinkedList 數(shù)據(jù)獲取
public?E?get(int?index)?{
????checkElementIndex(index);
????return?node(index).item;
}
/**
?*?Returns?the?(non-null)?Node?at?the?specified?element?index.
?*/
//?遍歷查找?index?位置的節(jié)點(diǎn)信息
Node?node(int?index)? {
????//?assert?isElementIndex(index);
????//?這里判斷?index?是在當(dāng)前鏈表的前半部分還是后半部分，然后決定是從
????// first 向后查找還是從 last 向前查找。
????if?(index?>?1))?{
????????Node?x?=?first;
????????for?(int?i?=?0;?i?????????????x?=?x.next;
????????return?x;
????}?else?{
????????Node?x?=?last;
????????for?(int?i?=?size?-?1;?i?>?index;?i--)
????????????x?=?x.prev;
????????return?x;
????}
}
LinkedList 數(shù)據(jù)新增
尾部插入 public?boolean?add(E?e)?{
????linkLast(e);
????return?true;
}
void?linkLast(E?e)?{
????final?Node?l?=?last;
????//?新節(jié)點(diǎn)，prev?為當(dāng)前尾部節(jié)點(diǎn)，e為元素值，next?為?null，
????final?Node?newNode?=?new?Node<>(l,?e,?null);
????last?=?newNode;
????if?(l?==?null)
????????first?=?newNode;
????else
?????????//?目前的尾部節(jié)點(diǎn)?next?指向新的節(jié)點(diǎn)
????????l.next?=?newNode;
????size++;
????modCount++;
}默認(rèn)的 add 方式就是尾部新增了，尾部新增的邏輯很簡單，只需要創(chuàng)建一個新的節(jié)點(diǎn)，新節(jié)點(diǎn)的 prev 設(shè)置現(xiàn)有的末尾節(jié)點(diǎn)，現(xiàn)有的末尾 Node 指向新節(jié)點(diǎn) Node，新節(jié)點(diǎn)的 next 設(shè)為 null 即可。 中間新增 下面是在指定位置新增元素，涉及到的源碼部分。 public?void?add(int?index,?E?element)?{
????checkPositionIndex(index);
????if?(index?==?size)
????????//?如果位置就是當(dāng)前鏈表尾部，直接尾插
????????linkLast(element);
????else
????????//?獲取?index?位置的節(jié)點(diǎn)，插入新的元素
????????linkBefore(element,?node(index));
}
/**
?*?Inserts?element?e?before?non-null?Node?succ.
?*/
//?在指定節(jié)點(diǎn)處新增元素，修改指定元素的下一個節(jié)點(diǎn)為新增元素，新增元素的下一個節(jié)點(diǎn)是查找到得?node?的next節(jié)點(diǎn)指向，
//?新增元素的上一個節(jié)點(diǎn)為查找到的?node?節(jié)點(diǎn)，查找到的?node?節(jié)點(diǎn)的?next?指向?node?的?prev?修改為新?Node
void?linkBefore(E?e,?Node?succ) ?{
????//?assert?succ?!=?null;
????final?Node?pred?=?succ.prev;
????final?Node?newNode?=?new?Node<>(pred,?e,?succ);
????succ.prev?=?newNode;
????if?(pred?==?null)
????????first?=?newNode;
????else
????????pred.next?=?newNode;
????size++;
????modCount++;
}可以看到指定位置插入元素主要分為兩個部分，第一個部分是查找 node 節(jié)點(diǎn)部分，這部分就是上面介紹的 LinkedList 數(shù)據(jù)獲取部分， 第二個部分是在查找到得 node 對象后插入元素。主要就是修改 node 的 next 指向?yàn)樾鹿?jié)點(diǎn)，新節(jié)點(diǎn)的 prev 指向?yàn)椴檎业降?node 節(jié)點(diǎn)，新節(jié)點(diǎn)的 next 指向?yàn)椴檎业降?node 節(jié)點(diǎn)的 next 指向。查找到的 node 節(jié)點(diǎn)的 next 指向的 node 節(jié)點(diǎn)的 prev 修改為新節(jié)點(diǎn)。 
LinkedLst 插入元素
LinkedList 數(shù)據(jù)刪除
public?E?remove(int?index)?{
????checkElementIndex(index);
????return?unlink(node(index));
}
/**
?*?Unlinks?non-null?node?x.
?*/
E?unlink(Node?x) ?{
????//?assert?x?!=?null;
????final?E?element?=?x.item;
????final?Node?next?=?x.next;
????final?Node?prev?=?x.prev;
????if?(prev?==?null)?{
????????first?=?next;
????}?else?{
????????prev.next?=?next;
????????x.prev?=?null;
????}
????if?(next?==?null)?{
????????last?=?prev;
????}?else?{
????????next.prev?=?prev;
????????x.next?=?null;
????}
????x.item?=?null;
????size--;
????modCount++;
????return?element;
}
擴(kuò)展
public?class?LinkedList<E>?extends?AbstractSequentialList<E>
????implements?List<E>,?Deque<E>,?Cloneable,?java.io.Serializable
Queue ?queue?=?new?LinkedList<>();
queue.add("a");
queue.add("b");
queue.add("c");
queue.add("d");
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
// result：
//?a
//?b
//?c
//?d
poll 時(shí)刪除 first 節(jié)點(diǎn)不就完事了嘛。?
總結(jié)
遍歷，ArrayList 每次都是直接定位，LinkedList 通過 next 節(jié)點(diǎn)定位，不相上下。這里要注意的是 LinkedList ?只有使用迭代器的方式遍歷才會使用 next 節(jié)點(diǎn)。如果使用 get，則因?yàn)楸闅v查找效率低下。新增，ArrayList 可能會需要擴(kuò)容，中間插入時(shí)，ArrayList 需要后移插入位置之后的所有元素。LinkedList 直接修改 node 的 prev, next 指向，LinkedList 勝出。 刪除，同 2. 隨機(jī)訪問指定位置，ArrayList 直接定位，LinkedList 從頭會尾開始查找，數(shù)組勝出。
有道無術(shù)，術(shù)可成；有術(shù)無道，止于術(shù)
歡迎大家關(guān)注Java之道公眾號
好文章，我在看??