java模擬實現雙向鏈表
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點
下圖是雙向鏈表的邏輯結構圖，和單鏈表不同的是，雙向鏈表中每個節點包含兩個節點的指針引用，和一個數據域，這兩個節點分別指向前一個節點和後一個節點；
雙向鏈表的這種結構比起單鏈表，其改進之處正在於此，通過對前後節點的引用可以使得在整個鏈表中，通過給定的值，可以從前或者向後遍歷，大大提升瞭遍歷查詢的效率，一定程度上解決瞭單鏈表的性能問題，但與此同時，鏈表的存儲開銷也增大瞭，我們熟悉的linkedList，其底層就是這個原理實現的.
廢話不多說，相信通過上面的解釋大傢已經很明白瞭，下面直接上代碼，可以結合代碼和圖結構理解雙向鏈表，
public class DoubleLinkTest<T> {
/**
* 內部構造節點類
*
* @param <T>
*/
private class Node<T> {
private T data;
private Node next; // 指向下一個節點的引用
private Node prev; // 指向前一個節點的引用
public Node(T data) {
this.data = data;
}
}
private Node<T> head; // 模擬頭結點
private Node<T> last; // 模擬尾部節點
private Node<T> other; // 暫定一個臨時節點，用作指針節點
private int length;
public void DoubleLinkTest() {
head = new Node<T>(null);
last = head;
length = 0;
}
public void DoubleLinkTest(T data) {
head = new Node<T>(data);
last = head;
length = 0;
}
/**
* 鏈表是否為空
*
* @return
*/
public boolean isEmpty() {
return length == 0;
}
/**
* 普通添加，往鏈表尾部添加
*
* @param data
*/
public void add(T data) {
if (isEmpty()) { // 鏈表為空，新創建一個鏈表
head = new Node<T>(data);
last = head;
length++;
} else {
other = new Node<T>(data);
other.prev = last;
last.next = other; // 將新的節點與原來的尾部節點進行結構上的關聯
last = other; // other將成為最後一個節點
length++;
}
}
/**
* 在指定的數據後面添加數據
*
* @param data
* @param insertData
*/
public void addAfter(T data, T insertData) {
other = head;
while (other != null) { // 我們假定這個head是不為空的。
if (other.data.equals(data)) {
Node<T> t = new Node<T>(insertData);
t.prev = other;
t.next = other.next;// 對新插入的數據進行一個指向的定義
other.next = t;
if (t.next == null) {
last = t;
}
length++;
}
other = other.next;
}
}
/**
* 刪除，刪除指定的數據
*
* @param data
*/
public void remove(T data) {
other = head;// 我們假定這個head是不為空的。
while (other != null) {
if (other.data.equals(data)) {
other.prev.next = other.next;
length--;
}
other = other.next;
}
}
/**
* 測試打印數據
*/
public void printList() {
other = head;
for (int i = 0; i < length; i++) {
System.out.println(other.data + " ");
other = other.next;
}
}
public static void main(String[] args) {
DoubleLinkTest<Integer> link = new DoubleLinkTest<Integer>();
link.add(1);
link.add(2);
link.add(3);
link.add(5);
link.add(6);
link.add(7);
link.printList();
System.out.println(" ============== ");
System.out.println(" ==== 在3後面添加一個數據開始========== ");
link.addAfter(3, 99);
link.printList();
System.out.println(" ==== 在3後面添加一個數據結束========== " + "\r\n");
System.out.println(" ==== 移除一個數據開始========== ");
link.remove(99);
link.printList();
System.out.println(" \r\n");
}
}
運行main函數，可以看到控制臺的打印輸出：
以上就是本文的全部內容，希望對大傢的學習有所幫助，也希望大傢多多支持WalkonNet。