本文源碼： GitHub·點這裡 || GitEE·點這裡
一、連結清單簡介
1、連結清單概念
連結清單是一種實體存儲單元上非連續、非順序的存儲結構，資料元素的邏輯順序是通過連結清單中的指針連結次序實作的。連結清單由一系列節點組成，節點可以在運作時動态生成，節點包括兩個部分：一個是存儲資料元素的資料域，另一個是存儲下一個結點位址的指針域。
2、基礎特點
記憶體存儲
邏輯結構
特點描述
- 實體存儲上是無序且不連續的；
- 連結清單是由多個節點以鍊式結構組成；
- 邏輯層面上看形成一個有序的鍊路結構；
連結清單結構解決數組存儲需要預先知道元素個數的缺陷，可以充分利用記憶體空間，實作靈活的記憶體動态管理。
二、單向連結清單
1、基礎描述
單向連結清單是連結清單的一種，其特點是連結清單的連結方向是單向的，連結清單的周遊要從頭部開始順序讀取；結點構成，head指針指向第一個成為表頭結點，終止于最後一個指向NULL的指針。
2、基礎操作
添加資料
- 初始化head節點，作為連結清單的頭；
- 修改目前末尾節點的next指針；
- 新添加的節點房子在連結清單末尾；
删除資料
周遊找到要删除的節點，把删除節點前個節點的指針指向該删除節點的下個節點；
三、雙向連結清單
1、概念描述
雙向連結清單也叫雙連結清單，是連結清單的一種，連結清單的每個資料結點中都有兩個指針，分别指向直接後繼和直接前驅，從雙向連結清單中的任意一個結點開始，都可以很快速地通路它的前驅結點和後繼結點，連結清單結構的使用多數都是構造雙向循環連結清單。
- 周遊找到連結清單的最後一個節點；
- 添加最新尾節點的prev指針；
- 雙向連結清單，基于要删除節點操作即可；
- 操作上圖中要删除的Node2節點；
- Node2.prev.next = Node2.next;
- Node2.next.prev = Node2.prev;
通過上述流程的操作，就把連結清單中一個節點删除，剩下節點再度連接配接成鍊式結構。
3、源碼分析
在Java的API中，LinkedList是典型的雙向連結清單結構，下面基于LinkedList源碼看雙向連結清單的操作。
基礎案例
public class M01_Linked {
public static void main(String[] args) {
List<User> userList = new LinkedList<>() ;
User removeUser = new User(200,"Second") ;
// 添加元素
userList.add(new User(100,"First")) ;
userList.add(removeUser) ;
userList.add(new User(300,"Third")) ;
System.out.println("初始化："+userList);
// 修改元素
userList.get(0).setUserName("Zero");
System.out.println("修改後："+userList);
// 删除元素
userList.remove(removeUser) ;
System.out.println("删除後："+userList);
}
}
class User {
private Integer userId ;
private String userName ;
public User(Integer userId, String userName) {
this.userId = userId;
this.userName = userName;
}
@Override
public String toString() {
return "User{" +
"userId=" + userId +
", userName='" + userName + '\'' +
'}';
}
// 省略Get和Set方法
} 節點描述
節點三個核心描述：資料，next指針，prev指針。
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;
}
} 首位節點處理
基于LinkedList源碼，首尾節點方式，針對上圖雙連結清單的首位指針特點，這裡源碼很好了解。
public class LinkedList {
transient Node<E> first;
transient Node<E> last;
// 處理首節點
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;
}
// 處理尾節點
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;
}
} 添加節點
添加節點的方法直接調用linkLast方法，把新節點放到連結清單的尾部即可。
public boolean add(E e) {
linkLast(e);
return true;
} 删除節點
第一步：周遊對比，找到要删除的節點；
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;
} 第二步：移除節點，重新搭建連結清單結構，并且把目前連結清單的資料置為null，并傳回被移除的節點；
E unlink(Node<E> x) {
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;
return element;
} 如上就是對Java中LinkedList雙連結清單源碼的部分結構分析，這種代碼看多了，總感覺自己寫的代碼不是Java。
四、環形連結清單
在單連結清單中，将終端結點的指針域NULL改為指向表頭結點或開始結點，這樣就形成了環形連結清單：
環形連結清單連結清單的一種結構，特點是表中最後一個結點的指針域指向頭結點，整個連結清單形成一個環。
五、源代碼位址
GitHub·位址
https://github.com/cicadasmile/model-arithmetic-parent
GitEE·位址
https://gitee.com/cicadasmile/model-arithmetic-parent