7L-雙線鏈表實現
鏈表是基本的數據結構，尤其雙向鏈表在應用中最為常見，LinkedList 就實現了雙向鏈表。今天我們一起手寫一個雙向鏈表。
文中涉及的代碼可訪問 GitHub://github.com/UniqueDong/algorithms.git
上次我們說了「單向鏈表」的代碼實現，今天帶大家一起玩下雙向鏈表，雙向鏈表的節點比單項多了一個指針引用 「prev」。雙向鏈表就像渣男，跟「前女友」和「現女友」，還有一個「備胎』都保持聯繫。前女友就像是前驅節點，現女友就是 「當前 data」，而「next」指針就像是他套住的備胎。每個 Node 節點有三個屬性，類比就是 「前女友」+ 「現女友」 + 「備胎」。
使用這樣的數據結構就能實現「進可攻退可守」靈活狀態。
接下來讓我們一起實現『渣男雙向鏈表』。
定義Node
節點分別保存現女友、前女友、跟備胎的聯繫方式，這樣就能夠實現一三五輪換運動（往前看有前女友，往後看有備胎），通過不同指針變可以找到前女友跟備胎。就像渣男擁有她們的聯繫方式。
private static class Node<E> {
//現女友
E item;
// 備胎
Node<E> next;
// 前女友
Node<E> prev;
public Node(Node<E> prev, E item, Node<E> next) {
this.prev = prev;
this.item = item;
this.next = next;
}
}
代碼實現
定義好渣男節點後，就開始實現我們的雙向鏈表。類似過來就是一個渣男聯盟排成一列。我們還需要定義兩個指針分別指向頭結點和尾節點。一個帶頭大哥，一個收尾小弟。
public class DoubleLinkedList<E> extends AbstractList<E> implements Queue<E> {
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
}
頭節點添加
新的渣男進群了，把他設置成群主帶頭大哥。首先構建新節點，prev = null，帶頭大哥業務繁忙，不找前女友，所以 prev = null；next 則指向原先的 first。
- 如果鏈表是空的，則還要把尾節點也指向新創建的節點。
- 若果鏈表已近有數據，則把原先 first.prev = newNode。
@Override
public void addFirst(E e) {
linkFirst(e);
}
/**
* 頭結點添加數據
*
* @param e 數據
*/
private void linkFirst(E e) {
final Node<E> f = this.first;
Node<E> newNode = new Node<>(null, e, f);
// first 指向新節點
first = newNode;
if (Objects.isNull(f)) {
// 鏈表是空的
last = newNode;
} else {
// 將原 first.prev = newNode
f.prev = newNode;
}
size++;
}
尾節點添加
將新進來的成員放在尾巴。
第一步構建新節點，把 last 指向新節點。
第二步判斷 last 節點是否是空，為空則說明當前鏈表是空，還要把 first 指向新節點。否則就需要把原 last.next 的指針指向新節點。
@Override
public boolean add(E e) {
addLast(e);
return true;
}
private void addLast(E e) {
final Node<E> l = this.last;
Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (Objects.isNull(l)) {
// 鏈表為空的情況下，設置 first 指向新節點
first = newNode;
} else {
// 原 last 節點的 next 指向新節點
l.next = newNode;
}
size++;
}
指定位置添加
分為兩種情況，一個是在最後的節點新加一個。一種是在指定節點的前面插入新節點。
在後面添加前面尾巴添加已經說過，對於在指定節點的前面插入需要我們先找到指定位置節點，然後改變他們的 prev next 指向。
@Override
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size) {
linkLast(element);
} else {
linkBefore(element, node(index));
}
}
/**
* Links e as last element.
*/
void linkLast(E element) {
addLast(element);
}
/**
* Inserts element e before non-null Node succ.
*/
private void linkBefore(E element, Node<E> succ) {
// assert succ != null
final Node<E> prev = succ.prev;
// 構造新節點
final Node<E> newNode = new Node<>(prev, element, succ);
succ.prev = newNode;
if (Objects.isNull(prev)) {
first = newNode;
} else {
prev.next = newNode;
}
size++;
}
節點查找
為了優化，根據 index 查找的時候先判斷 index 落在前半部分還是後半部分。前半部分通過 first 開始查找，否則通過 last 指針從後往前遍歷。
@Override
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// 優化查找，判斷 index 在前半部分還是後半部分。
if (index < (this.size >> 2)) {
// 前半部分，從頭結點開始查找
Node<E> x = this.first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
} else {
// 後半部分，從尾節點開始查找
Node<E> x = this.last;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
return x;
}
}
查找 Object 所在位置 indexOf ,若找不到返回 -1
@Override
public int indexOf(Object o) {
int index = 0;
if (Objects.isNull(o)) {
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 (x.item.equals(o)) {
return index;
}
index++;
}
}
return -1;
}
判斷 鏈表中是否存在 指定對象 contains ，其實還是利用 上面的 indexOf 方法，當返回值 不等於 -1 則說明包含該對象。
@Override
public boolean contains(Object o) {
return indexOf(o) != -1;
}
節點刪除
有兩種刪除情況：
- 根據下標刪除指定位置的節點。
- 刪除指定數據的節點。
刪除指定位置節點
- 首先判斷該 index 是否合法存在。
- 查找要刪除的節點位置，重新設置被刪除節點關聯的指針指向。
node() 方法已經在前面的查找中封裝好這裡可以直接調用，我們再實現 unlink 方法，該方法還會用於刪除指定對象，所以這抽出來實現復用。也是最核心最不好理解的方法，我們多思考畫圖理解下。
@Override
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
public final void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* Tells if the argument is the index of an existing element.
*/
private boolean isElementIndex(int index) {
return index >= 0 && index < size();
}
/**
* Unlinks non-null node x.
*/
private 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;
// 若 只有一個節點，那麼會執行 prev == null 和 next == null 分支代碼
// 若 prev == null 則說明刪除的是頭結點,主要負責 x 節點跟前驅節點的引用處理
if (Objects.isNull(prev)) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
// 若 next 為空，說明刪除的是尾節點，主要負責 x 與 next 節點 引用的處理
if (Objects.isNull(next)) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
return element;
}
分別找出被刪除節點 x 的前驅和後繼節點，要考慮當前鏈表只有一個節點的情況，最後還要把被刪除節點的 的 next 指針 ，item 設置 null，便於垃圾回收，防止內存泄漏。
刪除指定數據
這裡判斷下數據是否是 null , 從頭節點開始遍歷鏈表，當找到索要刪除的節點的時候低啊用前面封裝好的 unlink 方法實現刪除。
@Override
public boolean remove(Object o) {
if (Objects.isNull(o)) {
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;
}
完整代碼可以參考 GitHub：//github.com/UniqueDong/algorithms.git
加群跟我們一起探討，歡迎關注 MageByte，我第一時間解答。
推薦閱讀
4.線性表之數組
5.鏈表導論-心法篇
原創不易，覺得有用希望讀者隨手「在看」「收藏」「轉發」三連。
