注：本系列文章中用到的jdk版本均為
java8
LinkedList類圖如下：
LinkedList底層是由雙向鏈表實(shí)現(xiàn)的。鏈表好比火車，每節(jié)車廂包含了車廂和連接下一節(jié)車廂的連接點(diǎn)。而雙向鏈表的每個(gè)節(jié)點(diǎn)不僅有指向下一個(gè)節(jié)點(diǎn)的指針，還有指向上一個(gè)節(jié)點(diǎn)的指針。
在LinkedList源碼中有一個(gè)Node靜態(tài)類，源碼如下：
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;
}
}
一個(gè)Node節(jié)點(diǎn)包含三個(gè)部分，分別是
item：數(shù)據(jù)
next：下一個(gè)節(jié)點(diǎn)的指針
prev：上一個(gè)節(jié)點(diǎn)的指針
LinkedList的主要變量如下：
// 集合中的元素?cái)?shù)量
transient int size = 0;
/**
* 首節(jié)點(diǎn)的指針.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node first;
/**
* 尾結(jié)點(diǎn)的指針.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node last;
一、添加元素
LinkedList支持在任意節(jié)點(diǎn)位置添加元素，不僅提供了集合常用的add()方法，還提供了addFirst()和addLast()，add()方法默認(rèn)調(diào)用addLast()方法，也就是默認(rèn)是往鏈表尾部插入元素的。
add()方法源碼：
public boolean add(E e) {
linkLast(e);
return true;
}
1.1 尾部插入元素
linkLast()源碼如下：
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
我們來畫張圖演示一下如何給鏈表尾部插入元素：
假如鏈表中沒有元素
對(duì)應(yīng)源碼中的if語句，如果沒有元素則新增的這個(gè)節(jié)點(diǎn)為鏈表中唯一的一個(gè)元素，既是首節(jié)點(diǎn)，又是尾結(jié)點(diǎn)，前一個(gè)元素的指針和后一個(gè)元素的指針都是null。這里注意head節(jié)點(diǎn)不是第一個(gè)節(jié)點(diǎn)，head節(jié)點(diǎn)只是標(biāo)識(shí)了這個(gè)鏈表的地址。
假如鏈表中有元素
對(duì)應(yīng)源碼中else語句。先將新增的元素當(dāng)成Last節(jié)點(diǎn)，然后將原來的Last節(jié)點(diǎn)的next指向新節(jié)點(diǎn)。
else
l.next = newNode;
一圖勝前言，畫個(gè)圖是不是什么都明白了。
1.2 頭部插入元素
linkFirst()源碼如下：
private void linkFirst(E e) {
final Node f = first;
final Node newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
還是根據(jù)上面的圖來解讀一下源碼，先將第一個(gè)節(jié)點(diǎn)賦值給中間變量f，將新節(jié)點(diǎn)newNode賦值給first節(jié)點(diǎn)。如果鏈表沒有元素，則Last節(jié)點(diǎn)和First節(jié)點(diǎn)都是新插入的節(jié)點(diǎn)newNode，否則，將原來的First節(jié)點(diǎn)的頭指針指向新節(jié)點(diǎn)。
二、刪除元素
LinkedList提供的刪除方法有根據(jù)索引和元素刪除，除此之外還提供刪除第一個(gè)元素和最后一個(gè)元素的方法，這里我們只分析一下根據(jù)索引刪除的方法。
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
checkElementIndex(index)方法就是用來判斷傳輸?shù)乃饕凳欠窈戏?，不合法則拋出數(shù)組越界異常。重點(diǎn)來看一下unlink(node(index))方法是如何刪除元素的。
node(index)方法源碼：
node(index)方法就是根據(jù)索引獲取該索引位置的節(jié)點(diǎn)
Node node(int index) {
// assert isElementIndex(index);
// 如果指定下標(biāo) < 一半元素?cái)?shù)量，則從首結(jié)點(diǎn)開始遍歷
// 否則，從尾結(jié)點(diǎn)開始遍歷
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
unlink(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;
}
畫張圖分析一下刪除是如何進(jìn)行的：
假設(shè)刪除的是第一個(gè)元素：則它的
prev==NULL，我們需要將他的后一個(gè)元素（圖中的second）作為第一個(gè)元素假設(shè)刪除的是最后一個(gè)元素，則它的
next==null，我們需要將他的前一個(gè)元素（圖中的second）作為最后一個(gè)元素如果是中間的任意元素，則需要將它的前一個(gè)元素的
next指針指向它的后一個(gè)元素，同時(shí)將它的后一個(gè)元素的prev指針指向它的前一個(gè)元素。
三、總結(jié)
LinkedList底層是由雙向鏈表實(shí)現(xiàn)的，由于是鏈表實(shí)現(xiàn)的，不僅要存放數(shù)據(jù)，還要存放指針，所以內(nèi)存開銷要比ArrayList大，刪除元素不需要移動(dòng)其他元素，只需要改變指針的指向，因此刪除效率更高，同時(shí)它沒有實(shí)現(xiàn)RandomAccess接口，因此使用迭代器遍歷要比for循環(huán)更加高效。LinkedList也支持插入重復(fù)值和空值，同樣也是線程不安全的。
特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長按關(guān)注一下：
長按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠摯感謝
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
