相信大家都明白 LinkedList 是基于雙向連結清單而實作的，本篇文章主要講解一下雙向連結清單的實作，并且我們參考 LinkedList 自己實作一個單連結清單嘗試一下。
什麼是連結清單？
簡單的來講一下什麼是連結清單：首先連結清單是一種
線性的資料結構
（其他資料結構還有，
樹
、
圖
），是在每一個節點裡存到下一個節點（
next
）的指針（
Pointer
）。
連結清單最大的好處則是采用了
見縫插針的方式
，連結清單中的
每一個節點分布在記憶體的不同位置
（連結清單不需要一塊連續完整的空間），依靠
next
指針關聯起來。這樣可以
靈活有效地利用零散的碎片空間
。由于不必須按順序存儲，連結清單的插入和删除操作可以達到 O(1) 的複雜度。
而雙向連結清單比單向連結清單稍微複雜一些（僅僅一些），它的每一個節點除了擁有
data
和
next
指針，還擁有指向前置節點的
prev
指針。意思就是：
單向連結清單隻可以通路到下一個節點
，而
雙向連結清單不僅可以通路下一個節點還可以通路上一個節點
。
雙向連結清單
圖我懶的畫出自：
https://zhuanlan.zhihu.com/p/29627391
，下面那個圖也是。
單向連結清單
LinkedList 實作
大家如果看過 LinkedList 就可以發現它就是使用雙向連結清單實作的，這裡使用兩個 LinkedList 提供的方法說明一下其背後的實作原理，就使用一個 add() 方法加一個 remove() 方法吧。
node 構造器
private static class Node<E> {
E item;
/*
從屬性可以看出來是雙向連結清單
next -> 下一個節點; prev -> 上一個節點
*/
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
add()
方法，稍微注意一下：
add()
被重載了，下面的
add()
方法直接将元素追加到連結清單的尾部不需要指定下标，另外一個
add()
可以指定下标（index）進行插入資料操作。
// 方法入口
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
/*
1: 擷取當先的最後一個元素, 即: 尾部
2: 初始化 Node, 可以看到這裡直接将 l 一起也傳遞了過去, 因為之前說過
雙向連結清單不僅可以通路下一個節點還可以通路上一個節點.
現在插入了新的元素那麼原來的尾元素就成為了現在新的尾元素的上一個節點.
是以現在的尾元素的上一個節點是 l, 下一個節點一定是 null.
3: 将建立的新節點指定為 last 節點, 這裡 LinkedList 提供了 head、last 友善擷取以及指定擷取頭節點、尾節點
*/
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
/*
4: 這裡使用 final 修飾 l 也是很厲害的, 如果 l == null 就證明了是剛建立并且沒有使用的, 是以把新節點指定為 head(頭節點)
5：否則 l 的下一個節點 next 屬性直接指向新節點
6：連結清單大小 +1, 這裡的 size 也是 LinkedList 提供的一個屬性, 大家平時使用的 list.size() 方法就是直接傳回的這個 size
即: return size;
*/
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
remove()
，也是被重載了，我剛試了一下預設的直接
remove()
直接從 0 下标開始删除一位，另一個
remove()
是通過指定下标進行删除，最後一個通過指定值去删除。咱們在這裡要說的就是通過 index 下标去删除。
// 方法入口
public E remove(int index) {
/*
1: 檢查 index 是否越界. index >= 0 && index < size
2: 調用删除(實際就是 GC), 先擷取了 node 然後調用 unlink 方法.
*/
checkElementIndex(index);
return unlink(node(index));
}
// 擷取 Node 這裡使用了二分查找思想, 但并沒有像遞歸一樣, 而隻執行了一次.
Node<E> node(int index) {
/*
1: 判斷 index 範圍, 按位運算擷取當先連結清單 size 的中間值
2: 小于中間值則從 first 節點開始周遊也是就是前問說的 head
大于中間值則從 last 尾巴節點開始周遊, 這樣如果大量資料最不理想的情況下效率也是相同的
3: 傳回節點
*/
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;
}
}
// 調用删除(實際就是 GC)
E unlink(Node<E> x) {
/*
1: 擷取删除節點的元素, 沒有意義也不知道為什麼都要删除了為什麼還要擷取一下再傳回出去?
2: 擷取目前删除節點的下一個節點
3: 擷取目前删除節點的上一個節點
這裡包括上面之是以都使用 final 修飾變量, 是為了資料一緻性（原因之一）.
*/
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
/*
4: 如果删除節點的上一個節點是 null 就證明了它是頭節點 head, 将删除節點的下一個節點指定為 head
不是 null 則将**上一個節點的 next 指針指向删除節點的 next 節點**
然後将删除節點的上一個節點指針賦為 null, 等着被 GC, x.prev = null;
*/
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
/*
5: 如果 next 是 null 是證明删除節點沒有下一個節點, 則将删除節點的上一個節點指定為 last 節點
如果 next 不是 null 則将**下一個節點對上一個節點的指針修改為删除節點的上一個節點** 這句話有點繞一定要了解.
然後将删除節點的下一個節點指針賦為 null, 等着被 GC, x.next = null;
*/
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
/*
6: 到這一步 x.item = null; 一個 Node 中所有的屬性都已經是 null 了, 等着被 GC 回收就可以了
然後删除節點的上下節點指針已經更新完成, 已經完成了删除操作了 90% 了
7: size - 1, 目前連結清單的長度 -1
完畢.
*/
x.item = null;
size--;
modCount++;
return element;
}
自定義單向連結清單
下面關于單向連結清單的操作是最基本的，需要完善的地方還是有的。remove() 方法暫時隻提供了删除 head 元素，添加了一個檢查連結清單的方法。
public class LinkedTable {
private Node head;
private Node last;
private Long size = 0L;
public void linkLast(Object object) {
Node newNode = new Node(object);
if (size == 0) {
// first data
head = newNode;
last = newNode;
} else {
// last data
last.next = newNode;
last = newNode;
}
size++;
}
public void linkFirst(Object object) {
Node newNode = new Node(object);
newNode.next = head;
head = newNode;
size++;
}
private Object unlinkFirst(Node node) {
final Object o = node.object;
final Node next = node.next;
// call GC
head.object = null;
head.next = null;
head = next;
if (next == null) {
last = null;
}
size--;
return o;
}
public Object removeFirst() {
Node node = head;
if (node == null) {
throw new IndexOutOfBoundsException("Index out of length! ");
}
return unlinkFirst(node);
}
void add(Object object) {
linkLast(object);
}
void addLast(Object object) {
linkLast(object);
}
void addFirst(Object object) {
linkFirst(object);
}
Object getLast() {
return last.object;
}
Object getFirst() {
return head.object;
}
// check linked table
public void checkLinkedTable() {
Node node = head;
while (node != null) {
System.out.print(node.object.toString() + " ");
node = node.next;
}
System.out.println("");
}
public Object get(Long index) throws Exception {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of length! ");
}
if (index == 0) {
return head.object;
}
if (index == size - 1) {
return last.object;
}
Node node = head;
for (Long i = 0L; i < index; i++) {
node = node.next;
}
return node.object;
}
public Long getSize() {
return size;
}
private static class Node {
Object object;
Node next;
public Node(Object o) {
this.object = o;
}
}
}
驗證自定義單向連結清單
public class test {
public static void main(String...args) throws Exception {
LinkedTable linkedTable = new LinkedTable();
linkedTable.add("BKN481");
linkedTable.add("BKN482");
linkedTable.add("BKN483");
linkedTable.add("BKN484");
linkedTable.add("BKN485");
linkedTable.checkLinkedTable();
linkedTable.removeFirst();
System.out.println(linkedTable.getSize());
linkedTable.removeFirst();
System.out.println(linkedTable.getSize());
linkedTable.removeFirst();
System.out.println(linkedTable.getSize());
linkedTable.removeFirst();
System.out.println(linkedTable.getSize());
linkedTable.checkLinkedTable();
}
}
輸出：
BKN481 BKN482 BKN483 BKN484 BKN485
4
3
2
1
BKN485
完畢，歡迎批評指教。