分析完了List與Queue之后，終于可以看看LinkedList的實(shí)現(xiàn)了。LinkedList彌補(bǔ)了ArrayList增刪較慢的問(wèn)題痛侍，但在查找方面又遜色于ArrayList钥弯，所以在使用時(shí)需要根據(jù)場(chǎng)景靈活選擇。對(duì)于這兩個(gè)頻繁使用的集合類垂寥，掌握它們的源碼并正確使用颠黎，可以讓我們的代碼更高效。
LinkedList既實(shí)現(xiàn)了List滞项，又實(shí)現(xiàn)了Deque狭归，前者使它能夠像使用ArrayList一樣使用，后者又使它能夠承擔(dān)隊(duì)列的職責(zé)文判。LinkedList內(nèi)部結(jié)構(gòu)是一個(gè)雙向鏈表过椎，我們?cè)诜治?code>ArrayDeque時(shí)提到過(guò)這個(gè)概念，就是擴(kuò)充單鏈表的指針域戏仓，增加一個(gè)指向前一個(gè)元素的指針previous疚宇。
AbstractSequentialList
AbstractSequentialList是LinkedList的父級(jí)，它繼承自AbstractList赏殃，并且是一個(gè)抽象類敷待，它主要為順序表的鏈?zhǔn)綄?shí)現(xiàn)提供一個(gè)骨架：
This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a "sequential access" data store (such as a linked list). For random access data (such as an array), AbstractList should be used in preference to this class.
意思是它的主要作用是提供一個(gè)實(shí)現(xiàn)List接口的骨架，來(lái)減少我們實(shí)現(xiàn)基于鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)類時(shí)所需的工作量仁热。AbstractSequentialList并沒有做很多特殊的事情榜揖，其中最主要的是提供一個(gè)方法的默認(rèn)實(shí)現(xiàn)，并將以下方法抽象抗蠢，以期有更符合場(chǎng)景的實(shí)現(xiàn)：
public abstract ListIterator<E> listIterator(int index);
其他一些方法的實(shí)現(xiàn)都利用了這個(gè)listIterator方法举哟，我們不再一一查看了。下面我們分析LinkedList的實(shí)現(xiàn)
LinkedList的結(jié)構(gòu)
LinkedList的繼承結(jié)構(gòu)如下所示：
可以看到物蝙，LinkedList也實(shí)現(xiàn)了Cloneable炎滞、java.io.Serializable等方法，借鑒于ArrayList的經(jīng)驗(yàn)诬乞，我們可以想到它的Clone也是淺克隆册赛，在序列化方法也采用了同樣的方式钠导，我們就不再贅述了。
構(gòu)造方法與成員變量
數(shù)據(jù)單元Node
在介紹鏈表結(jié)構(gòu)時(shí)提到過(guò)森瘪，其數(shù)據(jù)單元分為數(shù)據(jù)域和指針域牡属，分別存儲(chǔ)數(shù)據(jù)和指向下一個(gè)元素的位置，在java中只要定義一個(gè)實(shí)體類就可以解決了扼睬。
private static class Node<E> {
E item; //數(shù)據(jù)
Node<E> next; //下一個(gè)元素
Node<E> prev; //上一個(gè)元素
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
成員變量
LinkedList成員變量主要有三個(gè)逮栅，而且其意義清晰可見。
// 記錄當(dāng)前鏈表的長(zhǎng)度
transient int size = 0;
// 第一個(gè)節(jié)點(diǎn)
transient Node<E> first;
// 最后一個(gè)節(jié)點(diǎn)
transient Node<E> last;
構(gòu)造函數(shù)
因?yàn)殒湵頉]有長(zhǎng)度方面的問(wèn)題窗宇，所以也不會(huì)涉及到擴(kuò)容等問(wèn)題措伐，其構(gòu)造函數(shù)也十分簡(jiǎn)潔了。
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
一個(gè)默認(rèn)的構(gòu)造函數(shù)军俊，什么都沒有做侥加，一個(gè)是用其他集合初始化，調(diào)用了一下addAll方法粪躬。addAll方法我們就不再分析了担败，它應(yīng)該是和添加一個(gè)元素的方法是一致的。
重要方法
LinkedList既繼承了List镰官，又繼承了Deque提前，那它必然有一堆add、remove泳唠、addFirst狈网、addLast等方法。這些方法的含義也相差不大警检，實(shí)現(xiàn)也是類似的孙援，因此LinkedList又提取了新的方法，來(lái)簡(jiǎn)化這些問(wèn)題扇雕。我們看看這些不對(duì)外的方法拓售，以及它們是如何與上述函數(shù)對(duì)應(yīng)的。
//將一個(gè)元素鏈接到首位
private void linkFirst(E e) {
//先將原鏈表存起來(lái)
final Node<E> f = first;
//定義一個(gè)新節(jié)點(diǎn)镶奉，其next指向原來(lái)的first
final Node<E> newNode = new Node<>(null, e, f);
//將first指向新建的節(jié)點(diǎn)
first = newNode;
//原鏈表為空表
if (f == null)
//把last也指向新建的節(jié)點(diǎn)础淤，現(xiàn)在first與last都指向了它
last = newNode;
else
//把原鏈表掛載在新建節(jié)點(diǎn)，也就是現(xiàn)在的first之后
f.prev = newNode;
size++;
modCount++;
}
//與linkFirst類似
void linkLast(E e) {
//...
}
//在某個(gè)非空節(jié)點(diǎn)之前添加元素
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//先把succ節(jié)點(diǎn)的前置節(jié)點(diǎn)存起來(lái)
final Node<E> pred = succ.prev;
//新節(jié)點(diǎn)插在pred與succ之間
final Node<E> newNode = new Node<>(pred, e, succ);
//succ的prev指針移到新節(jié)點(diǎn)
succ.prev = newNode;
//前置節(jié)點(diǎn)為空
if (pred == null)
//說(shuō)明插入到了首位
first = newNode;
else
//把前置節(jié)點(diǎn)的next指針也指向新建的節(jié)點(diǎn)
pred.next = newNode;
size++;
modCount++;
}
//刪除首位的元素哨苛，元素必須非空
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
private E unlinkLast(Node<E> l) {
//...
}
//刪除一個(gè)指定的節(jié)點(diǎn)
E unlink(Node<E> x) {
//...
}
可以看到鸽凶，LinkedList提供了一系列方法用來(lái)插入和刪除，但是卻沒有再實(shí)現(xiàn)一個(gè)方法來(lái)進(jìn)行查詢建峭，因?yàn)閷?duì)鏈表的查詢是比較慢的玻侥，所以它是通過(guò)另外的方法來(lái)實(shí)現(xiàn)的，我們看一下：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//可以說(shuō)盡力了
Node<E> node(int index) {
// assert isElementIndex(index);
//size>>1就是取一半的意思
//折半亿蒸，將遍歷次數(shù)減少一半
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
最后凑兰，我們看下它如何對(duì)應(yīng)那些繼承來(lái)的方法：
//引用了node方法掌桩，需要遍歷
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
//也可能需要遍歷
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//也要遍歷
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E element() {
return getFirst();
}
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E remove() {
return removeFirst();
}
public boolean offer(E e) {
return add(e);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
//...
總結(jié)
LinkedList非常適合大量數(shù)據(jù)的插入與刪除，但其對(duì)處于中間位置的元素姑食，無(wú)論是增刪還是改查都需要折半遍歷波岛，這在數(shù)據(jù)量大時(shí)會(huì)十分影響性能。在使用時(shí)音半，盡量不要涉及查詢與在中間插入數(shù)據(jù)则拷，另外如果要遍歷，也最好使用foreach曹鸠，也就是Iterator提供的方式煌茬。
上一篇：Java集合源碼分析之Queue（三）：ArrayDeque
下一篇：Java集合源碼分析之Map（一）：超級(jí)接口Map
我是飛機(jī)醬，如果您喜歡我的文章物延，可以關(guān)注我~
編程之路宣旱，道阻且長(zhǎng)仅父。唯叛薯，路漫漫其修遠(yuǎn)兮，吾將上下而求索笙纤。
