Java數(shù)據(jù)結構之雙向鏈表圖解

更新時間：2022年05月26日 14:46:27 作者：@李思成

這篇文章主要為大家詳細介紹了Java數(shù)據(jù)結構之雙向鏈表，文中圖解分析的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

雙向鏈表（Doubly linked list）

什么是雙向鏈表？

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅(qū)結點和后繼結點。

雙向鏈表與單向鏈表的主要區(qū)別：

查找方向：單向鏈表的查找方向只能是一個方向，而雙向鏈表可以向前或者向后查找。
刪除：單向鏈表的刪除需要借助輔助指針，先找到要刪除節(jié)點的前驅(qū)，然后進行刪除。
temp.next = temp.next.next;(temp為輔助指針)
雙向鏈表可以進行自我刪除。

雙向鏈表與單向鏈表的優(yōu)劣：

優(yōu)點：雙鏈表結構比單鏈表結構更有優(yōu)越性。

缺點：從存儲結構來看，雙向鏈表比單向鏈表多了一個指針，需要一個額外的、線性的內(nèi)存使用量。（在32位操作系統(tǒng)中一個指針為4個字節(jié)，64位操作系統(tǒng)中一個指針為8個字節(jié)）。

雙向鏈表的邏輯結構圖解：

雙向鏈表的具體操作：

添加：
圖解：

代碼：

//添加一個節(jié)點到最后
? ? public void add(DoubleNode newNode) {
? ? ? ? DoubleNode temp = head;
? ? ? ? while (true) {
? ? ? ? ? ? if (temp.next == null) {
? ? ? ? ? ? ? ? // 當temp.next 為空時，證明temp為最后一個元素。
? ? ? ? ? ? ? ? temp.next = newNode; //temp節(jié)點的下一位指向新節(jié)點
? ? ? ? ? ? ? ? newNode.pre = temp;//新節(jié)點的前一位指向temp
? ? ? ? ? ? ? ? //這兩步構成雙向鏈表
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }else if (temp.next.ID == newNode.ID) {
? ? ? ? ? ? ? ? //ID相同證明 已經(jīng)存在該學生。
? ? ? ? ? ? ? ? System.out.printf("要插入學號為%d的學生已經(jīng)存在。\n", newNode.ID);
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? temp = temp.next;
? ? ? ? }
? ? }
?
? ? //按學號順序添加節(jié)點
? ? public void Sortadd(DoubleNode newNode) {
? ? ? ? DoubleNode temp = head;
? ? ? ? while (true) {
? ? ? ? ? ? if (temp.next == null) {
? ? ? ? ? ? ? ? //說明要添加的節(jié)點序號在當前鏈表中最大，因此直接添加在末尾。
? ? ? ? ? ? ? ? temp.next = newNode;//temp節(jié)點的下一位指向新節(jié)點
? ? ? ? ? ? ? ? newNode.pre = temp;//新節(jié)點的前一位指向temp
? ? ? ? ? ? ? ? //這兩步構成雙向鏈表
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? } else if (temp.next.ID > newNode.ID) {
? ? ? ? ? ? ? ? //當前節(jié)點的下一位節(jié)點的編號大于 要添加的新節(jié)點，則證明新節(jié)點要添加在temp節(jié)點之后
? ? ? ? ? ? ? ? newNode.next = temp.next;//要添加節(jié)點的下一位 指向temp當前節(jié)點的下一位
? ? ? ? ? ? ? ? temp.next.pre = newNode;//temp當前節(jié)點的下一位的前一位 指向 新節(jié)點構成雙向鏈表
? ? ? ? ? ? ? ? temp.next = newNode; // 再讓當前節(jié)點的下一位指向 新節(jié)點
? ? ? ? ? ? ? ? newNode.pre = temp;//新節(jié)點的前一位 指向 當前節(jié)點temp
? ? ? ? ? ? ? ? //這樣連接完成后就將 ?新節(jié)點插入 到 原本鏈表的temp節(jié)點與temp.next節(jié)點之間
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }else if (temp.next.ID == newNode.ID) {
? ? ? ? ? ? ? ? //ID相同證明 已經(jīng)存在該學生。
? ? ? ? ? ? ? ? System.out.printf("要插入學號為%d的學生已經(jīng)存在。\n", newNode.ID);
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? temp = temp.next;
? ? ? ? }
? ? }

刪除：
圖解：

代碼：

?//刪除一個節(jié)點。
? ? //自我刪除
? ? 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節(jié)點不存在\n", id);
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? } else if (temp.ID == id) {
? ? ? ? ? ? ? ? //找到要刪除節(jié)點
? ? ? ? ? ? ? ? // 此時temp 就代表將要被刪除節(jié)點
? ? ? ? ? ? ? ? //temp.pre.next 指 當前要被刪除節(jié)點 的前一位 的后一位
? ? ? ? ? ? ? ? // temp.next ?指 當前要被刪除節(jié)點的后一位
? ? ? ? ? ? ? ? temp.pre.next = temp.next;
? ? ? ? ? ? ? ? // （當前要被刪除節(jié)點 的前一位 的后一位）指向 （當前要被刪除節(jié)點的后一位）
? ? ? ? ? ? ? ? //這樣就完成了 temp節(jié)點的刪除操作
?
? ? ? ? ? ? ? ? // 如果是最后一個節(jié)點，就不需要執(zhí)行下面這句話，否則出現(xiàn)空指針
? ? ? ? ? ? ? ? if (temp.next != null) {
? ? ? ? ? ? ? ? ? ? temp.next.pre = temp.pre;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? temp = temp.next;
? ? ? ? }
? ? }

修改：
侃侃：它實際上與單鏈表的刪除是一樣。

代碼：

//修改鏈表節(jié)點
? ? 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) {
? ? ? ? ? ? ? ? //找到要修改的節(jié)點
? ? ? ? ? ? ? ? temp.name = newNode.name;
? ? ? ? ? ? ? ? temp.mark = newNode.mark;
? ? ? ? ? ? ? ? return;
? ? ? ? ? ? }
? ? ? ? ? ? temp = temp.next;
? ? ? ? }
? ? ? ? System.out.printf("要修改的%d節(jié)點不存在\n", newNode.ID);
? ? }

雙向鏈表實例：

用雙向鏈表創(chuàng)建一個學生信息管理系統(tǒng)，完成對學生信息的添加，刪除，修改操作。

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;
? ? }
?
? ? //添加一個節(jié)點到最后
? ? public void add(DoubleNode newNode) {
? ? ? ? DoubleNode temp = head;
? ? ? ? while (true) {
? ? ? ? ? ? if (temp.next == null) {
? ? ? ? ? ? ? ? // 當temp.next 為空時，證明temp為最后一個元素。
? ? ? ? ? ? ? ? temp.next = newNode; //temp節(jié)點的下一位指向新節(jié)點
? ? ? ? ? ? ? ? newNode.pre = temp;//新節(jié)點的前一位指向temp
? ? ? ? ? ? ? ? //這兩步構成雙向鏈表
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }else if (temp.next.ID == newNode.ID) {
? ? ? ? ? ? ? ? //ID相同證明 已經(jīng)存在該學生。
? ? ? ? ? ? ? ? System.out.printf("要插入學號為%d的學生已經(jīng)存在。\n", newNode.ID);
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? temp = temp.next;
? ? ? ? }
? ? }
?
? ? //按學號順序添加節(jié)點
? ? public void Sortadd(DoubleNode newNode) {
? ? ? ? DoubleNode temp = head;
? ? ? ? while (true) {
? ? ? ? ? ? if (temp.next == null) {
? ? ? ? ? ? ? ? //說明要添加的節(jié)點序號在當前鏈表中最大，因此直接添加在末尾。
? ? ? ? ? ? ? ? temp.next = newNode;//temp節(jié)點的下一位指向新節(jié)點
? ? ? ? ? ? ? ? newNode.pre = temp;//新節(jié)點的前一位指向temp
? ? ? ? ? ? ? ? //這兩步構成雙向鏈表
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? } else if (temp.next.ID > newNode.ID) {
? ? ? ? ? ? ? ? //當前節(jié)點的下一位節(jié)點的編號大于 要添加的新節(jié)點，則證明新節(jié)點要添加在temp節(jié)點之后
? ? ? ? ? ? ? ? newNode.next = temp.next;//要添加節(jié)點的下一位 指向temp當前節(jié)點的下一位
? ? ? ? ? ? ? ? temp.next.pre = newNode;//temp當前節(jié)點的下一位的前一位 指向 新節(jié)點構成雙向鏈表
? ? ? ? ? ? ? ? temp.next = newNode; // 再讓當前節(jié)點的下一位指向 新節(jié)點
? ? ? ? ? ? ? ? newNode.pre = temp;//新節(jié)點的前一位 指向 當前節(jié)點temp
? ? ? ? ? ? ? ? //這樣連接完成后就將 ?新節(jié)點插入 到 原本鏈表的temp節(jié)點與temp.next節(jié)點之間
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }else if (temp.next.ID == newNode.ID) {
? ? ? ? ? ? ? ? //ID相同證明 已經(jīng)存在該學生。
? ? ? ? ? ? ? ? System.out.printf("要插入學號為%d的學生已經(jīng)存在。\n", newNode.ID);
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? temp = temp.next;
? ? ? ? }
? ? }
?
? ? //刪除一個節(jié)點。
? ? //自我刪除
? ? 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節(jié)點不存在\n", id);
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? } else if (temp.ID == id) {
? ? ? ? ? ? ? ? //找到要刪除節(jié)點
? ? ? ? ? ? ? ? // 此時temp 就代表將要被刪除節(jié)點
? ? ? ? ? ? ? ? //temp.pre.next 指 當前要被刪除節(jié)點 的前一位 的后一位
? ? ? ? ? ? ? ? // temp.next ?指 當前要被刪除節(jié)點的后一位
? ? ? ? ? ? ? ? temp.pre.next = temp.next;
? ? ? ? ? ? ? ? // （當前要被刪除節(jié)點 的前一位 的后一位）指向 （當前要被刪除節(jié)點的后一位）
? ? ? ? ? ? ? ? //這樣就完成了 temp節(jié)點的刪除操作
?
? ? ? ? ? ? ? ? // 如果是最后一個節(jié)點，就不需要執(zhí)行下面這句話，否則出現(xiàn)空指針
? ? ? ? ? ? ? ? if (temp.next != null) {
? ? ? ? ? ? ? ? ? ? temp.next.pre = temp.pre;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? temp = temp.next;
? ? ? ? }
? ? }
?
? ? //修改鏈表節(jié)點
? ? 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) {
? ? ? ? ? ? ? ? //找到要修改的節(jié)點
? ? ? ? ? ? ? ? temp.name = newNode.name;
? ? ? ? ? ? ? ? temp.mark = newNode.mark;
? ? ? ? ? ? ? ? return;
? ? ? ? ? ? }
? ? ? ? ? ? temp = temp.next;
? ? ? ? }
? ? ? ? System.out.printf("要修改的%d節(jié)點不存在\n", newNode.ID);
? ? }
?
? ? public void ShowList() {
? ? ? ? // 判斷鏈表是否為空
? ? ? ? if (head.next == null) {
? ? ? ? ? ? System.out.println("鏈表為空");
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? // 因為頭節(jié)點，不能動，因此我們需要一個輔助變量來遍歷
? ? ? ? DoubleNode temp = head.next;
? ? ? ? while (true) {
? ? ? ? ? ? // 判斷是否到鏈表最后
? ? ? ? ? ? if (temp == null) {
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? System.out.println(temp);// 輸出節(jié)點的信息
? ? ? ? ? ? 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 + '}';
? ? }
}

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

java中的Arrays這個工具類你真的會用嗎(一文秒懂)
這篇文章主要介紹了java中的Arrays這個工具類你真的會用嗎,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2020-06-06
Rxjava功能操作符的使用方法詳解
這篇文章主要介紹了Rxjava功能操作符的使用方法詳解，還是比較不錯的，這里分享給大家，供需要的朋友參考。
2017-11-11
RocketMQ根據(jù)Tag進行消息過濾
消費者訂閱了某個主題后，Apache RocketMQ 會將該主題中的所有消息投遞給消費者。若消費者只需要關注部分消息，可通過設置過濾條件在 Apache RocketMQ 服務端進行過濾，只獲取到需要關注的消息子集，避免接收到大量無效的消息
2023-02-02
Mybatis如何從數(shù)據(jù)庫中獲取數(shù)據(jù)存為List類型(存為model)
這篇文章主要介紹了Mybatis如何從數(shù)據(jù)庫中獲取數(shù)據(jù)存為List類型(存為model)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2022-01-01
詳解Java的MyBatis框架和Spring框架的整合運用
在Web端的SSH框架整合中Spring主要負責數(shù)據(jù)庫處理,而引入MyBatis后二者的集成使用效果更佳,下面我們就來詳解Java的MyBatis框架和Spring框架的整合運用
2016-06-06
網(wǎng)關Spring Cloud Gateway HTTP超時配置問題
這篇文章主要介紹了網(wǎng)關Spring Cloud Gateway HTTP超時配置問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
2024-01-01
詳解基于SpringBoot使用AOP技術實現(xiàn)操作日志管理
這篇文章主要介紹了詳解基于SpringBoot使用AOP技術實現(xiàn)操作日志管理，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2019-11-11
深入分析Android系統(tǒng)中SparseArray的源碼
這篇文章主要介紹了深入分析Android系統(tǒng)中SparseArray的源碼,SparseArray為Java實現(xiàn),需要的朋友可以參考下
2015-07-07
使用nexus3.X上傳本地jar包并且通過pom讀取的解決方案(全網(wǎng)最新)
這篇文章主要介紹了使用nexus3.X上傳本地jar包并且通過pom讀取的解決方案(全網(wǎng)最新),本文內(nèi)容有點長，結合圖文實例給大家講解的非常詳細，需要的朋友可以參考下
2023-11-11
Java的集合其實就是各種基本的數(shù)據(jù)結構(棧,隊列,hash表等),基于業(yè)務需求進而演變出的Java特有的數(shù)據(jù)結構(因為不僅僅是基本數(shù)據(jù)結構),這篇文章主要給大家介紹了關于Java集合和數(shù)據(jù)結構排序的相關資料,需要的朋友可以參考下
2021-08-08