大廠之路的第二篇 雙鏈表即LinkedList
上一篇旺拉，我們分析了ArrayList,我們分析了它的底層數(shù)據(jù)結(jié)構(gòu)，也從源碼角度分析了它的一些常用函數(shù)棵磷。那么蛾狗，這一節(jié)，我們同樣從源碼的角度來看一下LinkedList的底層數(shù)據(jù)結(jié)構(gòu)以及它的一些常用函數(shù)仪媒。
開篇我們就說到了LinkedList是一個(gè)雙鏈表沉桌，所謂雙鏈表就是說它的鏈條是有兩個(gè)方向的，通過一個(gè)元素我們既可以找到它的上一個(gè)元素也可以找到它的下一個(gè)元素算吩。如果遍歷的話留凭，我們既可以從鏈表的頭部向后進(jìn)行遍歷，也可以從尾部向頭部進(jìn)行遍歷偎巢。
ok蔼夜，話不多說，直接進(jìn)入到源碼來驗(yàn)證這一點(diǎn)压昼。
LinkedList的數(shù)據(jù)結(jié)構(gòu)--雙鏈表
進(jìn)入到LinkedList的源碼中求冷，我們可以很容易的找到這樣兩個(gè)成員變量:transient Node<E> first;和transient Node<E> last;，它們的類型都是Node窍霞。那么匠题，Node的數(shù)據(jù)結(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;
this.next = next;
this.prev = prev;
}
}
Node是LinkedList中的一個(gè)靜態(tài)內(nèi)部類但金，我們可以看到它有三個(gè)成員屬性:item,next和prev韭山。見名知意，我們可以很容易的猜想到這三個(gè)變量分別代表著什么：item用于存儲(chǔ)當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)冷溃，next用于指向下一個(gè)節(jié)點(diǎn)的引用,而prev則指向上一個(gè)節(jié)點(diǎn)钱磅。我們暫且可以這么猜想，后面在LinkedList的常用函數(shù)的源碼分析中似枕，我們會(huì)去驗(yàn)證這一點(diǎn)续搀。
ok，那么我們現(xiàn)在就進(jìn)入到LinkedList的常用函數(shù)的源碼分析中去吧菠净！
同樣禁舷，我們先來看 LinkedList的構(gòu)造函數(shù)。
LinkedList的構(gòu)造函數(shù)
LinkedList只有兩個(gè)構(gòu)造函數(shù)：一個(gè)是無(wú)參構(gòu)造毅往，另一個(gè)是傳入一個(gè)集合的有參構(gòu)造牵咙。
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
首先看這個(gè)無(wú)參構(gòu)造，基本什么都沒干攀唯，也就是說只是new出了一個(gè)LinkedList的實(shí)例洁桌，成員變量first和last都為null。
我們?cè)賮砜春竺孢@個(gè)構(gòu)造函數(shù):它的參數(shù)只有一個(gè)侯嘀，一個(gè)集合另凌，傳入這個(gè)集合以后它做了哪些事情呢谱轨？我們到addAll這個(gè)函數(shù)里去看一看:
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
我們假設(shè)要添加的集合中有兩個(gè)元素,然后我們來逐句分析addAll這個(gè)函數(shù)。
首先吠谢，檢查index的合法性土童，顯然是合法的。
然后工坊，將傳入的collection轉(zhuǎn)化為一個(gè)數(shù)組献汗。
接著，因?yàn)?code>index和size都為0王污，所以就命中第一個(gè)if語(yǔ)句罢吃，從而使得succ和pred都為null。
隨后昭齐，進(jìn)入到foreach這個(gè)循環(huán)當(dāng)中尿招。因?yàn)槲覀兗现兄挥袃蓚€(gè)元素，所以這個(gè)循環(huán)只會(huì)走兩次阱驾，我們每一次都來實(shí)際分析一下就谜。
首先，先構(gòu)造出一個(gè)Node節(jié)點(diǎn)
- 第一次時(shí)啊易，因?yàn)?code>pred為
null吁伺，所以會(huì)走if代碼塊饮睬，所以會(huì)將構(gòu)造出來的第一個(gè)Node節(jié)點(diǎn)賦給first租谈，然后再將其賦給pred，所以在下一次循環(huán)的時(shí)候pred不再為null捆愁。- 第二次的時(shí)候割去，因?yàn)?code>pred不再為
null，所以命中else代碼塊昼丑，因?yàn)?code>pred指向的是first引用呻逆，所以first的next指針就指向了新生成的Node節(jié)點(diǎn)。而新生成的Node節(jié)點(diǎn)在構(gòu)造的時(shí)候就將其prev指針指向了pred也就是first節(jié)點(diǎn)菩帝。隨后再將pred指向了最后這個(gè)節(jié)點(diǎn)咖城。
最后，走出foreach循環(huán)以后呼奢，因?yàn)?code>succ在此過程中宜雀，沒有被賦值，所以仍然為null握础，也就命中了if語(yǔ)句辐董，將last指向了最后生成的那個(gè)節(jié)點(diǎn)，并給size重新賦值禀综。
這樣简烘，整個(gè)構(gòu)造函數(shù)就走完了苔严。
不難發(fā)現(xiàn)，走完整個(gè)構(gòu)造孤澎，first,last,以及size都被賦值了届氢，而且形成了一條雙向鏈表。
下面亥至，我們接著分析LinkedList的一些常用函數(shù)悼沈。
LinkedList add系列函數(shù)
1.向尾部添加元素
由于LinkedList既實(shí)現(xiàn)了List接口，又實(shí)現(xiàn)了Deque接口姐扮，而這兩個(gè)接口又有不同的add函數(shù),所以LinkedList有兩個(gè)不同的add函數(shù)都實(shí)現(xiàn)了向尾部添加元素絮供。而這兩個(gè)函數(shù)唯一的區(qū)別就是有沒有返回值。
public boolean add(E e) {
//實(shí)現(xiàn)自AbstractList
linkLast(e);
return true;
}
public void addLast(E e) {
//實(shí)現(xiàn)自Deque
linkLast(e);
}
所以茶敏，我們主要要看的就是linkLast這個(gè)函數(shù)壤靶。
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
首先，先拿到last的引用惊搏，然后在構(gòu)造的Node節(jié)點(diǎn)的時(shí)候?qū)⑵?code>prev指針指向last節(jié)點(diǎn)贮乳，然后將新節(jié)點(diǎn)賦給last。
其次恬惯，判斷當(dāng)前鏈表的first是否為null向拆，也就是鏈表是不是為null，如果是則將新構(gòu)造的節(jié)點(diǎn)同時(shí)賦給first酪耳，否則將當(dāng)前鏈表的last的next指針指向新構(gòu)造的節(jié)點(diǎn)浓恳，其實(shí)就是一個(gè)重新連接鏈表的過程。
最后碗暗，給size加1.
2.向指定位置添加元素
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
首先颈将，還是檢查索引的合法性。
第二步言疗，判斷索引是不是等于size,如果是的話晴圾，那么操作其實(shí)就等同于向尾部添加元素，這個(gè)操作我們前面已經(jīng)分析過了噪奄，就不再贅述死姚。
第三步，如果index不等于size,那么就走linkBefore這個(gè)函數(shù).
這個(gè)步驟可以劃分成兩步：
1.node(index)找到要往哪一個(gè)節(jié)點(diǎn)前面插入
Node<E> node(int index) {
// assert isElementIndex(index);
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;
}
}
由于LinkedList是雙向鏈表勤篮，所以先判斷index是處于鏈表的前半段還是后半段都毒，如果是前半段則從頭部開始遍歷，反之從后尾部開始遍歷叙谨，這樣也提高了性能温鸽。
- 然后才是真正的插入操作:
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
第一步，找到要插入的節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)，記為pred涤垫。
第二步姑尺，以要插入的元素為數(shù)據(jù)構(gòu)造新節(jié)點(diǎn)，并將其prev指針指向pred節(jié)點(diǎn)蝠猬。
第三步切蟋，將要插入節(jié)點(diǎn)的prev指針指向新構(gòu)造的節(jié)點(diǎn)。
第四步榆芦，判斷pred節(jié)點(diǎn)是否為空柄粹。如果為空則說明我們要插入的位置其實(shí)是鏈表頭部，那么就將新節(jié)點(diǎn)賦給first匆绣，否則將pred節(jié)點(diǎn)的next指針指向我們新構(gòu)造的節(jié)點(diǎn)驻右。
最后，將size的值加1崎淳。
總的來說這個(gè)過程其實(shí)就是一個(gè)鏈表的斷開以及重新連接的過程堪夭。感興趣的朋友可以自己在紙上畫出這個(gè)過程。
3.向頭部添加元素
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
這個(gè)其實(shí)就更簡(jiǎn)單了拣凹。
首先森爽，找到first節(jié)點(diǎn)，并用一個(gè)臨時(shí)變量f存儲(chǔ)嚣镜。
其次爬迟，以要插入的數(shù)據(jù)構(gòu)造出一個(gè)新的節(jié)點(diǎn)，并將其next指針指向老的first節(jié)點(diǎn)菊匿。
然后付呕，重新給first節(jié)點(diǎn)賦值，將新構(gòu)造的節(jié)點(diǎn)賦給first捧请。
最后凡涩，判斷老的first節(jié)點(diǎn)是不是為null,如果是則說明之前的鏈表中沒有數(shù)據(jù)：將last同樣指向新生成的節(jié)點(diǎn);否則將老的first節(jié)點(diǎn)的prev指針指向新插入的節(jié)點(diǎn)棒搜。
當(dāng)然疹蛉，最后要給size重新賦值。
3.向鏈表中插入集合
分為兩種情況:1.向尾部插入集合 2.向指定位置插入集合力麸。
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
其實(shí)主要就是要看addAll這個(gè)函數(shù)可款，這個(gè)函數(shù)我們?cè)诜治?code>LinkedList的構(gòu)造函數(shù)的時(shí)候其實(shí)已經(jīng)解析過了，所以我們也不再重復(fù)的去分析了克蚂。
按照增刪改查的順序闺鲸，那么我們下面就分析remove系列函數(shù)
LinkedList remove系列函數(shù)
1.移除頭部節(jié)點(diǎn)
移除頭部節(jié)點(diǎn)的函數(shù)有兩個(gè):其實(shí)最終都是走了removeFirst這個(gè)函數(shù)
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
主要是分析unlinkFirst這個(gè)函數(shù)
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;
}
這個(gè)函數(shù)的過程其實(shí)很好理解：
1.首先獲取到老的first節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，也就是移除老的first后的新的first節(jié)點(diǎn)埃叭。
2.將老的first節(jié)點(diǎn)的element以及next都置為null幫助gc能夠快速回收
3.將老的first節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)賦給first摸恍，如果為空則說明整個(gè)鏈表在first移除之后就空了，所以也將last置為null;否則，將新的first節(jié)點(diǎn)的prev置為null立镶，實(shí)際上就是徹底斷開新的first節(jié)點(diǎn)與老的first節(jié)點(diǎn)之間的連接壁袄。
4.最后重新給size賦值，以及將移除節(jié)點(diǎn)對(duì)應(yīng)的element返回媚媒。
2.移除尾部節(jié)點(diǎn)
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
可以看到嗜逻，移除尾部節(jié)點(diǎn)跟移除頭部節(jié)點(diǎn)其實(shí)是一個(gè)很相似的過程，移除頭部節(jié)點(diǎn)的話其實(shí)是將頭部節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)置為頭部節(jié)點(diǎn)缭召，而移除尾部節(jié)點(diǎn)則是將尾部節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)置為尾部節(jié)點(diǎn)栈顷。所以我們也不再去分析這個(gè)過程了。
3.移除指定位置的節(jié)點(diǎn)
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
這個(gè)過程可以分為兩個(gè)步驟:
1.先找到要移除的那個(gè)節(jié)點(diǎn):根據(jù)判斷index屬于鏈表的前半段還是后半段來決定是從頭部開始遍歷還是尾部開始遍歷嵌巷，找到對(duì)應(yīng)的節(jié)點(diǎn)萄凤。
Node<E> node(int index) {
// assert isElementIndex(index);
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;
}
}
2.然后走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;
}
我們來重點(diǎn)分析一下這個(gè)unlink函數(shù)，其實(shí)這個(gè)函數(shù)跟linkBefore其實(shí)是差不了太多的搪哪，都是一個(gè)斷鏈以及給各節(jié)點(diǎn)指針重新指定指向的過程蛙卤。
1.獲得要移除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)，即prev和next
2.判斷prev是否為null,如果是則將next賦給first噩死；否則將prev的next指針指向next,并將要移除的節(jié)點(diǎn)的prev指針置空颤难。
3.判斷next是否為null,如果是則將prev賦給last；否則將next的prev指針指向prev,并將要移除的節(jié)點(diǎn)的next指針置空已维。
4.最后將要移除節(jié)點(diǎn)的item置空行嗤，幫助gc快速回收。并重新給size賦值垛耳。
4.從頭部開始遍歷移除第一個(gè)數(shù)據(jù)等于指定元素的節(jié)點(diǎn)
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;
}
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
這兩個(gè)方法最終都是走的上面那個(gè)函數(shù)栅屏，而上面那個(gè)函數(shù)主要走的還是走的unlink函數(shù)。unlink函數(shù)我們上面已經(jīng)詳細(xì)分析過了堂鲜，所以我們?cè)谶@就不再分析了栈雳。
5.從尾部開始遍歷移除第一個(gè)數(shù)據(jù)等于指定元素的節(jié)點(diǎn)
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
這里我們發(fā)現(xiàn)，同樣這個(gè)函數(shù)的核心還是走unlink函數(shù)缔莲，這就是上面我們?yōu)槭裁匆攸c(diǎn)分析unlink函數(shù)的原因哥纫。
ok,remove系列函數(shù)我們就分析到這了。
LinkedList set系列函數(shù)
set系列函數(shù)比較可憐痴奏，就只有一個(gè)函數(shù):
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
首先蛀骇，還是驗(yàn)證index的合法性
其次，還是通過node函數(shù)來找到指定節(jié)點(diǎn)读拆。
最后擅憔，替換指定節(jié)點(diǎn)的item,并將老的item返回。
set函數(shù)相對(duì)來說比較簡(jiǎn)單檐晕。
LinkedList get系列函數(shù)
get系列函數(shù)也比較簡(jiǎn)單暑诸，如果是查找頭部和尾部函數(shù)速度也是相當(dāng)?shù)目臁?br>
如果是查找指定位置的元素?cái)?shù)據(jù)，則同樣是通過node函數(shù)來去遍歷查找。
所以說个榕，node函數(shù)也是LinkedList中的一個(gè)比較重要的函數(shù).
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
這三個(gè)函數(shù)比較簡(jiǎn)單啦逆，我們就不詳細(xì)去展開了。
前面我們有提到過笛洛，LinkedList有實(shí)現(xiàn)Deque接口夏志，而Deque接口有什么特性呢？
Deque是一個(gè)雙端隊(duì)列苛让。我們知道隊(duì)列的特性就是先進(jìn)先出:從隊(duì)尾進(jìn)沟蔑，從對(duì)頭出。而雙端隊(duì)列則是可以從兩端插入和從兩端彈出的一種特殊隊(duì)列狱杰。
因?yàn)?LinkedList實(shí)現(xiàn)了Deque接口瘦材，所以它同樣實(shí)現(xiàn)了Deque所特有的一些方法:peek,peekFirst, peekLast,poll,pollFirst,pollLast,pop,push等一系列方法。這些方法其實(shí)是跟我們所分析的方法有重合的仿畸，所以在這里就不再去分析了食棕。
好了，今天關(guān)于LinkedList的源碼我們就分析到這里了错沽。
下一篇簿晓，我們將對(duì)ArrayList和LinkedList做一個(gè)總結(jié)，分析兩個(gè)各自的優(yōu)缺點(diǎn)以及它們的異同和各自的適合的應(yīng)用場(chǎng)景千埃。
