溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
（1）LinkedList只是一個List嗎？
（2）LinkedList還有其它什么特性嗎？
（3）LinkedList為啥經常拿出來跟ArrayList比較？
（4）我為什么把LinkedList放在最后一章來講？
LinkedList是一個以雙向鏈表實現的List，它除了作為List使用，還可以作為隊列或者棧來使用，它是怎么實現的呢？讓我們一起來學習吧。
通過繼承體系，我們可以看到LinkedList不僅實現了List接口，還實現了Queue和Deque接口，所以它既能作為List使用，也能作為雙端隊列使用，當然也可以作為棧使用。
// 元素個數
transient int size = 0;
// 鏈表首節點
transient Node<E> first;
// 鏈表尾節點
transient Node<E> last;屬性很簡單，定義了元素個數size和鏈表的首尾節點。
典型的雙鏈表結構。
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;
}
}public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}兩個構造方法也很簡單，可以看出是一個×××的隊列。
作為一個雙端隊列，添加元素主要有兩種，一種是在隊列尾部添加元素，一種是在隊列首部添加元素，這兩種形式在LinkedList中主要是通過下面兩個方法來實現的。
// 從隊列首添加元素
private void linkFirst(E e) {
// 首節點
final Node<E> f = first;
// 創建新節點，新節點的next是首節點
final Node<E> newNode = new Node<>(null, e, f);
// 讓新節點作為新的首節點
first = newNode;
// 判斷是不是第一個添加的元素
// 如果是就把last也置為新節點
// 否則把原首節點的prev指針置為新節點
if (f == null)
last = newNode;
else
f.prev = newNode;
// 元素個數加1
size++;
// 修改次數加1，說明這是一個支持fail-fast的集合
modCount++;
}
// 從隊列尾添加元素
void linkLast(E e) {
// 隊列尾節點
final Node<E> l = last;
// 創建新節點，新節點的prev是尾節點
final Node<E> newNode = new Node<>(l, e, null);
// 讓新節點成為新的尾節點
last = newNode;
// 判斷是不是第一個添加的元素
// 如果是就把first也置為新節點
// 否則把原尾節點的next指針置為新節點
if (l == null)
first = newNode;
else
l.next = newNode;
// 元素個數加1
size++;
// 修改次數加1
modCount++;
}
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
// 作為×××隊列，添加元素總是會成功的
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}典型的雙鏈表在首尾添加元素的方法，代碼比較簡單，這里不作詳細描述了。
上面是作為雙端隊列來看，它的添加元素分為首尾添加元素，那么，作為List呢？
作為List，是要支持在中間添加元素的，主要是通過下面這個方法實現的。
// 在節點succ之前添加元素
void linkBefore(E e, Node<E> succ) {
// succ是待添加節點的后繼節點
// 找到待添加節點的前置節點
final Node<E> pred = succ.prev;
// 在其前置節點和后繼節點之間創建一個新節點
final Node<E> newNode = new Node<>(pred, e, succ);
// 修改后繼節點的前置指針指向新節點
succ.prev = newNode;
// 判斷前置節點是否為空
// 如果為空，說明是第一個添加的元素，修改first指針
// 否則修改前置節點的next為新節點
if (pred == null)
first = newNode;
else
pred.next = newNode;
// 修改元素個數
size++;
// 修改次數加1
modCount++;
}
// 尋找index位置的節點
Node<E> node(int index) {
// 因為是雙鏈表
// 所以根據index是在前半段還是后半段決定從前遍歷還是從后遍歷
// 這樣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;
}
}
// 在指定index位置處添加元素
public void add(int index, E element) {
// 判斷是否越界
checkPositionIndex(index);
// 如果index是在隊列尾節點之后的一個位置
// 把新節點直接添加到尾節點之后
// 否則調用linkBefore()方法在中間添加節點
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}在中間添加元素的方法也很簡單，典型的雙鏈表在中間添加元素的方法。
添加元素的三種方式大致如下圖所示：
在隊列首尾添加元素很高效，時間復雜度為O(1)。
在中間添加元素比較低效，首先要先找到插入位置的節點，再修改前后節點的指針，時間復雜度為O(n)。
作為雙端隊列，刪除元素也有兩種方式，一種是隊列首刪除元素，一種是隊列尾刪除元素。
作為List，又要支持中間刪除元素，所以刪除元素一個有三個方法，分別如下。
// 刪除首節點
private E unlinkFirst(Node<E> f) {
// 首節點的元素值
final E element = f.item;
// 首節點的next指針
final Node<E> next = f.next;
// 添加首節點的內容，協助GC
f.item = null;
f.next = null; // help GC
// 把首節點的next作為新的首節點
first = next;
// 如果只有一個元素，刪除了，把last也置為空
// 否則把next的前置指針置為空
if (next == null)
last = null;
else
next.prev = null;
// 元素個數減1
size--;
// 修改次數加1
modCount++;
// 返回刪除的元素
return element;
}
// 刪除尾節點
private E unlinkLast(Node<E> l) {
// 尾節點的元素值
final E element = l.item;
// 尾節點的前置指針
final Node<E> prev = l.prev;
// 清空尾節點的內容，協助GC
l.item = null;
l.prev = null; // help GC
// 讓前置節點成為新的尾節點
last = prev;
// 如果只有一個元素，刪除了把first置為空
// 否則把前置節點的next置為空
if (prev == null)
first = null;
else
prev.next = null;
// 元素個數減1
size--;
// 修改次數加1
modCount++;
// 返回刪除的元素
return element;
}
// 刪除指定節點x
E unlink(Node<E> x) {
// x的元素值
final E element = x.item;
// x的前置節點
final Node<E> next = x.next;
// x的后置節點
final Node<E> prev = x.prev;
// 如果前置節點為空
// 說明是首節點，讓first指向x的后置節點
// 否則修改前置節點的next為x的后置節點
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
// 如果后置節點為空
// 說明是尾節點，讓last指向x的前置節點
// 否則修改后置節點的prev為x的前置節點
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// 清空x的元素值，協助GC
x.item = null;
// 元素個數減1
size--;
// 修改次數加1
modCount++;
// 返回刪除的元素
return element;
}
// remove的時候如果沒有元素拋出異常
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
// remove的時候如果沒有元素拋出異常
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
// poll的時候如果沒有元素返回null
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
// poll的時候如果沒有元素返回null
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
// 刪除中間節點
public E remove(int index) {
// 檢查是否越界
checkElementIndex(index);
// 刪除指定index位置的節點
return unlink(node(index));
}刪除元素的三種方法都是典型的雙鏈表刪除元素的方法，大致流程如下圖所示。
在隊列首尾刪除元素很高效，時間復雜度為O(1)。
在中間刪除元素比較低效，首先要找到刪除位置的節點，再修改前后指針，時間復雜度為O(n)。
前面我們說了，LinkedList是雙端隊列，還記得雙端隊列可以作為棧使用嗎？
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}棧的特性是LIFO(Last In First Out)，所以作為棧使用也很簡單，添加刪除元素都只操作隊列首節點即可。
（1）LinkedList是一個以雙鏈表實現的List；
（2）LinkedList還是一個雙端隊列，具有隊列、雙端隊列、棧的特性；
（3）LinkedList在隊列首尾添加、刪除元素非常高效，時間復雜度為O(1)；
（4）LinkedList在中間添加、刪除元素比較低效，時間復雜度為O(n)；
（5）LinkedList不支持隨機訪問，所以訪問非隊列首尾的元素比較低效；
（6）LinkedList在功能上等于ArrayList + ArrayDeque；
java集合部分的源碼分析全部完結，整個專題以ArrayList開頭，以LinkedList結尾，我覺得非常合適，因為ArrayList代表了List的典型實現，LInkedList代表了Deque的典型實現，同時LinkedList也實現了List，通過這兩個類一首一尾正好可以把整個集合貫穿起來。
還記得我們一共分析了哪些類嗎？
下一章，筆者將對整個java集合做一個總結，并提出一些閱讀源碼過程中的問題，敬請期待^^
歡迎關注我的公眾號“彤哥讀源碼”，查看更多源碼系列文章, 與彤哥一起暢游源碼的海洋。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
