双向链表应用实例
双向链表的操作分析和实现
使用带head头的双向链表实现 -水浒英雄排行榜
---------------------------------------------------------------
-》管理单向链表的缺点分析:
(1)单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找。
(2)单向链表不能自我删除,需要靠辅助辅助节点,而双向链表,则可以自我删除,所以前面我们单链表删除节点时,总是找到temp,temp是待删除节点的前一个节点。
分析双向链表如何完成遍历,添加,修改和删除的思路:
具体代码:
1 package com.atguigu.linkedlist; 2 3 public class DoubleLinkedListDemo { 4 5 public static void main(String[] args) { 6 // 测试 7 System.out.println("双向链表的测试"); 8 // 先创建节点 9 HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨"); 10 HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟"); 11 HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星"); 12 HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头"); 13 // 创建一个双向链表 14 DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); 15 doubleLinkedList.add(hero1); 16 doubleLinkedList.add(hero2); 17 doubleLinkedList.add(hero3); 18 doubleLinkedList.add(hero4); 19 20 doubleLinkedList.list(); 21 22 // 修改 23 HeroNode2 newHeroNode = new HeroNode2(4, "公孙胜", "入云龙"); 24 doubleLinkedList.update(newHeroNode); 25 System.out.println("修改后的链表情况"); 26 doubleLinkedList.list(); 27 28 // 删除 29 doubleLinkedList.del(3); 30 System.out.println("删除后的链表情况~~"); 31 doubleLinkedList.list(); 32 33 34 35 } 36 37 } 38 39 // 创建一个双向链表的类 40 class DoubleLinkedList { 41 42 // 先初始化一个头节点, 头节点不要动, 不存放具体的数据 43 private HeroNode2 head = new HeroNode2(0, "", ""); 44 45 // 返回头节点 46 public HeroNode2 getHead() { 47 return head; 48 } 49 50 // 遍历双向链表的方法 51 // 显示链表[遍历] 52 public void list() { 53 // 判断链表是否为空 54 if (head.next == null) { 55 System.out.println("链表为空"); 56 return; 57 } 58 // 因为头节点,不能动,因此我们需要一个辅助变量来遍历 59 HeroNode2 temp = head.next; 60 while (true) { 61 // 判断是否到链表最后 62 if (temp == null) { 63 break; 64 } 65 // 输出节点的信息 66 System.out.println(temp); 67 // 将temp后移, 一定小心 68 temp = temp.next; 69 } 70 } 71 72 // 添加一个节点到双向链表的最后. 73 public void add(HeroNode2 heroNode) { 74 75 // 因为head节点不能动,因此我们需要一个辅助遍历 temp 76 HeroNode2 temp = head; 77 // 遍历链表,找到最后 78 while (true) { 79 // 找到链表的最后 80 if (temp.next == null) {// 81 break; 82 } 83 // 如果没有找到最后, 将将temp后移 84 temp = temp.next; 85 } 86 // 当退出while循环时,temp就指向了链表的最后 87 // 形成一个双向链表 88 temp.next = heroNode; 89 heroNode.pre = temp; 90 } 91 92 // 修改一个节点的内容, 可以看到双向链表的节点内容修改和单向链表一样 93 // 只是 节点类型改成 HeroNode2 94 public void update(HeroNode2 newHeroNode) { 95 // 判断是否空 96 if (head.next == null) { 97 System.out.println("链表为空~"); 98 return; 99 } 100 // 找到需要修改的节点, 根据no编号 101 // 定义一个辅助变量 102 HeroNode2 temp = head.next; 103 boolean flag = false; // 表示是否找到该节点 104 while (true) { 105 if (temp == null) { 106 break; // 已经遍历完链表 107 } 108 if (temp.no == newHeroNode.no) { 109 // 找到 110 flag = true; 111 break; 112 } 113 temp = temp.next; 114 } 115 // 根据flag 判断是否找到要修改的节点 116 if (flag) { 117 temp.name = newHeroNode.name; 118 temp.nickname = newHeroNode.nickname; 119 } else { // 没有找到 120 System.out.printf("没有找到 编号 %d 的节点,不能修改\n", newHeroNode.no); 121 } 122 } 123 124 // 从双向链表中删除一个节点, 125 // 说明 126 // 1 对于双向链表,我们可以直接找到要删除的这个节点 127 // 2 找到后,自我删除即可 128 public void del(int no) { 129 130 // 判断当前链表是否为空 131 if (head.next == null) {// 空链表 132 System.out.println("链表为空,无法删除"); 133 return; 134 } 135 136 HeroNode2 temp = head.next; // 辅助变量(指针) 137 boolean flag = false; // 标志是否找到待删除节点的 138 while (true) { 139 if (temp == null) { // 已经到链表的最后 140 break; 141 } 142 if (temp.no == no) { 143 // 找到的待删除节点的前一个节点temp 144 flag = true; 145 break; 146 } 147 temp = temp.next; // temp后移,遍历 148 } 149 // 判断flag 150 if (flag) { // 找到 151 // 可以删除 152 // temp.next = temp.next.next;[单向链表] 153 temp.pre.next = temp.next; 154 // 这里我们的代码有问题? 155 // 如果是最后一个节点,就不需要执行下面这句话,否则出现空指针 156 if (temp.next != null) { 157 temp.next.pre = temp.pre; 158 } 159 } else { 160 System.out.printf("要删除的 %d 节点不存在\n", no); 161 } 162 } 163 164 } 165 166 // 定义HeroNode2 , 每个HeroNode 对象就是一个节点 167 class HeroNode2 { 168 public int no; 169 public String name; 170 public String nickname; 171 public HeroNode2 next; // 指向下一个节点, 默认为null 172 public HeroNode2 pre; // 指向前一个节点, 默认为null 173 // 构造器 174 175 public HeroNode2(int no, String name, String nickname) { 176 this.no = no; 177 this.name = name; 178 this.nickname = nickname; 179 } 180 181 // 为了显示方法,我们重新toString 182 @Override 183 public String toString() { 184 return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; 185 } 186 187 }
原文:https://www.cnblogs.com/cire/p/13363633.html