書接上一篇ArrayList源碼解析,這一節(jié)繼續(xù)分析LinkedList在Java8中的實(shí)現(xiàn)司忱，它同樣實(shí)現(xiàn)了List接口氓奈，不過由名字就可以知道痹籍，內(nèi)部實(shí)現(xiàn)是基于鏈表的，而且是雙向鏈表贷屎，所以Linked List在執(zhí)行像插入或者刪除這樣的操作罢防，效率是極高的，相對(duì)地唉侄，在隨機(jī)訪問方面就弱了很多咒吐。
本文基于JDK1.8中LinkedList源碼分析
類定義
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
由上圖以及類定義片段可知，LinkedList繼承了AbstractSequentialList并且實(shí)現(xiàn)List属划，Deque恬叹，Cloneable, Serializable接口。
其中同眯，AbstractSequentialList相較于AbstractList(ArrayList的父類),只支持次序訪問绽昼，而不支持隨機(jī)訪問，因?yàn)樗?br>
get(int index) ,set(int index, E element), add(int index, E element), remove(int index) 都是基于迭代器實(shí)現(xiàn)的须蜗。所以在LinkedList使用迭代器遍歷更快硅确，而ArrayList使用get (i)更快。
接口方面明肮，LinkedList多繼承了一個(gè)Deque接口菱农，所以實(shí)現(xiàn)了雙端隊(duì)列的一系列方法。
基本數(shù)據(jù)結(jié)構(gòu)
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
LinkedList中主要定義了頭節(jié)點(diǎn)指針柿估，尾節(jié)點(diǎn)指針循未，以及size用于計(jì)數(shù)鏈表中節(jié)點(diǎn)個(gè)數(shù)。那么每一個(gè)Node的結(jié)構(gòu)如何呢秫舌？
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element; //當(dāng)前節(jié)點(diǎn)值
this.next = next; //后繼節(jié)點(diǎn)
this.prev = prev;//前驅(qū)節(jié)點(diǎn)
}
}
可以看出的妖，這是一個(gè)典型的雙向鏈表的節(jié)點(diǎn)。
LinkedList先不從初始化聊起足陨，首先談插入與刪除羔味。
獲取節(jié)點(diǎn)
獲取節(jié)點(diǎn)是相對(duì)比較簡單的操作， LinkedList提供了:
- getFirst獲取頭節(jié)點(diǎn)
- getLast獲取尾節(jié)點(diǎn)
- get(int index) 獲取指定位置的節(jié)點(diǎn)
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
檢查非空后钠右，直接返回first節(jié)點(diǎn)的item
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
檢查非空后赋元，直接返回last節(jié)點(diǎn)的item
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
首先檢查index范圍，然后調(diào)用node(index)獲取index處的節(jié)點(diǎn)飒房，返回該節(jié)點(diǎn)的item值搁凸。
看看node(index)的實(shí)現(xiàn)，后面很多地方借助于這個(gè)小函數(shù)：
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) { //判斷index是在鏈表偏左側(cè)還是偏右側(cè)
Node<E> x = first;
for (int i = 0; i < index; i++) //從左邊往右next
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--) //從右往左prev
x = x.prev;
return x;
}
}
由上面可以看出狠毯，在鏈表中找一個(gè)位置护糖，只能通過不斷遍歷。
另外還有IndexOf嚼松，LastIndexOf操作嫡良，找出指定元素在LinkedList中的位置：
也是一個(gè)從前找锰扶，一個(gè)從后找，只分析下IndexOf操作：
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
主要也是不斷遍歷寝受，找到值相等的節(jié)點(diǎn)坷牛，返回它的Index。
更改節(jié)點(diǎn)的值
主要也就是一個(gè)set函數(shù)
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
根據(jù)index找到指定節(jié)點(diǎn)很澄，更改它的值京闰，并且會(huì)返回原有值。
插入節(jié)點(diǎn)
LinkedList實(shí)現(xiàn)了Deque接口甩苛，支持在鏈表頭部和尾部插入元素：
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
這里我們可以看到內(nèi)部實(shí)現(xiàn)的函數(shù)是linkFirst,linkLast,
鏈表頭插入元素：
private void linkFirst(E e) {
final Node<E> f = first; //現(xiàn)將原有的first節(jié)點(diǎn)保存在f中
final Node<E> newNode = new Node<>(null, e, f); //將新增節(jié)點(diǎn)包裝成一個(gè)Node節(jié)點(diǎn)蹂楣，同時(shí)該節(jié)點(diǎn)的next指向之前的first
first = newNode; //將新增的節(jié)點(diǎn)設(shè)成first
if (f == null)
last = newNode; //如果原來的first就是空，那么新增的newNode同時(shí)也是last節(jié)點(diǎn)
else
f.prev = newNode; //如果不是空讯蒲，則原來的first節(jié)點(diǎn)的前置節(jié)點(diǎn)就是現(xiàn)在新增的節(jié)點(diǎn)
size++; //插入元素后痊土，節(jié)點(diǎn)個(gè)數(shù)加1
modCount++; //還記得上一篇講述的快速失敗嗎？這邊依然是這個(gè)作用
}
主要流程：
- 將原有頭節(jié)點(diǎn)保存到f
- 將插入元素包裝成新節(jié)點(diǎn)墨林，并且該新節(jié)點(diǎn)的next指向原來的頭節(jié)點(diǎn)赁酝，即f
- 如果原來的頭節(jié)點(diǎn)f為空的話，那么新插的頭節(jié)點(diǎn)也是last節(jié)點(diǎn)萌丈，否則，還要設(shè)置f的前置節(jié)點(diǎn)為NewNode雷则，即NewNode現(xiàn)在是first節(jié)點(diǎn)了
- 記得增加size辆雾，記錄修改次數(shù)modCount
鏈表尾插入元素
void linkLast(E e) {
final Node<E> l = last; //將尾節(jié)點(diǎn)保存到l中
final Node<E> newNode = new Node<>(l, e, null); //把e包裝成Node節(jié)點(diǎn)，同時(shí)把該節(jié)點(diǎn)的前置節(jié)點(diǎn)設(shè)置為l
last = newNode; //把新插的節(jié)點(diǎn)設(shè)置為last節(jié)點(diǎn)
if (l == null)
first = newNode; //如果原來的last節(jié)點(diǎn)為空月劈，那么新增的節(jié)點(diǎn)在意義上也是first節(jié)點(diǎn)
else
l.next = newNode; //否則的話還要將newNode設(shè)為原有l(wèi)ast節(jié)點(diǎn)的后繼節(jié)點(diǎn)度迂，所以newNode現(xiàn)在是新的Last節(jié)點(diǎn)
size++;
modCount++;
}
在指定index處插入元素
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
首先調(diào)用checkPositionIndex檢查index值是否在范圍內(nèi)猜揪，如果index在最后的話惭墓，就調(diào)用在尾部插入的函數(shù)，否則調(diào)用LinkBefore而姐，主要看LinkBefore如何實(shí)現(xiàn)的：
void linkBefore(E e, Node<E> succ) { //在succ節(jié)點(diǎn)前插入newNode
// assert succ != null;
final Node<E> pred = succ.prev; //將succ的前置節(jié)點(diǎn)記為pred
final Node<E> newNode = new Node<>(pred, e, succ); 以pred為前置節(jié)點(diǎn)腊凶，以succ為后繼節(jié)點(diǎn)建立newNode
succ.prev = newNode; //將new Node設(shè)為succ的前置節(jié)點(diǎn)
if (pred == null)
first = newNode; //如果原有的succ的前置節(jié)點(diǎn)為空，那么新插入的newNode就是first節(jié)點(diǎn)
else
pred.next = newNode; // 否則拴念，要把newNode設(shè)為原來pred節(jié)點(diǎn)的后置節(jié)點(diǎn)
size++;
modCount++;
}
其余幾個(gè)常用的add方法也是基于以上函數(shù)：
public boolean add(E e) {
linkLast(e);
return true;
}
add函數(shù)默認(rèn)在函數(shù)尾部插入元素
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
addAll(Collection<? extends E> c)指的是在list尾部插入一個(gè)集合，具體實(shí)現(xiàn)又依賴于addAll(size政鼠，c)风瘦，指的是在指定位置插入一個(gè)集合：
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); // 檢查index位置是否超出范圍
Object[] a = c.toArray(); //將集合c轉(zhuǎn)變成Object數(shù)組 同時(shí)計(jì)算數(shù)組長度
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) { //如果插入位置為尾部，succ則為null公般，原來鏈表的last設(shè)置為此刻的pred節(jié)點(diǎn)
succ = null;
pred = last;
} else {
succ = node(index); //否則万搔，index所在節(jié)點(diǎn)設(shè)置為succ胡桨，succ的前置節(jié)點(diǎn)設(shè)為pred
pred = succ.prev;
}
for (Object o : a) { //循環(huán)遍歷數(shù)組a
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null); //以a為element元素構(gòu)造Node節(jié)點(diǎn)
if (pred == null)
first = newNode;? //如果pred為空，此Node就為first節(jié)點(diǎn)
else
pred.next = newNode; //否則就往pred后插入該Node
pred = newNode; //newNode此刻成為新的pred, 這樣不斷循環(huán)遍歷瞬雹，把這個(gè)數(shù)組插入到鏈表中
}
if (succ == null) { //如果succ為空昧谊，就把插入的最后一個(gè)節(jié)點(diǎn)設(shè)為last
last = pred;
} else {
pred.next = succ; //否則，把之前保存的succ接到pred后面
succ.prev = pred; //并且把succ的前向指針指向插入的最后一個(gè)元素
}
size += numNew; //記錄增長的尺寸
modCount++; //記錄修改次數(shù)
return true;
}
具體流程可以看代碼中的注釋挖炬。
刪除節(jié)點(diǎn)####
因?yàn)閷?shí)現(xiàn)了Deque的接口揽浙，所以還是實(shí)現(xiàn)了removeFirst, removeLast方法。
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
首先保存fisrt節(jié)點(diǎn)到f意敛，如果為空馅巷，拋出NoSuchElementException異常，實(shí)際還是調(diào)用unlinkFirst完成操作草姻。
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item; //把f.item的值保存到element
final Node<E> next = f.next; //把f.next的值記住
f.item = null;
f.next = null; // help GC //把item和next的都指向null
first = next; //next成為實(shí)際的first節(jié)點(diǎn)
if (next == null) //next為空的話钓猬，因?yàn)閚ext是第一個(gè)節(jié)點(diǎn)，所以鏈表都是空的撩独，last也為空
last = null;
else
next.prev = null; //next不為空敞曹，也要將它的前驅(qū)節(jié)點(diǎn)記為null，因?yàn)閚ext是第一個(gè)節(jié)點(diǎn)
size--; //節(jié)點(diǎn)減少一個(gè)
modCount++; //操作次數(shù)加1
return element;
}
removeLast的實(shí)現(xiàn)基本和removeFirst對(duì)稱：
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
主要實(shí)現(xiàn)還是借助于unlinkLast:
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item; //保存最后一個(gè)節(jié)點(diǎn)的值
final Node<E> prev = l.prev; //把最后一個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)記為prev综膀，它將成為last節(jié)點(diǎn)
l.item = null;
l.prev = null; // help GC //l節(jié)點(diǎn)的item和prev都記為空
last = prev; //此時(shí)設(shè)置剛才記錄的前驅(qū)節(jié)點(diǎn)為last
if (prev == null) //prev為空的話澳迫，說明要?jiǎng)h除的l前面原來沒節(jié)點(diǎn)，那么刪了l剧劝，整個(gè)鏈表為空
first = null;
else
prev.next = null; //prev成為最后一個(gè)節(jié)點(diǎn)橄登，沒有后繼節(jié)點(diǎn)
size--;
modCount++;
return element;
}
在指定index刪除
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
首先也是檢查index是否合法，否則拋出IndexOutOfBoundsException異常讥此。
如果刪除成功拢锹，返回刪除的節(jié)點(diǎn)。
具體實(shí)現(xiàn)依賴于unlink萄喳，也就是unlink做實(shí)際的刪除操作：
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> 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;
}
根據(jù)圖和代碼來看卒稳，刪除一個(gè)節(jié)點(diǎn)有以下幾步：
- 將刪除的節(jié)點(diǎn)保存在element里，同時(shí)把要?jiǎng)h除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)標(biāo)記為prev,后繼節(jié)點(diǎn)標(biāo)記為next他巨；
- 如果prev為空充坑，那么next節(jié)點(diǎn)直接為first節(jié)點(diǎn)，反之把prev的next指向next節(jié)點(diǎn)染突，如圖中上面彎曲的紅色箭頭所示匪傍；
- 如果next為空，那么prev節(jié)點(diǎn)直接為last節(jié)點(diǎn)觉痛，反之把next的prev指向prev節(jié)點(diǎn)役衡，如圖中下面彎曲的藍(lán)色箭頭所示；
- 把要?jiǎng)h除的節(jié)點(diǎn)置空薪棒，返回第一步保存的element手蝎。
還有種刪除是以刪除的元素作為參數(shù)：
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
- o為null榕莺，也是遍歷鏈表，找到第一個(gè)值為null的節(jié)點(diǎn)棵介，刪除钉鸯；
- o部位空，遍歷鏈表邮辽，找到第一個(gè)值相等的節(jié)點(diǎn)唠雕，調(diào)用unlink(x)刪除。
清空列表
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
由代碼看出吨述，也就是循環(huán)遍歷整個(gè)鏈表岩睁，將每個(gè)節(jié)點(diǎn)的每個(gè)屬性都置為空。
LinkedList還定義了很多別的方法揣云，基本上和上面分析的幾個(gè)函數(shù)功能類似
- elemet和GetFirst一樣捕儒，都返回列表的頭，并且不移除它邓夕，如果列表為空刘莹，都會(huì)拋出NoSucnElement異常；
- peek也會(huì)返回第一個(gè)元素焚刚，但是為空時(shí)返回null, 不拋異常点弯；
- remove方法內(nèi)部就是調(diào)用removeFirst，所以表現(xiàn)相同矿咕，返回移除的元素抢肛，如果列表為空，都會(huì)拋出NoSucnElement異常痴腌；
- poll也是移除第一個(gè)元素雌团，只是會(huì)在列表為空時(shí)只返回null燃领；
- offer和offerLast在尾部add節(jié)點(diǎn)士聪， 最終調(diào)用的都是addLast方法，offerFirst在頭保護(hù)add節(jié)點(diǎn)猛蔽，調(diào)用的就是addFirst方法剥悟；
- peekFirst返回頭節(jié)點(diǎn)，為空時(shí)返回null曼库，peekLast返回尾節(jié)點(diǎn)区岗，為空時(shí)返回null，都不會(huì)刪除節(jié)點(diǎn)毁枯；
- pollFirst刪除并返回頭節(jié)點(diǎn)慈缔，為空時(shí)返回null ，pollLast刪除并返回尾節(jié)點(diǎn)种玛，為空時(shí)返回null藐鹤；
- push和pop也是讓LinkedList具有棧的功能瓤檐，也只是調(diào)用了addFirst和removeFirst函數(shù)。
ListIterator
最后重點(diǎn)說一下LinkedList中如何實(shí)現(xiàn)了ListIterator迭代器娱节。
ListIterator是一個(gè)更加強(qiáng)大的Iterator迭代器的子類型挠蛉，它只能用于各種List類的訪問。盡管Iterator只能向前移動(dòng)肄满，但是ListIterator可以雙向移動(dòng)谴古。它還可以產(chǎn)生相對(duì)于迭代器在列表中指向的當(dāng)前位置的前一個(gè)和后一個(gè)元素的索引，可以用set()方法替換它訪問過得最后一個(gè)元素稠歉。
定義如下：
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
指定index掰担，可以在一開始就獲取一個(gè)指向index位置元素的迭代器。
實(shí)際上LinkedList是實(shí)現(xiàn)了ListItr類：
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next; //用于記錄當(dāng)前節(jié)點(diǎn)
private int nextIndex; //用于記錄當(dāng)前節(jié)點(diǎn)所在索引
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index); //返回index處的節(jié)點(diǎn)轧抗，記錄為next
nextIndex = index; //記錄當(dāng)前索引
}
public boolean hasNext() {
return nextIndex < size; //通過判斷nextIndex是否還在size范圍內(nèi)
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next; //記錄上一次的值
next = next.next; //往后移動(dòng)一個(gè)節(jié)點(diǎn)
nextIndex++; //索引值也加1
return lastReturned.item; //next會(huì)返回上一次的值
}
public boolean hasPrevious() { //通過哦按段nextIndex是否還大于0恩敌，如果<=0，就證明沒有前驅(qū)節(jié)點(diǎn)了
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev; //往前移動(dòng)
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
我們可以發(fā)現(xiàn)在ListIterator的操作中仍然有checkForComodification函數(shù)横媚，而且在上面敘述的各種操作中還是會(huì)記錄modCount,所以LinkedList也是會(huì)產(chǎn)生快速失敗事件的纠炮。
