雙鏈表

本文是觀看尚硅谷韓老師數(shù)據(jù)結(jié)構(gòu)與算法根據(jù)老師講解自己做的筆記,部分信息收集網(wǎng)絡(luò)

與單鏈表區(qū)別

邏輯上沒有區(qū)別。他們均是完成線性表的內(nèi)容。主要的區(qū)別是結(jié)構(gòu)上的構(gòu)造有所區(qū)別。 對(duì)于單鏈表：

對(duì)于一個(gè)節(jié)點(diǎn)，有儲(chǔ)存數(shù)據(jù)的data。和next后驅(qū)節(jié)點(diǎn)(指針)。也就是這個(gè)單鏈表想要一些遍歷的操作都得通過前節(jié)點(diǎn)—>后節(jié)點(diǎn)。

對(duì)于雙鏈表：

對(duì)于一個(gè)節(jié)點(diǎn)，有些和單鏈表一樣有存儲(chǔ)數(shù)據(jù)的data,指向后方的next（指針）。它擁有單鏈表的所有操作和內(nèi)容。但是他還有一個(gè)前驅(qū)節(jié)點(diǎn)pre(指針)。

雙向鏈表應(yīng)用實(shí)例

雙向鏈表的操作分析和實(shí)現(xiàn)
使用帶 head 頭的雙向鏈表實(shí)現(xiàn)
管理單向鏈表的缺點(diǎn)分析:

單向鏈表，查找的方向只能是一個(gè)方向，而雙向鏈表可以向前或者向后查找。

單向鏈表不能自我刪除，需要靠輔助節(jié)點(diǎn) ，而雙向鏈表，則可以自我刪除，所以前面我們單鏈表刪除
時(shí)節(jié)點(diǎn)，總是找到 temp,temp 是待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)(認(rèn)真體會(huì)). 3) 分析了雙向鏈表如何完成遍歷，添加，修改和刪除的思路

對(duì)上圖的說明:
分析 雙向鏈表的遍歷，添加，修改，刪除的操作思路===》代碼實(shí)現(xiàn)

遍歷 方和 單鏈表一樣，只是可以向前，也可以向后查找

添加 (默認(rèn)添加到雙向鏈表的最后)
(1) 先找到雙向鏈表的最后這個(gè)節(jié)點(diǎn)
(2) temp.next = newHeroNode
(3) newHeroNode.pre = temp;

修改 思路和 原來的單向鏈表一樣. 4) 刪除
(1) 因?yàn)槭请p向鏈表，因此，我們可以實(shí)現(xiàn)自我刪除某個(gè)節(jié)點(diǎn)
(2) 直接找到要?jiǎng)h除的這個(gè)節(jié)點(diǎn)，比如 temp
(3) temp.pre.next = temp.next
(4) temp.next.pre = temp.pre;

代碼解釋

package com.fs.demo_2020_07_14_DoubleLinkedList;import java.util.Stack;/*** 雙鏈表 演示*/ public class SingleDoubleLinkedListDemo {public static void main(String[] args) {//測試雙鏈表的增刪改查SingleDoubleLinkedList singleDoubleLinkedList = new SingleDoubleLinkedList();//創(chuàng)建節(jié)點(diǎn)System.out.println("---------添加4個(gè)節(jié)點(diǎn)(1,2,3,4)------------");Node node1 = new Node(1, "節(jié)點(diǎn)一");Node node2 = new Node(2, "節(jié)點(diǎn)二");Node node3 = new Node(3, "節(jié)點(diǎn)三");Node node4 = new Node(4, "節(jié)點(diǎn)四");//添加節(jié)點(diǎn)singleDoubleLinkedList.add(node1);singleDoubleLinkedList.add(node2);singleDoubleLinkedList.add(node3);singleDoubleLinkedList.add(node4);//顯示一把System.out.println("----------------測試遍歷雙向鏈表---------------");singleDoubleLinkedList.showLinkedList();System.out.println("---------------測試添加節(jié)點(diǎn)到雙鏈表的最后----------------------");Node node5 = new Node(5, "節(jié)點(diǎn)五");singleDoubleLinkedList.add(node5);//顯示一把singleDoubleLinkedList.showLinkedList();System.out.println("----------刪除節(jié)點(diǎn)為3的---------------");singleDoubleLinkedList.delNode(3);//顯示一把singleDoubleLinkedList.showLinkedList();System.out.println("-----------修改節(jié)點(diǎn)5的數(shù)據(jù)為測試節(jié)點(diǎn)----------");singleDoubleLinkedList.updateByNum(new Node(5,"測試節(jié)點(diǎn)"));//顯示一把singleDoubleLinkedList.showLinkedList();}}//創(chuàng)建一個(gè)類來模擬雙鏈表 class SingleDoubleLinkedList {//先初始化一個(gè)頭節(jié)點(diǎn),頭節(jié)點(diǎn)不動(dòng),不存放具體信息private Node headNode = new Node(0, "頭結(jié)點(diǎn)");//生成一個(gè)get方法 返回頭結(jié)點(diǎn),便于后面的測試方法拿頭結(jié)點(diǎn)測試public Node getHeadNode() {return headNode;}/*一 添加一個(gè)節(jié)點(diǎn)到雙鏈表的最后思路:*/public void add(Node node) {//拿到初始化的頭結(jié)點(diǎn),作為輔助遍歷tempNode temp = headNode;//遍歷鏈表,找到最后的節(jié)點(diǎn)while (true) {//由圖解得知,單鏈表當(dāng)遍歷到最后一個(gè)節(jié)點(diǎn)后,next存儲(chǔ)的值為null.因?yàn)闆]有下一個(gè)節(jié)點(diǎn)可以存儲(chǔ)了if (temp.next == null) {//那就停止循環(huán)break;}//如果沒有找到最后,那就將temp后移一個(gè)節(jié)點(diǎn)temp = temp.next;}//循環(huán)結(jié)束后,所明temp到達(dá)最后一個(gè)節(jié)點(diǎn)了,那么就在最后一個(gè)節(jié)點(diǎn)后添加數(shù)據(jù),將temp的next存儲(chǔ)添加的節(jié)點(diǎn)值temp.next = node;//將指針指到的這個(gè)節(jié)點(diǎn)的next指向添加的節(jié)點(diǎn)node.pre = temp;//將添加的節(jié)點(diǎn)的pre指向temp}/*三 修改節(jié)點(diǎn)信息,根據(jù)num來修改,但是num不能修改,只能修改num節(jié)點(diǎn)的name*/public void updateByNum(Node newNode) {//還是先判斷鏈表是否為空,判斷頭部節(jié)點(diǎn)的下一位是否為空if (headNode.next == null) {System.out.println("鏈表為空~~~");return;}//找到需要修改的節(jié)點(diǎn),根據(jù)num號(hào)//定義一個(gè)輔助節(jié)點(diǎn),這次就不是頭結(jié)點(diǎn)了,因?yàn)轭^結(jié)點(diǎn)不能更改Node temp = headNode.next;//立一個(gè)flag,表示是否找到這個(gè)節(jié)點(diǎn)boolean flag = false;while (true) {if (temp == null) {break;//說明已經(jīng)遍歷完了}if (temp.num == newNode.num) {//說明找到flag = true;break;}//每次循環(huán)指針指向下一個(gè)temp = temp.next;}//根據(jù)flag來判斷是否找到要修改的節(jié)點(diǎn)if (flag) {//說明找到,就將新節(jié)數(shù)據(jù)賦值給遍歷到的這個(gè)節(jié)點(diǎn)temp.name = newNode.name;} else {//沒有找到System.out.println("沒有找到編號(hào)為:" + newNode.num + "的節(jié)點(diǎn)~~~");}}/*刪除節(jié)點(diǎn)思路:由于是雙鏈表結(jié)構(gòu),我們temp輔助指針指向后可以進(jìn)行自我刪除*/public void delNode(int num) {//判斷鏈表是否為空if (headNode.next == null) {System.out.println("鏈表為空~~~");return;}//同樣,標(biāo)志是否摘掉帶刪除的節(jié)點(diǎn)Node temp = headNode.next;//立flagboolean flag = false;while (true) {if (temp == null) {//已經(jīng)到達(dá)最后的節(jié)點(diǎn)break;}//因?yàn)楝F(xiàn)在temp指向誰,誰就是可以自我刪除if (temp.num == num) {//說明找到了刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)tempflag = true;break;}temp = temp.next;//循環(huán)后移}//判斷flagif (flag) {//說明找到,可以刪除temp.pre.next = temp.next;//先將temp前面的next指向temp.next,這樣temp就斷了一條//因?yàn)槲覀兛赡芤獎(jiǎng)h除的是最后一條,最后一條的temp.next為空//那么temp.next== null.pre就 一定會(huì)空指針異常if (temp.next != null) {temp.next.pre = temp.pre;//在將temp的后一個(gè)的pre指向temp的pre.這樣又?jǐn)嗔艘粭l,就實(shí)現(xiàn)了自我刪除}} else {System.out.println("您需要?jiǎng)h除的節(jié)點(diǎn):" + num + "在鏈表中不存在~~~");}}/*顯示鏈表,遍歷查看*/public void showLinkedList() {//判斷鏈表否為空,if (headNode.next == null) {System.out.println("鏈表為空,請(qǐng)?zhí)砑雍蟛榭磣~~");return;}//同樣,頭結(jié)點(diǎn)不能動(dòng),作為輔助遍歷,從頭節(jié)點(diǎn)的下一位開始顯示,頭節(jié)點(diǎn)不顯示Node temp = headNode.next;while (true) {//判斷是否到最后一個(gè)節(jié)點(diǎn)了if (temp == null) {break;}//輸出節(jié)點(diǎn)信息System.out.println(temp);//將temp后移temp = temp.next;}}}//創(chuàng)建一個(gè)類類模擬雙鏈表節(jié)點(diǎn) class Node {public int num;//當(dāng)前節(jié)點(diǎn)數(shù)public String name;//給當(dāng)前節(jié)點(diǎn)取個(gè)名字,模擬節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)public Node next;//當(dāng)前節(jié)點(diǎn)存儲(chǔ)的下一個(gè)節(jié)點(diǎn)信息public Node pre;//存儲(chǔ)當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)//提供構(gòu)造方法來初始化這個(gè)節(jié)點(diǎn)信息public Node(int num, String name) {this.num = num;this.name = name;}@Overridepublic String toString() {return "Node{" +"num=" + num +", name='" + name + '\'' +'}';} }

測試控制臺(tái)結(jié)果

---------添加4個(gè)節(jié)點(diǎn)(1,2,3,4)------------ ----------------測試遍歷雙向鏈表--------------- Node{num=1, name='節(jié)點(diǎn)一'} Node{num=2, name='節(jié)點(diǎn)二'} Node{num=3, name='節(jié)點(diǎn)三'} Node{num=4, name='節(jié)點(diǎn)四'} ---------------測試添加節(jié)點(diǎn)到雙鏈表的最后---------------------- Node{num=1, name='節(jié)點(diǎn)一'} Node{num=2, name='節(jié)點(diǎn)二'} Node{num=3, name='節(jié)點(diǎn)三'} Node{num=4, name='節(jié)點(diǎn)四'} Node{num=5, name='節(jié)點(diǎn)五'} ----------刪除節(jié)點(diǎn)為3的--------------- Node{num=1, name='節(jié)點(diǎn)一'} Node{num=2, name='節(jié)點(diǎn)二'} Node{num=4, name='節(jié)點(diǎn)四'} Node{num=5, name='節(jié)點(diǎn)五'} -----------修改節(jié)點(diǎn)5的數(shù)據(jù)為測試節(jié)點(diǎn)---------- Node{num=1, name='節(jié)點(diǎn)一'} Node{num=2, name='節(jié)點(diǎn)二'} Node{num=4, name='節(jié)點(diǎn)四'} Node{num=5, name='測試節(jié)點(diǎn)'}

總結(jié)

以上是生活随笔為你收集整理的浅谈:数据结构之双链表结构与代码模拟双链表的实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。