大廠之路的第二篇 雙鏈表即LinkedList
上一篇，我們分析了ArrayList,我們分析了它的底層數(shù)據(jù)結(jié)構(gòu)，也從源碼角度分析了它的一些常用函數(shù)。那么，這一節(jié)，我們同樣從源碼的角度來看一下LinkedList的底層數(shù)據(jù)結(jié)構(gòu)以及它的一些常用函數(shù)。
開篇我們就說到了LinkedList是一個雙鏈表，所謂雙鏈表就是說它的鏈條是有兩個方向的，通過一個元素我們既可以找到它的上一個元素也可以找到它的下一個元素。如果遍歷的話，我們既可以從鏈表的頭部向后進(jìn)行遍歷，也可以從尾部向頭部進(jìn)行遍歷。
ok，話不多說，直接進(jìn)入到源碼來驗(yàn)證這一點(diǎn)。
LinkedList的數(shù)據(jù)結(jié)構(gòu)--雙鏈表
進(jìn)入到LinkedList的源碼中，我們可以很容易的找到這樣兩個成員變量: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中的一個靜態(tài)內(nèi)部類，我們可以看到它有三個成員屬性:item,next和prev。見名知意，我們可以很容易的猜想到這三個變量分別代表著什么：item用于存儲當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)，next用于指向下一個節(jié)點(diǎn)的引用,而prev則指向上一個節(jié)點(diǎn)。我們暫且可以這么猜想，后面在LinkedList的常用函數(shù)的源碼分析中，我們會去驗(yàn)證這一點(diǎn)。
ok，那么我們現(xiàn)在就進(jìn)入到LinkedList的常用函數(shù)的源碼分析中去吧！
同樣，我們先來看 LinkedList的構(gòu)造函數(shù)。
LinkedList的構(gòu)造函數(shù)
LinkedList只有兩個構(gòu)造函數(shù)：一個是無參構(gòu)造，另一個是傳入一個集合的有參構(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òu)造，基本什么都沒干，也就是說只是new出了一個LinkedList的實(shí)例，成員變量first和last都為null。
我們再來看后面這個構(gòu)造函數(shù):它的參數(shù)只有一個，一個集合，傳入這個集合以后它做了哪些事情呢？我們到addAll這個函數(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è)要添加的集合中有兩個元素,然后我們來逐句分析addAll這個函數(shù)。
首先，檢查index的合法性，顯然是合法的。
然后，將傳入的collection轉(zhuǎn)化為一個數(shù)組。
接著，因?yàn)?code>index和size都為0，所以就命中第一個if語句，從而使得succ和pred都為null。
隨后，進(jìn)入到foreach這個循環(huán)當(dāng)中。因?yàn)槲覀兗现兄挥袃蓚€元素，所以這個循環(huán)只會走兩次，我們每一次都來實(shí)際分析一下。
首先，先構(gòu)造出一個Node節(jié)點(diǎn)
- 第一次時，因?yàn)?code>pred為
null，所以會走if代碼塊，所以會將構(gòu)造出來的第一個Node節(jié)點(diǎn)賦給first，然后再將其賦給pred，所以在下一次循環(huán)的時候pred不再為null。- 第二次的時候，因?yàn)?code>pred不再為
null，所以命中else代碼塊，因?yàn)?code>pred指向的是first引用，所以first的next指針就指向了新生成的Node節(jié)點(diǎn)。而新生成的Node節(jié)點(diǎn)在構(gòu)造的時候就將其prev指針指向了pred也就是first節(jié)點(diǎn)。隨后再將pred指向了最后這個節(jié)點(diǎn)。
最后，走出foreach循環(huán)以后，因?yàn)?code>succ在此過程中，沒有被賦值，所以仍然為null，也就命中了if語句，將last指向了最后生成的那個節(jié)點(diǎn)，并給size重新賦值。
這樣，整個構(gòu)造函數(shù)就走完了。
不難發(fā)現(xiàn)，走完整個構(gòu)造，first,last,以及size都被賦值了，而且形成了一條雙向鏈表。
下面，我們接著分析LinkedList的一些常用函數(shù)。
LinkedList add系列函數(shù)
1.向尾部添加元素
由于LinkedList既實(shí)現(xiàn)了List接口，又實(shí)現(xiàn)了Deque接口，而這兩個接口又有不同的add函數(shù),所以LinkedList有兩個不同的add函數(shù)都實(shí)現(xiàn)了向尾部添加元素。而這兩個函數(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這個函數(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)的時候?qū)⑵?code>prev指針指向last節(jié)點(diǎn)，然后將新節(jié)點(diǎn)賦給last。
其次，判斷當(dāng)前鏈表的first是否為null，也就是鏈表是不是為null，如果是則將新構(gòu)造的節(jié)點(diǎn)同時賦給first，否則將當(dāng)前鏈表的last的next指針指向新構(gòu)造的節(jié)點(diǎn)，其實(shí)就是一個重新連接鏈表的過程。
最后，給size加1.
2.向指定位置添加元素
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
首先，還是檢查索引的合法性。
第二步，判斷索引是不是等于size,如果是的話，那么操作其實(shí)就等同于向尾部添加元素，這個操作我們前面已經(jīng)分析過了，就不再贅述。
第三步，如果index不等于size,那么就走linkBefore這個函數(shù).
這個步驟可以劃分成兩步：
1.node(index)找到要往哪一個節(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)的上一個節(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。
總的來說這個過程其實(shí)就是一個鏈表的斷開以及重新連接的過程。感興趣的朋友可以自己在紙上畫出這個過程。
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++;
}
這個其實(shí)就更簡單了。
首先，找到first節(jié)點(diǎn)，并用一個臨時變量f存儲。
其次，以要插入的數(shù)據(jù)構(gòu)造出一個新的節(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這個函數(shù)，這個函數(shù)我們在分析LinkedList的構(gòu)造函數(shù)的時候其實(shí)已經(jīng)解析過了，所以我們也不再重復(fù)的去分析了。
按照增刪改查的順序，那么我們下面就分析remove系列函數(shù)
LinkedList remove系列函數(shù)
1.移除頭部節(jié)點(diǎn)
移除頭部節(jié)點(diǎn)的函數(shù)有兩個:其實(shí)最終都是走了removeFirst這個函數(shù)
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
主要是分析unlinkFirst這個函數(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;
}
這個函數(shù)的過程其實(shí)很好理解：
1.首先獲取到老的first節(jié)點(diǎn)的下一個節(jié)點(diǎn)，也就是移除老的first后的新的first節(jié)點(diǎn)。
2.將老的first節(jié)點(diǎn)的element以及next都置為null幫助gc能夠快速回收
3.將老的first節(jié)點(diǎn)的下一個節(jié)點(diǎn)賦給first，如果為空則說明整個鏈表在first移除之后就空了，所以也將last置為null;否則，將新的first節(jié)點(diǎn)的prev置為null，實(shí)際上就是徹底斷開新的first節(jié)點(diǎn)與老的first節(jié)點(diǎn)之間的連接。
4.最后重新給size賦值，以及將移除節(jié)點(diǎn)對應(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í)是一個很相似的過程，移除頭部節(jié)點(diǎn)的話其實(shí)是將頭部節(jié)點(diǎn)的下一個節(jié)點(diǎn)置為頭部節(jié)點(diǎn)，而移除尾部節(jié)點(diǎn)則是將尾部節(jié)點(diǎn)的前一個節(jié)點(diǎn)置為尾部節(jié)點(diǎn)。所以我們也不再去分析這個過程了。
3.移除指定位置的節(jié)點(diǎn)
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
這個過程可以分為兩個步驟:
1.先找到要移除的那個節(jié)點(diǎn):根據(jù)判斷index屬于鏈表的前半段還是后半段來決定是從頭部開始遍歷還是尾部開始遍歷，找到對應(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)分析一下這個unlink函數(shù)，其實(shí)這個函數(shù)跟linkBefore其實(shí)是差不了太多的，都是一個斷鏈以及給各節(jié)點(diǎn)指針重新指定指向的過程。
1.獲得要移除節(jié)點(diǎn)的上一個節(jié)點(diǎn)和下一個節(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.從頭部開始遍歷移除第一個數(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);
}
這兩個方法最終都是走的上面那個函數(shù)，而上面那個函數(shù)主要走的還是走的unlink函數(shù)。unlink函數(shù)我們上面已經(jīng)詳細(xì)分析過了，所以我們在這就不再分析了。
5.從尾部開始遍歷移除第一個數(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)，同樣這個函數(shù)的核心還是走unlink函數(shù)，這就是上面我們?yōu)槭裁匆攸c(diǎn)分析unlink函數(shù)的原因。
ok,remove系列函數(shù)我們就分析到這了。
LinkedList set系列函數(shù)
set系列函數(shù)比較可憐，就只有一個函數(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ù)相對來說比較簡單。
LinkedList get系列函數(shù)
get系列函數(shù)也比較簡單，如果是查找頭部和尾部函數(shù)速度也是相當(dāng)?shù)目臁?br>
如果是查找指定位置的元素數(shù)據(jù)，則同樣是通過node函數(shù)來去遍歷查找。
所以說，node函數(shù)也是LinkedList中的一個比較重要的函數(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;
}
這三個函數(shù)比較簡單，我們就不詳細(xì)去展開了。
前面我們有提到過，LinkedList有實(shí)現(xiàn)Deque接口，而Deque接口有什么特性呢？
Deque是一個雙端隊列。我們知道隊列的特性就是先進(jìn)先出:從隊尾進(jìn)，從對頭出。而雙端隊列則是可以從兩端插入和從兩端彈出的一種特殊隊列。
因?yàn)?LinkedList實(shí)現(xiàn)了Deque接口，所以它同樣實(shí)現(xiàn)了Deque所特有的一些方法:peek,peekFirst, peekLast,poll,pollFirst,pollLast,pop,push等一系列方法。這些方法其實(shí)是跟我們所分析的方法有重合的，所以在這里就不再去分析了。
好了，今天關(guān)于LinkedList的源碼我們就分析到這里了。
下一篇，我們將對ArrayList和LinkedList做一個總結(jié)，分析兩個各自的優(yōu)缺點(diǎn)以及它們的異同和各自的適合的應(yīng)用場景。
