1、循環連結清單
我們之前說過了單連結清單，大家應該都有印象吧，那麼循環連結清單是什麼呢？
循環連結清單就是将單連結清單中終端結點的指針端自空指針改為指向頭結點，就使整個單連結清單形成一個環，這種頭尾相接的單連結清單稱為單循環連結清單，簡稱循環連結清單 (circular linked list) 。
那麼循環連結清單出現的目的是為什麼呢？
循環連結清單解決如何從當中一個結點出發，通路到連結清單的全部結點。
為了使空連結清單與非空連結清單處理一緻，我們通常設一個頭結點，當然，這并不是說，循環連結清單一定要頭結點，這需要注意。 結構圖如下：
其實循環連結清單與單連結清單主要差異主要展現在循環的判斷條件上，單連結清單判斷最後一個節點的指針域是否為空，而循環連結清單判斷最後一個節點的指針域是否為頭節點。
操作代碼可以參考我之前做的單連結清單的代碼，隻是在添加尾節點的時候将尾節點的指針域為空，改為指向頭指針。
2、雙向連結清單
終于到了最後一個連結清單結構了，雙向連結清單，那麼雙向連結清單又是什麼呢？
雙向連結清單 (double linked List) 是在單連結清單的每個結點中，再設定一個指向其前驅結點的指針域。是以在雙向連結清單中的結點都有兩個指針域， 一個指向直接後繼，另一個指向直接前驅。
那麼為什麼我們要設定這種連結清單結構呢？
主要是為了解決單連結清單，查找下一節點的時間複雜度為O(1)，但是查找上一節點的時間複雜度為O(n)的問題，也就是為了解決單連結清單的單一性查找的問題。
雙向連結清單可以是循環連結清單，也可以不是循環連結清單，但是我們一般還是用循環雙向連結清單偏多，畢竟使用起來比較友善。結構圖如下：
雙向連結清單是單連結清單中擴充出來的結構，是以它的很多操作是和單連結清單相同的，比如求長度的 ListLength ，查找元素的 GetElem，獲得元素位置的 LocateElem 等，這些操作都隻要涉及一個方向的指針即可，另一指針多了也不能提供什麼幫助。
雙向連結清單既然是比單連結清單多了如可以反向周遊查找等資料結構，那麼也就需要付出一些小的代價：在插入和删除時，需要更改兩個指針變化。
插入操作時其實并不複雜，不過順序很重要，如圖所示：
千萬不要寫反了，如果先執行4，再執行其他的，找不到後繼的位置，那麼插入就會失敗，
删除節點稍微簡單點，如圖所示：
操作代碼如下：
public class DoubleLinkList<T> {
private Node<T> headPoint;// 定義頭節點
private Node<T> tail;// 定義尾節點
/**
* 定義一個節點類
*
* @author 紫薇天钺
*
* @param <T>
*/
private static class Node<T> {
T data;// 泛型資料
Node<T> next;// 建構指針域，指向下一個節點
Node<T> prev;// 建構指針域，指向上一個節點
Node(T data) {// 節點的構造函數
this.data = data;
}
}
/**
* 添加頭節點
*/
public void addHeadPoint() {
this.headPoint = new Node<T>(null);// 建立一個空值節點指派給頭節點
}
/**
* 添加尾節點
*/
public void addTail(T data) {
this.tail = new Node<T>(data);// 建立一個節點指派給尾節點
this.tail.prev = headPoint;// 尾節點的前驅指針域指向頭節點
this.tail.next = headPoint;// 尾節點的後繼指針域指向頭節點
this.headPoint.next = tail;// 頭節點的後繼指針指向尾節點
this.headPoint.prev = tail;// 頭節點的前驅域指向尾節點
}
/**
* 使用頭部插入法添加節點
*/
public void insertNode(T data) {
if (this.headPoint == null) {// 如果頭節點為空，添加頭節點
addHeadPoint();
}
if (this.tail == null) {// 如果尾節點為空，添加尾節點
addTail(data);
}
Node<T> newNode = new Node<T>(data);// 建立一個新的節點
newNode.prev = this.headPoint;// 新節點的前驅域指向頭節點
newNode.next = this.headPoint.next;// 新節點的後繼域指向下一個節點
headPoint.next.prev = newNode;// 新節點的後繼節點的前驅域指向新節點
headPoint.next = newNode;// 頭節點的後繼域指向新節點
}
/**
* 在指定位置添加節點
*
* @param index
* @param node
* @throws Exception
*/
public void insertNodeByIndex(int index, Node<T> node) throws Exception {
if (index < 0 || index >= length()) {// 判斷新插入的位置是否正确
throw new Exception("插入的位置不合法");
}
int length = 1;// 定義我們周遊的長度
Node<T> temp = headPoint.next;// 從頭節點下一個節點開始周遊
while (temp != null) {// 如果連結清單不為空，并且插入的位置不在頭節點之前
if (index == length++) {// 到達指定位置，這裡到達的位置為插入位置的前一個節點
node.next = temp.next;// 将新節點的後繼域指向插入位置的前一個節點下一個節點
node.prev = temp;// 将新節點的前驅域指向插入位置的前一個節點
temp.next.prev = node;// 将插入位置的前一個節點的下一個節點前驅域指向新節點
temp.next = node;// 将插入位置的前一個節點後繼域指向新節點
return;
}
temp = temp.next;
}
}
/**
* 根據節點位置删除節點
*
* @param index
* @throws Exception
*/
public void deleteNodeByIndex(int index) throws Exception {
if (isEmpty()) {// 判斷連結清單是否為空
throw new Exception("連結清單為空，不能删除");
}
if (index < 0 || index >= length()) {// 判斷删除的位置是否正确
throw new Exception("删除的位置不合法");
}
int length = 1;// 開始周遊的位置
Node<T> temp = headPoint.next;// 循環節點
while (temp != null) {// 如果連結清單不為空，并且删除的位置不在頭節點之前
if (index == length++) {// 到達指定位置，這裡到達的位置為删除位置的前一個節點
temp.next = temp.next.next;
temp.next.prev = temp;
return;
}
temp = temp.next;
}
}
/**
* 判斷連結清單是否為空
*
* @return
*/
public Boolean isEmpty() {
return this.headPoint == null;
}
/**
* 擷取連結清單的長度
*
* @return
*/
public int length() {
int length = 0;
Node<T> temp = headPoint;
while (temp.next != headPoint) {
length++;
temp = temp.next;
}
return length;
}
/**
* 擷取節點的值
*
* @param i
* @return
*/
public T getValue(int i) {
Node<T> node = headPoint.next;
int j = 0;
while (node != null && j < i) {
node = node.next;
j++;
}
return node.data;
}
/**
* 測試
*
* @param ages
* @throws Exception
*/
public static void main(String ages[]) throws Exception {
DoubleLinkList<Integer> list = new DoubleLinkList<Integer>();
list.addHeadPoint();
list.addTail(999);
for (int j = 0; j < 10; j++) {
list.insertNode(j);
}
System.out.println("原連結清單資料：");
for (int k = 0; k < list.length(); k++) {
System.out.print(list.getValue(k) + " ");
}
list.insertNodeByIndex(7, new Node<Integer>(123));
list.deleteNodeByIndex(5);
System.out.println();
System.out.println("最新連結清單資料：");
for (int k = 0; k < list.length(); k++) {
System.out.print(list.getValue(k) + " ");
}
}
}
最終運作結果如下：
3、連結清單的總結回顧
線性表終于結束了，我們先談了它的定義，線性表是零個或多個具有相同類型的資料元素的有限序列。然後談了線性表的抽象資料類型，如它的一些基本操作。
之後我們就線性表的兩大結構做了講述，先講的是比較容易的順序存儲結構，指的是用一段位址連續的存儲單元依次存儲線性表的資料元素。通常我們都是用數組來實作這一結構。
後來是我們的重點，由順序存儲結構的插入和删除操作不友善，引出了鍊式存儲結構。它具有不受固定的存儲空間限制，可以比較快捷的插入和删除操作的特點。然後我們分别就鍊式存儲結構的不同形式，如單連結清單、循環連結清單和雙向連結清單做了講解。
總體示意圖如下：