<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
Java資料結構之雙向連結串列圖解
2022-05-26 18:04:11
雙向連結串列（Doubly linked list）
什麼是雙向連結串列？
雙向連結串列也叫雙連結串列，是連結串列的一種，它的每個資料結點中都有兩個指標，分別指向直接後繼和直接前驅。所以，從雙向連結串列中的任意一個結點開始，都可以很方便地存取它的前驅結點和後繼結點。
雙向連結串列與單向連結串列的主要區別：
查詢方向 ： 單向連結串列的查詢方向只能是一個方向，而雙向連結串列可以向前或者向後查詢。
刪除： 單向連結串列的刪除需要藉助輔助指標，先找到要刪除節點的前驅，然後進行刪除。
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 + '}';
}
}以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支援it145.com。
相關文章
-
黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列
综合看Anker超能充系列的性价比很高，并且与不仅和iPhone12/苹果<em>Mac</em>Book很配，而且适合多设备充电需求的日常使用或差旅场景，不管是安卓还是Switch同样也能用得上它，希望这次分享能给准备购入充电器的小伙伴们有所
2021-06-01 09:31:42
-
吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！
除了L4WUDU与吴亦凡已经多次共事，成为了明面上的厂牌成员，吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节，这也是20XXCLUB首次全员合照，王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让
2021-06-01 09:31:34
-
IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？
目前应用IPFS的机构：1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆，历史资料永久保存在 IPFS 6 加
2021-06-01 09:31:24
-
有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊
开拓者的车机是兼容苹果和<em>安卓</em>，虽然我不怎么用，但确实兼顾了我家人的很多需求：副驾的门板还配有解锁开关，有的时候老婆开车，下车的时候偶尔会忘记解锁，我在副驾驶可以自己开门：第二排设计很好，不仅配置了一个很大的
2021-06-01 09:30:48
-
iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？
不仅是<em>安卓</em>手机，苹果手机的降价力度也是前所未有了，iPhone12也“跳水价”了，发布价是6799元，如今已经跌至5308元，降价幅度超过1400元，最新定价确认了。iPhone12是苹果首款5G手机，同时也是全球首款5nm芯片的智能机，它
2021-06-01 09:30:45