双向链表实战 野性酷女 2021-07-24 12:47 215阅读 0赞 # 一 点睛 # ## 1 需求 ## 使用带 head 头的双向链表实现水浒英雄排行榜。 ## 2 单向链表和双向链表对比 ## a 单向链表:查找的方向只能是一个方向,而双向链表可以向前或者向后查找。 b 单向链表不能自我删除,需要靠辅助节点 ,而双向链表,则可以自我删除。单链表删除节点时,总要找到temp节点,temp节点是待删除节点的前一个节点。 ## 3 图解 ## ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][] a 双向链表遍历方法和单链表一样,只是可以向前,也可以向后查找。 b 添加,默认添加到双向链表的最后。 第一步:先找到双向链表的最后这个节点。 第二步:temp.next = newHeroNode 第三步:newHeroNode.pre = temp; c 双向链表修改和单向链表一样。 d 双向链表删除可以实现自我删除某个节点。 第一步:直接找到要删除的这个节点,比如 temp 第二步:temp.pre.next = temp.next 第三步:temp.next.pre = temp.pre; # 二 代码 # package com.atguigu.linkedlist; /** * @className: DoubleLinkedListDemo * @description: 双向链表 * @date: 2021/3/3 * @author: cakin */ public class DoubleLinkedListDemo { /** * 功能描述:双向链表测试 * * @param args 命令行 * @author cakin * @date 2021/3/3 */ public static void main(String[] args) { // 测试 System.out.println("双向链表的测试"); // 先创建节点 HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨"); HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟"); HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星"); HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头"); // 创建一个双向链表 DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); doubleLinkedList.add(hero1); doubleLinkedList.add(hero2); doubleLinkedList.add(hero3); doubleLinkedList.add(hero4); doubleLinkedList.list(); // 修改 HeroNode2 newHeroNode = new HeroNode2(4, "公孙胜", "入云龙"); doubleLinkedList.update(newHeroNode); System.out.println("修改后的链表情况"); doubleLinkedList.list(); // 删除 doubleLinkedList.del(3); System.out.println("删除后的链表情况~~"); doubleLinkedList.list(); } } /** * @className: DoubleLinkedListDemo * @description: 双向链表的类类 * @date: 2021/3/3 * @author: cakin */ class DoubleLinkedList { // 先初始化一个头节点 private HeroNode2 head = new HeroNode2(0, "", ""); /** * 功能描述:返回头节点 * * @author cakin * @date 2021/3/3 */ public HeroNode2 getHead() { return head; } /** * 功能描述:遍历双向链表 * * @author cakin * @date 2021/3/3 */ public void list() { // 判断链表是否为空 if (head.next == null) { System.out.println("链表为空"); return; } // 辅助变量指向第个节点 HeroNode2 temp = head.next; while (true) { // 判断是否到链表最后 if (temp == null) { break; } // 输出节点的信息 System.out.println(temp); // 将temp后移 temp = temp.next; } } /** * 功能描述:添加一个节点到双向链表的最后 * * @author cakin * @date 2021/3/3 * @param heroNode 要添加的英雄节点 */ public void add(HeroNode2 heroNode) { // 辅助节点指向头节点 HeroNode2 temp = head; // 遍历链表,找到最后 while (true) { // 找到链表的最后 if (temp.next == null) {// break; } // 如果没有找到最后, 将temp后移 temp = temp.next; } // 当退出while循环时,temp就指向了链表的最后 // 形成一个双向链表 temp.next = heroNode; heroNode.pre = temp; } /** * 功能描述:修改一个节点的内容 * * @author cakin * @date 2021/3/3 * @param newHeroNode 待修改的英雄节点 * @description:双向链表的节点内容修改和单向链表一样 */ public void update(HeroNode2 newHeroNode) { // 判断是否空 if (head.next == null) { System.out.println("链表为空"); return; } // 找到需要修改的节点, 根据no编号 // 定义一个辅助变量 HeroNode2 temp = head.next; boolean flag = false; // 表示是否找到该节点 while (true) { if (temp == null) { break; // 已经遍历完链表 } if (temp.no == newHeroNode.no) { // 找到 flag = true; break; } temp = temp.next; } // 根据flag判断是否找到要修改的节点 if (flag) { temp.name = newHeroNode.name; temp.nickname = newHeroNode.nickname; } else { // 没有找到 System.out.printf("没有找到 编号 %d 的节点,不能修改\n", newHeroNode.no); } } /** * 功能描述:从双向链表中删除一个节点 * * @author cakin * @date 2021/3/3 * @param no 待删除节点的编号 * @description:说明 * 1 对于双向链表,我们可以直接找到要删除的这个节点 * 2 找到后,自我删除即可 */ public void del(int no) { // 判断当前链表是否为空 if (head.next == null) { // 空链表 System.out.println("链表为空,无法删除"); return; } HeroNode2 temp = head.next; // 辅助变量指向第一个节点 boolean flag = false; // 标志是否找到待删除节点的 while (true) { if (temp == null) { // 已经到链表的最后 break; } if (temp.no == no) { flag = true; break; } temp = temp.next; // temp后移,遍历 } // 判断flag if (flag) { // 找到 temp.pre.next = temp.next; // 如果是最后一个节点,就不需要执行下面这句话,否则出现空指针 if (temp.next != null) { temp.next.pre = temp.pre; } } else { System.out.printf("要删除的 %d 节点不存在\n", no); } } } /** * @className: HeroNode2 * @description: 英雄节点 * @date: 2021/3/3 * @author: cakin */ class HeroNode2 { public int no; public String name; public String nickname; public HeroNode2 next; // 指向下一个节点, 默认为null public HeroNode2 pre; // 指向前一个节点, 默认为null // 构造器 public HeroNode2(int no, String name, String nickname) { this.no = no; this.name = name; this.nickname = nickname; } @Override public String toString() { return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; } } # 三 测试 # 双向链表的测试 HeroNode [no=1, name=宋江, nickname=及时雨] HeroNode [no=2, name=卢俊义, nickname=玉麒麟] HeroNode [no=3, name=吴用, nickname=智多星] HeroNode [no=4, name=林冲, nickname=豹子头] 修改后的链表情况 HeroNode [no=1, name=宋江, nickname=及时雨] HeroNode [no=2, name=卢俊义, nickname=玉麒麟] HeroNode [no=3, name=吴用, nickname=智多星] HeroNode [no=4, name=公孙胜, nickname=入云龙] 删除后的链表情况~~ HeroNode [no=1, name=宋江, nickname=及时雨] HeroNode [no=2, name=卢俊义, nickname=玉麒麟] HeroNode [no=4, name=公孙胜, nickname=入云龙] [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/be523164dbf04c89b4abc18f776b3d58.png
相关 双向链表 一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空 灰太狼/ 2022年12月21日 04:54/ 0 赞/ 144 阅读
相关 双向链表 APUE 308页 线程学习时候有一个链表 struct job{ struct job next; struct job prev; 古城微笑少年丶/ 2022年08月05日 05:20/ 0 赞/ 141 阅读
相关 双向链表 前面叙述了关于单链表、双端链表、有序链表的结点插入以及遍历查找等示例。这几种链表都只能从前往后进行遍历,反向遍历是非常麻烦的一件事。 考虑一下下面这个情况:如果文本编辑 亦凉/ 2022年07月18日 05:29/ 0 赞/ 169 阅读
相关 双向链表 一、解析 在单链表中,有了next指针,要查找下一节点的时间复杂度为O(1),如果要查找的是上一节点的话,最坏的时间复杂度是O(n)了,以为每次都要从头开始查找。为了克服这个 「爱情、让人受尽委屈。」/ 2022年07月03日 13:57/ 0 赞/ 213 阅读
相关 双向链表 /双向链表/ include<stdio.h> typedef struct dbnode { int num; 骑猪看日落/ 2022年06月16日 13:08/ 0 赞/ 159 阅读
相关 双向链表和双向循环链表 双向链表和双向循环链表 和单向链表相比,多了一个前驱结点。如果他为空,那么next和prior都指向自己。而对于双循环链表,只需要最后一个元素的next指向head->n ╰+哭是因爲堅強的太久メ/ 2022年05月16日 01:29/ 0 赞/ 235 阅读
相关 双向链表 Problem Description 学会了单向链表,我们又多了一种解决问题的能力,单链表利用一个指针就能在内存中找到下一个位置,这是一个不会轻易断裂的链。但单链表有一个弱 忘是亡心i/ 2022年05月10日 04:34/ 0 赞/ 224 阅读
相关 双向链表 题目描述 构建一个双向链表并进行删除和插入操作,按要求输出。 输入 输入: 第一行输入元素个数M 第二行输入M个元素 第三行输入删除位置 第四行输入插入位 野性酷女/ 2022年04月04日 05:48/ 0 赞/ 203 阅读
相关 双向链表 【一】双向链表 > 单向链表,查找的只能是一个方向,而双向链表可以向前或向后查找。 > 单向链表不能自我删除,需要靠辅助节点;而双向链表可以自我删除 > 双向链表中的 小咪咪/ 2021年08月12日 00:11/ 0 赞/ 375 阅读
相关 双向链表实战 一 点睛 1 需求 使用带 head 头的双向链表实现水浒英雄排行榜。 2 单向链表和双向链表对比 a 单向链表:查找的方向只能是一个方向,而双向链表可以向 野性酷女/ 2021年07月24日 12:47/ 0 赞/ 216 阅读
还没有评论,来说两句吧...