Java數(shù)據(jù)結(jié)構(gòu)之雙向鏈表圖解
雙向鏈表(Doubly linked list)
什么是雙向鏈表?
雙向鏈表也叫雙鏈表,是鏈表的一種,它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針,分別指向直接后繼和直接前驅(qū)。所以,從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開(kāi)始,都可以很方便地訪問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。
雙向鏈表與單向鏈表的主要區(qū)別:
查找方向 : 單向鏈表的查找方向只能是一個(gè)方向,而雙向鏈表可以向前或者向后查找。
刪除: 單向鏈表的刪除需要借助輔助指針,先找到要?jiǎng)h除節(jié)點(diǎn)的前驅(qū),然后進(jìn)行刪除。
temp.next = temp.next.next;(temp為輔助指針)
雙向鏈表可以進(jìn)行自我刪除。
雙向鏈表與單向鏈表的優(yōu)劣:
優(yōu)點(diǎn):雙鏈表結(jié)構(gòu)比單鏈表結(jié)構(gòu)更有優(yōu)越性。
缺點(diǎn):從存儲(chǔ)結(jié)構(gòu)來(lái)看,雙向鏈表比單向鏈表多了一個(gè)指針,需要一個(gè)額外的、線性的內(nèi)存使用量。(在32位操作系統(tǒng)中一個(gè)指針為4個(gè)字節(jié),64位操作系統(tǒng)中一個(gè)指針為8個(gè)字節(jié))。
雙向鏈表的邏輯結(jié)構(gòu)圖解:
雙向鏈表的具體操作:
添加:
圖解:
代碼:
//添加一個(gè)節(jié)點(diǎn)到最后 ? ? public void add(DoubleNode newNode) { ? ? ? ? DoubleNode temp = head; ? ? ? ? while (true) { ? ? ? ? ? ? if (temp.next == null) { ? ? ? ? ? ? ? ? // 當(dāng)temp.next 為空時(shí),證明temp為最后一個(gè)元素。 ? ? ? ? ? ? ? ? temp.next = newNode; //temp節(jié)點(diǎn)的下一位指向新節(jié)點(diǎn) ? ? ? ? ? ? ? ? newNode.pre = temp;//新節(jié)點(diǎn)的前一位指向temp ? ? ? ? ? ? ? ? //這兩步構(gòu)成雙向鏈表 ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? }else if (temp.next.ID == newNode.ID) { ? ? ? ? ? ? ? ? //ID相同證明 已經(jīng)存在該學(xué)生。 ? ? ? ? ? ? ? ? System.out.printf("要插入學(xué)號(hào)為%d的學(xué)生已經(jīng)存在。\n", newNode.ID); ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? } ? ? ? ? ? ? temp = temp.next; ? ? ? ? } ? ? } ? ? ? //按學(xué)號(hào)順序添加節(jié)點(diǎn) ? ? public void Sortadd(DoubleNode newNode) { ? ? ? ? DoubleNode temp = head; ? ? ? ? while (true) { ? ? ? ? ? ? if (temp.next == null) { ? ? ? ? ? ? ? ? //說(shuō)明要添加的節(jié)點(diǎn)序號(hào)在當(dāng)前鏈表中最大,因此直接添加在末尾。 ? ? ? ? ? ? ? ? temp.next = newNode;//temp節(jié)點(diǎn)的下一位指向新節(jié)點(diǎn) ? ? ? ? ? ? ? ? newNode.pre = temp;//新節(jié)點(diǎn)的前一位指向temp ? ? ? ? ? ? ? ? //這兩步構(gòu)成雙向鏈表 ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? } else if (temp.next.ID > newNode.ID) { ? ? ? ? ? ? ? ? //當(dāng)前節(jié)點(diǎn)的下一位節(jié)點(diǎn)的編號(hào)大于 要添加的新節(jié)點(diǎn),則證明新節(jié)點(diǎn)要添加在temp節(jié)點(diǎn)之后 ? ? ? ? ? ? ? ? newNode.next = temp.next;//要添加節(jié)點(diǎn)的下一位 指向temp當(dāng)前節(jié)點(diǎn)的下一位 ? ? ? ? ? ? ? ? temp.next.pre = newNode;//temp當(dāng)前節(jié)點(diǎn)的下一位的前一位 指向 新節(jié)點(diǎn)構(gòu)成雙向鏈表 ? ? ? ? ? ? ? ? temp.next = newNode; // 再讓當(dāng)前節(jié)點(diǎn)的下一位指向 新節(jié)點(diǎn) ? ? ? ? ? ? ? ? newNode.pre = temp;//新節(jié)點(diǎn)的前一位 指向 當(dāng)前節(jié)點(diǎn)temp ? ? ? ? ? ? ? ? //這樣連接完成后就將 ?新節(jié)點(diǎn)插入 到 原本鏈表的temp節(jié)點(diǎn)與temp.next節(jié)點(diǎn)之間 ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? }else if (temp.next.ID == newNode.ID) { ? ? ? ? ? ? ? ? //ID相同證明 已經(jīng)存在該學(xué)生。 ? ? ? ? ? ? ? ? System.out.printf("要插入學(xué)號(hào)為%d的學(xué)生已經(jīng)存在。\n", newNode.ID); ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? } ? ? ? ? ? ? temp = temp.next; ? ? ? ? } ? ? }
刪除 :
圖解:
代碼:
?//刪除一個(gè)節(jié)點(diǎn)。 ? ? //自我刪除 ? ? 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("要?jiǎng)h除的%d節(jié)點(diǎn)不存在\n", id); ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? } else if (temp.ID == id) { ? ? ? ? ? ? ? ? //找到要?jiǎng)h除節(jié)點(diǎn) ? ? ? ? ? ? ? ? // 此時(shí)temp 就代表將要被刪除節(jié)點(diǎn) ? ? ? ? ? ? ? ? //temp.pre.next 指 當(dāng)前要被刪除節(jié)點(diǎn) 的前一位 的后一位 ? ? ? ? ? ? ? ? // temp.next ?指 當(dāng)前要被刪除節(jié)點(diǎn)的后一位 ? ? ? ? ? ? ? ? temp.pre.next = temp.next; ? ? ? ? ? ? ? ? // (當(dāng)前要被刪除節(jié)點(diǎn) 的前一位 的后一位)指向 (當(dāng)前要被刪除節(jié)點(diǎn)的后一位) ? ? ? ? ? ? ? ? //這樣就完成了 temp節(jié)點(diǎn)的刪除操作 ? ? ? ? ? ? ? ? ? // 如果是最后一個(gè)節(jié)點(diǎn),就不需要執(zhí)行下面這句話,否則出現(xiàn)空指針 ? ? ? ? ? ? ? ? if (temp.next != null) { ? ? ? ? ? ? ? ? ? ? temp.next.pre = temp.pre; ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? } ? ? ? ? ? ? temp = temp.next; ? ? ? ? } ? ? }
修改:
侃侃:它實(shí)際上與單鏈表的刪除是一樣。
代碼:
//修改鏈表節(jié)點(diǎn) ? ? 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é)點(diǎn) ? ? ? ? ? ? ? ? temp.name = newNode.name; ? ? ? ? ? ? ? ? temp.mark = newNode.mark; ? ? ? ? ? ? ? ? return; ? ? ? ? ? ? } ? ? ? ? ? ? temp = temp.next; ? ? ? ? } ? ? ? ? System.out.printf("要修改的%d節(jié)點(diǎn)不存在\n", newNode.ID); ? ? }
雙向鏈表實(shí)例:
用雙向鏈表創(chuàng)建一個(gè)學(xué)生信息管理系統(tǒng),完成對(duì)學(xué)生信息的添加,刪除,修改操作。
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; ? ? } ? ? ? //添加一個(gè)節(jié)點(diǎn)到最后 ? ? public void add(DoubleNode newNode) { ? ? ? ? DoubleNode temp = head; ? ? ? ? while (true) { ? ? ? ? ? ? if (temp.next == null) { ? ? ? ? ? ? ? ? // 當(dāng)temp.next 為空時(shí),證明temp為最后一個(gè)元素。 ? ? ? ? ? ? ? ? temp.next = newNode; //temp節(jié)點(diǎn)的下一位指向新節(jié)點(diǎn) ? ? ? ? ? ? ? ? newNode.pre = temp;//新節(jié)點(diǎn)的前一位指向temp ? ? ? ? ? ? ? ? //這兩步構(gòu)成雙向鏈表 ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? }else if (temp.next.ID == newNode.ID) { ? ? ? ? ? ? ? ? //ID相同證明 已經(jīng)存在該學(xué)生。 ? ? ? ? ? ? ? ? System.out.printf("要插入學(xué)號(hào)為%d的學(xué)生已經(jīng)存在。\n", newNode.ID); ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? } ? ? ? ? ? ? temp = temp.next; ? ? ? ? } ? ? } ? ? ? //按學(xué)號(hào)順序添加節(jié)點(diǎn) ? ? public void Sortadd(DoubleNode newNode) { ? ? ? ? DoubleNode temp = head; ? ? ? ? while (true) { ? ? ? ? ? ? if (temp.next == null) { ? ? ? ? ? ? ? ? //說(shuō)明要添加的節(jié)點(diǎn)序號(hào)在當(dāng)前鏈表中最大,因此直接添加在末尾。 ? ? ? ? ? ? ? ? temp.next = newNode;//temp節(jié)點(diǎn)的下一位指向新節(jié)點(diǎn) ? ? ? ? ? ? ? ? newNode.pre = temp;//新節(jié)點(diǎn)的前一位指向temp ? ? ? ? ? ? ? ? //這兩步構(gòu)成雙向鏈表 ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? } else if (temp.next.ID > newNode.ID) { ? ? ? ? ? ? ? ? //當(dāng)前節(jié)點(diǎn)的下一位節(jié)點(diǎn)的編號(hào)大于 要添加的新節(jié)點(diǎn),則證明新節(jié)點(diǎn)要添加在temp節(jié)點(diǎn)之后 ? ? ? ? ? ? ? ? newNode.next = temp.next;//要添加節(jié)點(diǎn)的下一位 指向temp當(dāng)前節(jié)點(diǎn)的下一位 ? ? ? ? ? ? ? ? temp.next.pre = newNode;//temp當(dāng)前節(jié)點(diǎn)的下一位的前一位 指向 新節(jié)點(diǎn)構(gòu)成雙向鏈表 ? ? ? ? ? ? ? ? temp.next = newNode; // 再讓當(dāng)前節(jié)點(diǎn)的下一位指向 新節(jié)點(diǎn) ? ? ? ? ? ? ? ? newNode.pre = temp;//新節(jié)點(diǎn)的前一位 指向 當(dāng)前節(jié)點(diǎn)temp ? ? ? ? ? ? ? ? //這樣連接完成后就將 ?新節(jié)點(diǎn)插入 到 原本鏈表的temp節(jié)點(diǎn)與temp.next節(jié)點(diǎn)之間 ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? }else if (temp.next.ID == newNode.ID) { ? ? ? ? ? ? ? ? //ID相同證明 已經(jīng)存在該學(xué)生。 ? ? ? ? ? ? ? ? System.out.printf("要插入學(xué)號(hào)為%d的學(xué)生已經(jīng)存在。\n", newNode.ID); ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? } ? ? ? ? ? ? temp = temp.next; ? ? ? ? } ? ? } ? ? ? //刪除一個(gè)節(jié)點(diǎn)。 ? ? //自我刪除 ? ? 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("要?jiǎng)h除的%d節(jié)點(diǎn)不存在\n", id); ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? } else if (temp.ID == id) { ? ? ? ? ? ? ? ? //找到要?jiǎng)h除節(jié)點(diǎn) ? ? ? ? ? ? ? ? // 此時(shí)temp 就代表將要被刪除節(jié)點(diǎn) ? ? ? ? ? ? ? ? //temp.pre.next 指 當(dāng)前要被刪除節(jié)點(diǎn) 的前一位 的后一位 ? ? ? ? ? ? ? ? // temp.next ?指 當(dāng)前要被刪除節(jié)點(diǎn)的后一位 ? ? ? ? ? ? ? ? temp.pre.next = temp.next; ? ? ? ? ? ? ? ? // (當(dāng)前要被刪除節(jié)點(diǎn) 的前一位 的后一位)指向 (當(dāng)前要被刪除節(jié)點(diǎn)的后一位) ? ? ? ? ? ? ? ? //這樣就完成了 temp節(jié)點(diǎn)的刪除操作 ? ? ? ? ? ? ? ? ? // 如果是最后一個(gè)節(jié)點(diǎn),就不需要執(zhí)行下面這句話,否則出現(xiàn)空指針 ? ? ? ? ? ? ? ? if (temp.next != null) { ? ? ? ? ? ? ? ? ? ? temp.next.pre = temp.pre; ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? } ? ? ? ? ? ? temp = temp.next; ? ? ? ? } ? ? } ? ? ? //修改鏈表節(jié)點(diǎn) ? ? 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é)點(diǎn) ? ? ? ? ? ? ? ? temp.name = newNode.name; ? ? ? ? ? ? ? ? temp.mark = newNode.mark; ? ? ? ? ? ? ? ? return; ? ? ? ? ? ? } ? ? ? ? ? ? temp = temp.next; ? ? ? ? } ? ? ? ? System.out.printf("要修改的%d節(jié)點(diǎn)不存在\n", newNode.ID); ? ? } ? ? ? public void ShowList() { ? ? ? ? // 判斷鏈表是否為空 ? ? ? ? if (head.next == null) { ? ? ? ? ? ? System.out.println("鏈表為空"); ? ? ? ? ? ? return; ? ? ? ? } ? ? ? ? // 因?yàn)轭^節(jié)點(diǎn),不能動(dòng),因此我們需要一個(gè)輔助變量來(lái)遍歷 ? ? ? ? DoubleNode temp = head.next; ? ? ? ? while (true) { ? ? ? ? ? ? // 判斷是否到鏈表最后 ? ? ? ? ? ? if (temp == null) { ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? } ? ? ? ? ? ? System.out.println(temp);// 輸出節(jié)點(diǎn)的信息 ? ? ? ? ? ? temp = temp.next; ? ? ? ? } ? ? } } ? class DoubleNode { ? ? public int ID; // 編號(hào)。 ? ? public String name; ? ? public int mark; ? ? public DoubleNode next; ? ? public DoubleNode pre; // 前一個(gè)(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 + '}'; ? ? } }
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
SpringBoot項(xiàng)目中定時(shí)器的實(shí)現(xiàn)示例
在Spring?Boot項(xiàng)目中,你可以使用Spring框架提供的@Scheduled注解來(lái)編寫(xiě)定時(shí)任務(wù),本文就來(lái)介紹一下SpringBoot項(xiàng)目中定時(shí)器的實(shí)現(xiàn),感興趣的可以了解一下2023-11-11使用SpringBoot中web項(xiàng)目推薦目錄結(jié)構(gòu)的問(wèn)題
這篇文章主要介紹了SpringBoot中web項(xiàng)目推薦目錄結(jié)構(gòu)的問(wèn)題,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-01-01java 學(xué)習(xí)筆記(入門篇)_java程序helloWorld
安裝配置完Java的jdk,下面就開(kāi)始寫(xiě)第一個(gè)java程序--hello World.用來(lái)在控制臺(tái)輸出“Hello World”,接下來(lái)詳細(xì)介紹,感興趣的朋友可以參考下2013-01-01mybatis-plus內(nèi)置雪花算法主鍵重復(fù)問(wèn)題解決
本文主要介紹了mybatis-plus內(nèi)置雪花算法主鍵重復(fù)問(wèn)題解決,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-09-09Java中的大數(shù)類簡(jiǎn)單實(shí)現(xiàn)
這篇文章主要介紹了Java中的大數(shù)類簡(jiǎn)單實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下2017-03-03Java線程通訊的實(shí)現(xiàn)方法總結(jié)
線程通訊指的是多個(gè)線程之間通過(guò)共享內(nèi)存或消息傳遞等方式來(lái)協(xié)調(diào)和同步它們的執(zhí)行,線程通訊的實(shí)現(xiàn)方式主要有以下兩種:共享內(nèi)存和消息傳遞,本文詳細(xì)介紹了Java線程是如何通訊的,感興趣的同學(xué)可以參考閱讀2023-05-05java實(shí)現(xiàn)多文件上傳至本地服務(wù)器功能
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)多文件上傳至本地服務(wù)器功能,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-01-01