深入學(xué)習(xí)Java之LinkedList
前言
LinkedList，作為最常用的List接口的實現(xiàn)類之一，與ArrayList基本齊名，兩者都是在日常開發(fā)中非常常用的List類型，不過，兩者的底層實現(xiàn)大不相同，這也導(dǎo)致了這兩者的應(yīng)用場景的不同，接下來，我們來詳細學(xué)習(xí)LinkedList的具體實現(xiàn)
LinkedList的繼承結(jié)構(gòu)
這里跟前面學(xué)習(xí)ArrayList一樣，首先先從宏觀上來看下LinkedList的繼承結(jié)構(gòu)，然后自上而下學(xué)習(xí)其各個接口，最后再學(xué)習(xí)其源碼的實現(xiàn)
LinkedList的繼承結(jié)構(gòu)如下所示
從上圖中可以非常清楚地看到,LinkedList同樣也是Iterable、Collection、AbstractCollection、ListAbstractList的子類，關(guān)于這幾個類，由于在ArrayList部分我們已經(jīng)進行過深入的學(xué)習(xí)了，這里就不再重復(fù)，如果看到這里還不熟悉的話，可以翻回前面的文章進行學(xué)習(xí)，接下來我們來學(xué)習(xí)新的接口中的方法，主要有Queue、Deque以及AbstractSequentialList
首先來看下Queue接口
相信學(xué)習(xí)過數(shù)據(jù)結(jié)構(gòu)的你對Queue，也就是隊列應(yīng)該不陌生，隊列是一個有序的數(shù)據(jù)結(jié)構(gòu)，并且隊列只有兩種操作，入隊和出隊，其中的入隊只能從后面入隊，出隊只能從前面出隊，就跟日常生活中排隊一樣(不考慮插隊的情況)，結(jié)合上圖可以看到，Queue接口對這些操作提供了定義，其中的add、offer是入隊操作，也就是從隊尾插入一個元素，不過add與offer的區(qū)別在于，如果隊列的長度的有限制的，而當隊列已經(jīng)滿的情況下，進行入隊操作，add會拋出異常，而offer不會，同理，對于出隊操作的remove、poll而言，兩者都是從隊首取出一個元素，remove在隊列為空的情況下會拋出異常，而poll則僅是返回null而不會拋出異常，element、peek是查看隊首的元素而不取出，這里需要注意跟remove、poll的區(qū)別，同理，element會在隊列為空的情況下拋出異常，peek僅僅返回null而不拋出異常
接下來是Deque接口
Deque，全稱是Double End Queue，也就是雙端隊列，所謂的雙端隊列，其實指的就是可以在兩端進行操作的隊列，這里的操作跟普通的隊列操作一致，包括(入隊，出隊，以及查看隊首元素)，只不過由于是雙端操作，所以Deque的方法比較多，Deque接口中同樣還提供了將其當成Queue進行操作的普通方法，同時，Deque接口還提供了幾個比較讓人迷惑的方法，分別是push、pop這兩者對應(yīng)的是棧的操作，也就是說，Deque實際上還可以當成棧來使用，這也是可以理解的嘛，棧本質(zhì)上就是一個只能在一端進行操作的線性表，而雙端隊列的每一個端都是可以進行插入和彈出的，所以本質(zhì)上也是符合棧的操作特性的，只是這里將其混合在一起，個人感覺不是很符合邏輯上的想法
Deque中的方法，如上圖所示，分別對應(yīng)的是Queue的操作方法，只是由于可以進行雙端操作，所以方法的數(shù)量加倍了，而且對應(yīng)的是First、Last，也就是隊首隊尾同時可以進行操作，這些方法基本都是見名之意，理解的Queue接口的方法之后，理解Deque的方法就不難了
接下來是AbstractSequentialList
從一開始的LinkedList結(jié)構(gòu)圖中可以看到，AbstractSequentialList繼承自AbstractCollection并且實現(xiàn)了List接口，之所以還需要提供AbstractSequentialList，是由于LinkedList的實現(xiàn)中，本質(zhì)上是以鏈式結(jié)構(gòu)將各個節(jié)點連接起來的，這種方式相對于以數(shù)組組成的線性結(jié)構(gòu)的優(yōu)勢在于，對特點節(jié)點進行插入、刪除操作的時候，所消耗的時間是常數(shù)級別的(數(shù)組形式的刪除、插入操作需要移動整個數(shù)組中后半部分的內(nèi)容)，然而這種方式的缺點也是非常明顯的，不支持索引操作，由于不是數(shù)組形式，所以是沒有方法可以直接訪問第n個元素的，而AbstractSequentialList抽象類，則定義了實現(xiàn)隨機訪問的操作方法，當然，這些離散訪問的代價其實是相當高的，后面我們將看到在LinkedList中的具體實現(xiàn)
LinkedList的源碼剖析
上面從宏觀的角度了解了LinkedList的繼承結(jié)構(gòu)，總體上把握了LinkedList的方法之后，接下里我們來具體學(xué)習(xí)LinkedList的實現(xiàn)
在LinkedList的源碼中，有一個Node類型的私有內(nèi)部類，這個類就是構(gòu)成LinkedList結(jié)構(gòu)的節(jié)點的定義類，代碼如下
private static class Node<E> {
// 元素值
E item;
// 后向指針
Node<E> next;
// 前向指針
Node<E> prev;
// 新建節(jié)點的時候，需要指明該節(jié)點的前向節(jié)點以及后向節(jié)點
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
從上面的Node節(jié)點的定義中可以知道，LinkedList本質(zhì)上是一個鏈表，并且是一個雙向鏈表，所謂的雙向鏈表指的就是鏈表中的節(jié)點都有一個前向指針和一個后向指針，分別指向自己的前向節(jié)點和后向節(jié)點，雙向鏈表的優(yōu)勢在于，可以往任意方法查找元素，而不像普通的單向鏈表一個，每次都必須從鏈表的頭部開始查找
學(xué)習(xí)完LinkedList的基本組成之后，接下來來學(xué)習(xí)下LinkedList的構(gòu)造方法
// 空構(gòu)造器，用于構(gòu)造一個空鏈表
public LinkedList() {
}
//用另外一個容器來構(gòu)造鏈表
public LinkedList(Collection<? extends E> c) {
this();
// 將該容器中的所有元素順序地添加到鏈表中
addAll(c);
}
// 添加一個容器中的所有元素
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;
// 新建兩個節(jié)點，用于指示所要插入位置的元素的前后元素
Node<E> pred, succ;
// 如果index == size，表明插入的位置是后面，則succ
// 也就是后向指針為空，pred，前向指針指向當前最后一個元素
if (index == size) {
succ = null;
pred = last;
// 否則的話，獲取當前index所指示的元素
// 并且使succ指向當前元素，pred指向其前面的元素
} else {
succ = node(index);
pred = succ.prev;
}
// 逐個添加元素
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
// 使用每個元素構(gòu)造一個節(jié)點，并且其前向節(jié)點為pred，
// 默認后向節(jié)點為null
Node<E> newNode = new Node<>(pred, e, null);
// 如果此時前向為null，說明此時的鏈表是空鏈表
// 則將first指向新建的節(jié)點，作為表頭
if (pred == null)
first = newNode;
else // 如果不為空，則將pred的后向指針指向新建的節(jié)點
pred.next = newNode;
// pred后移，重新指向新建的節(jié)點
// 從這里也可以看出元素添加的順序是添加到后面
// 也就是尾插入，而不是頭插入
pred = newNode;
}
// 當容器中的元素添加完成后，如果succ為空，說明
// 所要插入的位置要么是最后一個元素所在位置，
// 要么就是鏈表為空，last指向最后一個元素
if (succ == null) {
last = pred;
// 如果不為空，說明鏈表中早已經(jīng)有元素
// 則最后一個元素的后向指針指向該元素
// 并且該元素的前向指針指向最后一個元素
// 完成插入的過程
} else {
pred.next = succ;
succ.prev = pred;
}
// 統(tǒng)計鏈表中的元素總個數(shù)
size += numNew;
// 由于修改了鏈表結(jié)構(gòu)，modCount加1
modCount++;
return true;
}
插入元素
// 由于是LinkedList實現(xiàn)了Deque接口，所以LinkedList本身也是雙端
// 隊列，所以支持雙端的操作
// 添加到首部
public void addFirst(E e) {
linkFirst(e);
}
// 同樣是插入到首部，可以看到，offerFirst其實
// 使用的也是addFirst
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
// 棧的添加方式push，默認也是添加到首部
public void push(E e) {
addFirst(e);
}
// 添加到首部的具體實現(xiàn)，其實就是頭插法的應(yīng)用
private void linkFirst(E e) {
final Node<E> f = first;
// 新建 節(jié)點，并且其前向指針指向空，后向指針指向鏈表的
// 頭結(jié)點 first
final Node<E> newNode = new Node<>(null, e, f);
// fist重新指向新建的節(jié)點，也就是first重新成為頭結(jié)點
first = newNode;
// 如果插入之前的頭結(jié)點為空，說明鏈表為空
// 則尾指針同樣指向新建的節(jié)點，此時只有一個節(jié)點
if (f == null)
last = newNode;
else // 如果不為空，則插入前的頭結(jié)點的前向指針指向新建的節(jié)點，作為其后向節(jié)點
// 此時新建的節(jié)點真正成為頭節(jié)點
f.prev = newNode;
size++;
modCount++;
}
// =========================================================
// 添加到尾部
public void addLast(E e) {
linkLast(e);
}
// 插入到尾部，本質(zhì)也是使用addLast
public boolean offerLast(E e) {
addLast(e);
return true;
}
// 不指定添加方向
public boolean add(E e) {
// 默認添加到尾部
linkLast(e);
return true;
}
// 不指定方向，默認添加到尾部
public boolean offer(E e) {
return add(e);
}
// 插入到鏈表尾部，也就是尾插法
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
// 如果插入前尾節(jié)點為空，則說明插入前鏈表為空
// 頭結(jié)點指向新建節(jié)點，此時鏈表只有一個節(jié)點
if (l == null)
first = newNode;
else // 插入前的尾節(jié)點指向新建的節(jié)點，新建節(jié)點作為新的尾節(jié)點
l.next = newNode;
size++;
modCount++;
}
// ===================================================
// 在指定位置插入元素
public void add(int index, E element) {
checkPositionIndex(index);
// 如果是尾部，則直接添加即可
if (index == size)
linkLast(element);
else // 否則，獲取inde所在節(jié)點，并且鏈接到其前面
linkBefore(element, node(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++;
}
獲取元素
// 獲取第一個元素，直接返回first指向的節(jié)點的元素值即可
public E getFirst() {
final Node<E> f = first;
// 如果fist為空，說明此時鏈表為空
if (f == null)
throw new NoSuchElementException();
return f.item;
}
// 同樣為獲取第一個元素，但是當鏈表為空時，返回null而不是
// 拋出異常
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
// 同上
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
// 默認也是獲取第一個元素，同樣會拋出異常
public E element() {
return getFirst();
}
// 獲得第index個節(jié)點的元素，注意，此操作比較消耗資源
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
// 獲取第index個節(jié)點，從具體的實現(xiàn)中可以看到，基本上
// 使用索引來查找，是通過遍歷半個鏈表來實現(xiàn)的
Node<E> node(int index) {
// 先判斷所要獲取的位置屬于前半部分還是后半部分
// 這里設(shè)計的非常好，可以減少不必要的查找，提高效率，
// 學(xué)習(xí)了^_^
if (index < (size >> 1)) {
Node<E> x = first;
// 從頭找第index個節(jié)點
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
// 從后往前找第index個節(jié)點
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
// ========================================================
// 獲取最后一個元素，返回last指向的節(jié)點的值即可
public E getLast() {
final Node<E> l = last;
// 如果last為空，說明此時鏈表為空
if (l == null)
throw new NoSuchElementException();
return l.item;
}
// 獲取最后一個元素，在鏈表為空時，返回null而不是拋出異常
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
替換元素
// 現(xiàn)獲取第index個元素，然后將其值替換為新的值
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
刪除元素
// 刪除第一個元素
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
// 未指定方向時，默認刪除第一個元素
public E remove() {
return removeFirst();
}
// 刪除第一個元素，在鏈表為空時返回null，而不拋出異常
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
// 未指定方向時，默認刪除第一個元素，
// 在鏈表為空時返回null，而不拋出異常
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
// 棧的彈出方式，默認彈出第一個元素
public E pop() {
return removeFirst();
}
// 刪除第一個元素的具體實現(xiàn)
private E unlinkFirst(Node<E> f) {
final E element = f.item;
// 獲取第一個元素的后一個元素
final Node<E> next = f.next;
// 刪除第一個元素的值以及后向指針
f.item = null;
f.next = null; // help GC
// first指向新的節(jié)點
first = next;
// 如果新的節(jié)點為空，說明此時鏈表沒有元素
// last也指向null
if (next == null)
last = null;
else // 刪除next的前向指針，此時next為新的頭結(jié)點
// 前向指針不應(yīng)該還有指向
next.prev = null;
size--;
modCount++;
return element;
}
// ====================================================
// 刪除最后一個元素
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
// 刪除最后一個元素，鏈表為空時，返回null而不是拋出異常
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
// 刪除最后一個元素的具體實現(xiàn)
private E unlinkLast(Node<E> l) {
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
// 如果此時最后一個元素的前向指針為空，
// 說明此時鏈表為空，first也應(yīng)該指向null
if (prev == null)
first = null;
else
// 此時的prev為最后一個元素，next指向null
prev.next = null;
size--;
modCount++;
return element;
}
// =====================================================
刪除第一個出現(xiàn)的元素
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
// 刪除指定元素，默認是刪除第一個出現(xià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;
}
}
// 如果不為空，則刪除一個出現(xiàn)的元素
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
// 反向刪除第一個出現(xià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;
}
// 刪除元素的具體實現(xiàn)
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
// 獲得該元素的前向節(jié)點以及后向節(jié)點
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// 如果前向節(jié)點為空，則說明該節(jié)點為第一個節(jié)點
// fist指向其后的節(jié)點
if (prev == null) {
first = next;
} else {
// 否則，其前節(jié)點的后向指針指向其后節(jié)點
// 相當于刪除該節(jié)點
prev.next = next;
// 斷開節(jié)點x的前向引用
x.prev = null;
}
// 如果后向節(jié)點為空，則說明該節(jié)點為最后一個節(jié)點
// last指向其前節(jié)點
if (next == null) {
last = prev;
} else {
// 否則，其后節(jié)點的前向指針指向其前節(jié)點
// 相當于刪除該節(jié)點
next.prev = prev;
// 斷開節(jié)點x的后向引用
x.next = null;
}
// 節(jié)點x指向空
x.item = null;
size--;
modCount++;
return element;
}
獲得指定元素的索引
// 獲取第一個出現(xiàn)的元素的索引
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;
}
// 獲得反向第一個出現(xiàn)的元素的索引
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
將鏈表轉(zhuǎn)為數(shù)組
// 本質(zhì)上是鏈表的遍歷
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
// 同上，只是指定了元素的類型
public <T> T[] toArray(T[] a) {
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}
總結(jié)
本小節(jié)主要先從宏觀上了解LinkedList的繼承結(jié)構(gòu)，然后再逐個深入其實現(xiàn)接口的方法，最后，深入剖析了LinkedList的源碼實現(xiàn)，從LinkedList的源碼中可以看到，LinkedList比較適合從首部或者尾部進行元素的刪除、插入，這是效率最高的，其次是在任意位置插入、刪除元素，這里需要注意跟ArrayList的區(qū)別，LinkedList定位到某個元素所在位置時，需要遍歷該鏈表，所以需要消耗O(n)時間，但是插入的時候不需要進行元素的移動，而ArrayList定位的時候只需要O(1)的時間，但是卻需要移動元素，所以在數(shù)據(jù)量比較大的情況下，如果需要對數(shù)據(jù)進行頻繁的插入、刪除操作，使用LinkedList的優(yōu)勢大一些，而且由于LinkedList底層是通過節(jié)點之間的連接形成鏈的，所以不需要整一個連續(xù)的空間，這在某些情況下也是非常有利的條件(相對于ArrayList的數(shù)組結(jié)構(gòu))
