溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“Java數據結構之雙向鏈表如何實現”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Java數據結構之雙向鏈表如何實現”吧！
什么是雙向鏈表？
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。
雙向鏈表與單向鏈表的主要區別：
查找方向 ： 單向鏈表的查找方向只能是一個方向，而雙向鏈表可以向前或者向后查找。
刪除： 單向鏈表的刪除需要借助輔助指針，先找到要刪除節點的前驅，然后進行刪除。
temp.next = temp.next.next;(temp為輔助指針)
雙向鏈表可以進行自我刪除。
雙向鏈表與單向鏈表的優劣：
優點：雙鏈表結構比單鏈表結構更有優越性。
缺點：從存儲結構來看，雙向鏈表比單向鏈表多了一個指針，需要一個額外的、線性的內存使用量。（在32位操作系統中一個指針為4個字節，64位操作系統中一個指針為8個字節）。
雙向鏈表的邏輯結構圖解：
添加：
圖解：
代碼：
//添加一個節點到最后
public void add(DoubleNode newNode) {
DoubleNode temp = head;
while (true) {
if (temp.next == null) {
// 當temp.next 為空時，證明temp為最后一個元素。
temp.next = newNode; //temp節點的下一位指向新節點
newNode.pre = temp;//新節點的前一位指向temp
//這兩步構成雙向鏈表
break;
}else if (temp.next.ID == newNode.ID) {
//ID相同證明 已經存在該學生。
System.out.printf("要插入學號為%d的學生已經存在。\n", newNode.ID);
break;
}
temp = temp.next;
}
}
//按學號順序添加節點
public void Sortadd(DoubleNode newNode) {
DoubleNode temp = head;
while (true) {
if (temp.next == null) {
//說明要添加的節點序號在當前鏈表中最大，因此直接添加在末尾。
temp.next = newNode;//temp節點的下一位指向新節點
newNode.pre = temp;//新節點的前一位指向temp
//這兩步構成雙向鏈表
break;
} else if (temp.next.ID > newNode.ID) {
//當前節點的下一位節點的編號大于 要添加的新節點，則證明新節點要添加在temp節點之后
newNode.next = temp.next;//要添加節點的下一位 指向temp當前節點的下一位
temp.next.pre = newNode;//temp當前節點的下一位的前一位 指向 新節點構成雙向鏈表
temp.next = newNode; // 再讓當前節點的下一位指向 新節點
newNode.pre = temp;//新節點的前一位 指向 當前節點temp
//這樣連接完成后就將 新節點插入 到 原本鏈表的temp節點與temp.next節點之間
break;
}else if (temp.next.ID == newNode.ID) {
//ID相同證明 已經存在該學生。
System.out.printf("要插入學號為%d的學生已經存在。\n", newNode.ID);
break;
}
temp = temp.next;
}
}刪除 ：
圖解：
代碼：
//刪除一個節點。
//自我刪除
public void DoubleDelete(int id) {
if (head.next == null) {
System.out.println("鏈表為空！");
return;
}
DoubleNode temp = head.next;
while (true) {
if (temp == null) {
System.out.printf("要刪除的%d節點不存在\n", id);
break;
} else if (temp.ID == id) {
//找到要刪除節點
// 此時temp 就代表將要被刪除節點
//temp.pre.next 指 當前要被刪除節點 的前一位 的后一位
// temp.next 指 當前要被刪除節點的后一位
temp.pre.next = temp.next;
// （當前要被刪除節點 的前一位 的后一位）指向 （當前要被刪除節點的后一位）
//這樣就完成了 temp節點的刪除操作
// 如果是最后一個節點，就不需要執行下面這句話，否則出現空指針
if (temp.next != null) {
temp.next.pre = temp.pre;
}
break;
}
temp = temp.next;
}
}修改：
侃侃：它實際上與單鏈表的刪除是一樣。
代碼：
//修改鏈表節點
public void DoubleUpdate(DoubleNode newNode) {
if (head.next == null) {
System.out.println("鏈表為空！");
return;
}
DoubleNode temp = head.next;
while (true) {
if (temp == null) {
break;
} else if (temp.ID == newNode.ID) {
//找到要修改的節點
temp.name = newNode.name;
temp.mark = newNode.mark;
return;
}
temp = temp.next;
}
System.out.printf("要修改的%d節點不存在\n", newNode.ID);
}用雙向鏈表創建一個學生信息管理系統，完成對學生信息的添加，刪除，修改操作。
package Linkedlist;
//雙向鏈表。
public class DoubleLinkedListDemo {
public static void main(String agrs[]) {
DoubleNode stu1 = new DoubleNode(6, "張三", 99);
DoubleNode stu2 = new DoubleNode(2, "李四", 99);
DoubleNode stu3 = new DoubleNode(3, "王五", 99);
DoubleNode stu4 = new DoubleNode(5, "王二", 99);
DoubleNode stu5 = new DoubleNode(4, "小紅", 99);
DoubleNode stu6 = new DoubleNode(1, "小明", 99);
DoubleNode stu7 = new DoubleNode(1, "小明", 99);
DoubleLinkedlist doubleLinkedlist = new DoubleLinkedlist();
/* doubleLinkedlist.add(stu1);
doubleLinkedlist.add(stu2);
doubleLinkedlist.add(stu3);
doubleLinkedlist.add(stu4);
doubleLinkedlist.add(stu5);
doubleLinkedlist.add(stu6);
doubleLinkedlist.add(stu7);*/
doubleLinkedlist.Sortadd(stu1);
doubleLinkedlist.Sortadd(stu2);
doubleLinkedlist.Sortadd(stu3);
doubleLinkedlist.Sortadd(stu4);
doubleLinkedlist.Sortadd(stu5);
doubleLinkedlist.Sortadd(stu6);
doubleLinkedlist.add(stu7);
System.out.println("原鏈表展示！");
doubleLinkedlist.ShowList();
System.out.println();
doubleLinkedlist.DoubleDelete(6);
doubleLinkedlist.DoubleDelete(15);
System.out.println("刪除后鏈表展示！");
doubleLinkedlist.ShowList();
System.out.println();
DoubleNode stu8 = new DoubleNode(1, "李思成", 100);
DoubleNode stu9 = new DoubleNode(20, "李成", 100);
doubleLinkedlist.DoubleUpdate(stu8);
doubleLinkedlist.DoubleUpdate(stu9);
System.out.println("修改后鏈表展示！");
doubleLinkedlist.ShowList();
System.out.println();
}
}
class DoubleLinkedlist {
private DoubleNode head = new DoubleNode(0, "", 0);
public DoubleNode getHead() {
return head;
}
//添加一個節點到最后
public void add(DoubleNode newNode) {
DoubleNode temp = head;
while (true) {
if (temp.next == null) {
// 當temp.next 為空時，證明temp為最后一個元素。
temp.next = newNode; //temp節點的下一位指向新節點
newNode.pre = temp;//新節點的前一位指向temp
//這兩步構成雙向鏈表
break;
}else if (temp.next.ID == newNode.ID) {
//ID相同證明 已經存在該學生。
System.out.printf("要插入學號為%d的學生已經存在。\n", newNode.ID);
break;
}
temp = temp.next;
}
}
//按學號順序添加節點
public void Sortadd(DoubleNode newNode) {
DoubleNode temp = head;
while (true) {
if (temp.next == null) {
//說明要添加的節點序號在當前鏈表中最大，因此直接添加在末尾。
temp.next = newNode;//temp節點的下一位指向新節點
newNode.pre = temp;//新節點的前一位指向temp
//這兩步構成雙向鏈表
break;
} else if (temp.next.ID > newNode.ID) {
//當前節點的下一位節點的編號大于 要添加的新節點，則證明新節點要添加在temp節點之后
newNode.next = temp.next;//要添加節點的下一位 指向temp當前節點的下一位
temp.next.pre = newNode;//temp當前節點的下一位的前一位 指向 新節點構成雙向鏈表
temp.next = newNode; // 再讓當前節點的下一位指向 新節點
newNode.pre = temp;//新節點的前一位 指向 當前節點temp
//這樣連接完成后就將 新節點插入 到 原本鏈表的temp節點與temp.next節點之間
break;
}else if (temp.next.ID == newNode.ID) {
//ID相同證明 已經存在該學生。
System.out.printf("要插入學號為%d的學生已經存在。\n", newNode.ID);
break;
}
temp = temp.next;
}
}
//刪除一個節點。
//自我刪除
public void DoubleDelete(int id) {
if (head.next == null) {
System.out.println("鏈表為空！");
return;
}
DoubleNode temp = head.next;
while (true) {
if (temp == null) {
System.out.printf("要刪除的%d節點不存在\n", id);
break;
} else if (temp.ID == id) {
//找到要刪除節點
// 此時temp 就代表將要被刪除節點
//temp.pre.next 指 當前要被刪除節點 的前一位 的后一位
// temp.next 指 當前要被刪除節點的后一位
temp.pre.next = temp.next;
// （當前要被刪除節點 的前一位 的后一位）指向 （當前要被刪除節點的后一位）
//這樣就完成了 temp節點的刪除操作
// 如果是最后一個節點，就不需要執行下面這句話，否則出現空指針
if (temp.next != null) {
temp.next.pre = temp.pre;
}
break;
}
temp = temp.next;
}
}
//修改鏈表節點
public void DoubleUpdate(DoubleNode newNode) {
if (head.next == null) {
System.out.println("鏈表為空！");
return;
}
DoubleNode temp = head.next;
while (true) {
if (temp == null) {
break;
} else if (temp.ID == newNode.ID) {
//找到要修改的節點
temp.name = newNode.name;
temp.mark = newNode.mark;
return;
}
temp = temp.next;
}
System.out.printf("要修改的%d節點不存在\n", newNode.ID);
}
public void ShowList() {
// 判斷鏈表是否為空
if (head.next == null) {
System.out.println("鏈表為空");
return;
}
// 因為頭節點，不能動，因此我們需要一個輔助變量來遍歷
DoubleNode temp = head.next;
while (true) {
// 判斷是否到鏈表最后
if (temp == null) {
break;
}
System.out.println(temp);// 輸出節點的信息
temp = temp.next;
}
}
}
class DoubleNode {
public int ID; // 編號。
public String name;
public int mark;
public DoubleNode next;
public DoubleNode pre; // 前一個（Previous）
public DoubleNode(int ID, String name, int mark) {
this.ID = ID;
this.name = name;
this.mark = mark;
}
@Override
public String toString() {
return "DoubleNode{" + "ID=" + ID + ", name='" + name + '\'' + "mark=" + mark + '}';
}
}感謝各位的閱讀，以上就是“Java數據結構之雙向鏈表如何實現”的內容了，經過本文的學習后，相信大家對Java數據結構之雙向鏈表如何實現這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
