雙向連結清單、雙端(雙向)連結清單、循環(雙向)連結清單示意(簡)圖：
聲明：下面各圖中，箭頭指向的是整個節點，而不是指向節點中的prior或next。
雙向連結清單：隻有一個指針指向最開始的結點。
雙端(雙向)連結清單：有兩個指針分别指向兩端的節點。
循環(雙向)連結清單：指向形成一個閉環。
雙端(雙向)連結清單的Java實作(簡單示例)：
注：雙向連結清單、雙端(雙向)連結清單、循環(雙向)連結清單的實作思路幾乎一樣，這裡以實作雙端(雙向)連結清單示例。
/**
* 雙端(雙向)連結清單的(簡單)實作
*
* @author JustryDeng
* @date 2019/5/21 20:51
*/
public class DoublesidedLinkedlistImpl<T> {
/** 節點的個數 */
private int size;
/**
* 尾節點
* 注:本人新增節點時，從尾巴上新增
* 注:也可以從頭上進行新增節點
*/
private Node rear;
/**
* 目前節點
* 即:連結清單中最前面的節點，可了解為 隊列中的頭結點
*/
private Node head;
/**
* 成員内部類， 節點
*/
private class Node {
/** 内部類的元素,Object類型 */
private T data;
/** 上一個節點(即:前驅節點)的位址 */
private Node prior;
/** 下一個節點(即:後繼節點)的位址 */
private Node next;
private Node(T data) {
this.data = data;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node getPrior() {
return prior;
}
public void setPrior(Node prior) {
this.prior = prior;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
/**
* 新增節點
*
* @param obj
* 添加的元素
* @return 添加的元素對應的節點
* @date 2019/5/20 20:48
*/
public Node addNode(T obj) {
// obj不能為null
notNullCheck(obj);
// 每次增加的元素，都作為新的尾節點
Node newRear = new Node(obj);
if (size == 0) {
head = newRear;
rear = newRear;
} else {
newRear.prior = rear;
rear.next = newRear;
// 更新尾節點
rear = rear.next;
}
size++;
return newRear;
}
/**
* 删除目前(頭)節點
*
* @return 被删除了的(頭)節點
* @date 2019/5/20 20:50
*/
public Node deleteHead() {
if(isEmpty()) {
return null;
}
// targetObj存放原來的頭節點資料
Node targetNode = head;
if (head.next != null) {
// 斷開後繼節點對要删除的節點的引用
head.next.prior = null;
}
// 更新頭節點
head = head.next;
size--;
return targetNode;
}
/**
* 删除指定元素對應的第一個節點
*
* @return 删除成功與否(若元素不存在，則傳回false)
* @date 2019/5/20 20:50
*/
public boolean deleteFirstNode(T obj) {
// obj不能為null
notNullCheck(obj);
// 當head未null時，說明，目前為空連結清單
if (size == 0) {
return false;
}
// 目前節點
Node current = head;
// 前驅節點
Node previous = head;
// 判斷條件，如果目前節點的值和待删除的值不一緻，則繼續
while (!obj.equals(current.data)) {
// 如果下一個節點不存在(即:目前節點是尾節點)
// 則說明，不存在 元素值為obj的節點，直接傳回false
if (current.next == null) {
return false;
} else {
// 更新前驅節點、目前節點
previous = current;
current = current.next;
}
}
// 如果要删除的節點是第一個節點；
if (head.equals(current)) {
if (head.next != null) {
// 斷開後繼節點對要删除的節點的引用
head.next.prior = null;
}
// 更新頭結點
head = current.next;
// 如果要删除的節點是尾節點
} else if ((rear.equals(current))) {
// 前驅節點斷開對要删除的節點的應用
previous.next = null;
// 如果要删除的節點不是頭結點(是中間的某個節點或尾節點)
} else {
// 将目前節點“摳除”，并将“兩端”接上
previous.next = current.next;
current.prior = previous;
}
size--;
return true;
}
/**
* 删除指定元素對應的所有節點
* 注:此方法性能較低，少用或不用
*
*
* @return 删除了的節點數
* @date 2019/5/20 20:50
*/
public int deleteAllNode(T obj) {
int count = 0;
while(deleteFirstNode(obj)){
count++;
}
return count;
}
/**
* 查找元素的(第一個)節點
*
* @param obj
* 待查找的元素對象
* @return 元素的(第一個)節點, 無則傳回null
*/
public Node find(T obj) {
// obj不能為null
notNullCheck(obj);
Node currNode = head;
// 臨時大小為size
int tempSize = size;
while (tempSize > 0) {
if (obj.equals(currNode.data)) {
return currNode;
} else {
currNode = currNode.next;
}
tempSize--;
}
return null;
}
/**
* 非空檢驗
*
* @param obj
* 被驗證的對象
* @throws NullPointerException 空指針異常(運作時異常)
* @date 2019/5/20 21:00
*/
private void notNullCheck(T obj){
if(obj == null) {
throw new NullPointerException("data must not be null!");
}
}
/**
* 判斷連結清單是否為空
*
* @return 連結清單是否為空
* @date 2019/5/20 20:49
*/
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
if (isEmpty()) {
return "[]";
}
StringBuilder sb = new StringBuilder(16);
sb.append("[");
Node currentNode = head;
for (int i = 0; i < size; i++) {
sb.append(currentNode.data);
sb.append(", ");
currentNode = currentNode.next;
}
int length = sb.length();
sb.delete(length - 2, length).append("]");
return sb.toString();
}
public static void main(String[] args) {
DoublesidedLinkedlistImpl<String> uli = new DoublesidedLinkedlistImpl<>();
// 增
uli.addNode("A");
uli.addNode("B");
uli.addNode("C");
uli.addNode("C");
uli.addNode("D");
uli.addNode("C");
uli.addNode("E");
uli.addNode("E");
uli.addNode("F");
uli.addNode("E");
// toString
System.out.println("增加節點後的初始化連結清單:\t" + uli);
// 找到C元素對應的第一個節點
System.out.println("找到C元素對應的第一個節點:" + uli.find("C")
+ ",該節點的下下個節點的資料内容為:"
+ uli.find("C").getNext().getNext().getData());
// 删除頭結點
uli.deleteHead();
// toString
System.out.println("删除頭結點後:\t" + uli);
// 删除C元素對應的第一個節點
uli.deleteFirstNode("C");
// toString
System.out.println("删除C元素對應的第一個節點後:\t" +uli);
// 删除E元素對應的所有節點
uli.deleteAllNode("E");
// toString
System.out.println("删除E元素對應的所有節點後:\t" +uli);
}
}
測試一下：
運作(寫在實作類裡面的)主方法，控制台輸出：
由此可見：簡單的雙端(雙向)連結清單實作完畢！
^_^ 如有不當之處，歡迎指正
^_^ 學習視訊
51CTO學院《資料結構與算法》，講師張晨光