05、数据结构与算法 - 实战：双链表的增、删、改、查
前言
一、双链表的应用实例
使用带head头节点的双向链表实现 - 水浒传英雄排行榜
二、单链表的缺点分析
1、 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找；
2、 单向链表**不能自我删除**，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点(认真体会).；
三、双链表增删改查思路
- 分析 双向链表的遍历，添加，修改，删除的操作思路
1、 遍历方和单链表一样，只是可以向前，也可以向后查找；
2、 第一种添加(默认添加到双向链表的最后)；
(1) 先找到双向链表的最后这个节点
(2) temporary.next = newNode;
(3) newNode.pre = temporary; 3、 第二种添加(按编号的顺序添加)；
(1)用辅助节点的No与新插入的No比较，找到要插入的前一个节点
(2)先挂载后面：newNode.next = temporary.next; temporary.next.pre = newNode;
(3)在挂载前面：temporary.next = newNode; newNode.pre = temporary; 4、 修改思路和原来的单向链表一样.；
5、 删除；
(1) 因为是双向链表，因此，我们可以实现自我删除某个节点
(2) 直接找到要删除的这个节点，比如temp
(3) temp.pre.next = temp.next
(4) temp.next.pre = temp.pre;
- 上面的思路说明的逻辑图如下：
四、代码实现
4.1 项目结构
HeroNode.java :节点类
DoubleLinkedList.java : 双链表类
DoubleLinkedListMain.java : 测试类
4.2 HeroNode.java 节点类
package com.feng.ch04_doubleLinkedlist;
// 定义HeroNode ，每个 HeroNode 就是一个节点
public class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode pre; // 指向上一个节点，默认为null
public HeroNode next; // 指向下一个节点，默认为null
public HeroNode(int no, String name, String nickname){
this.no = no;
this.name = name;
this.nickname = nickname;
}
/* 为显示方法，重写 toString 方法*/
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
4.3 DoubleLinkedList.java 双链表类
package com.feng.ch04_doubleLinkedlist;
/*
* 创建一个双向链表的类
* */
public class DoubleLinkedList {
private HeroNode head = new HeroNode(0, "", "");
public HeroNode getHead() {
return head;
}
/*
* 添加节点：按顺序添加
* */
public void addDoubleLinkedByOrder(HeroNode newNode) {
HeroNode temporary = head;
boolean flag = false;
while (true) {
if (temporary.next == null) {
// 当前数据
break;
}
if (temporary.next.no > newNode.no) {
break;
} else if (temporary.next.no == newNode.no) {
flag = true;
break;
}
temporary = temporary.next;
}
if (flag) {
System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", newNode.no);
} else {
if (temporary.next == null){
// 挂载前面
temporary.next = newNode;
newNode.pre = temporary;
}else {
//挂载后面
newNode.next = temporary.next;
temporary.next.pre = newNode;
// 挂载前面
temporary.next = newNode;
newNode.pre = temporary;
}
}
}
/*
* 添加节点：直接添加到双向链表的最后
* */
public void addDoubleLinked(HeroNode newNode) {
HeroNode temporary = head;
while (true) {
if (temporary.next == null) {
// 最后一个 出去
break;
}
temporary = temporary.next; // 后移
}
/*
* 当退出while循环时，temp就指向了链表的最后
* 形成一个双向链表
* */
temporary.next = newNode;
newNode.pre = temporary;
}
/*
* 修改：可以看到双向链表的节点内容修改和单向链表一样
* */
public void updateNode(HeroNode newNode) {
if (head.next == null) {
return;
}
HeroNode temporary = head.next;
boolean flag = false;
while (true) {
if (temporary == null) {
// 没有匹配着
break;
}
if (temporary.no == newNode.no) {
flag = true;
break;
}
temporary = temporary.next;
}
if (flag) {
// 根据flag 判断是否找到要修改的节点
temporary.name = newNode.name;
temporary.nickname = newNode.nickname;
} else {
System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newNode.no);
}
}
/*
* 删除节点
* 1 对于双向链表，我们可以直接找到要删除的这个节点
* 2 找到后，自我删除即可
* */
public void deleteNode(int no) {
if (head.next == null) {
System.out.println("链表为空，无法删除");
return;
}
HeroNode temporary = head.next;
boolean flag = false;
while (true) {
if (temporary == null) {
break;
}
if (temporary.no == no) {
flag = true;
break;
}
temporary = temporary.next;
}
if (flag) {
temporary.pre.next = temporary.next;
if (temporary != null) {
temporary.next.pre = temporary.pre;
}
} else {
System.out.printf("要删除的 %d 节点不存在\n", no);
}
}
//显示链表【遍历】
public void list() {
if (head.next == null) {
System.out.println("链表为空");
return;
}
// 因为头结点不能动， 因此需要一个辅助节点 temp 来遍历
HeroNode temporary = head.next;
while (temporary != null) {
// 输出节点信息
System.out.println(temporary);
temporary = temporary.next;
}
}
}
4.4 DoubleLinkedListMain.java 测试类
package com.feng.ch04_doubleLinkedlist;
public class DoubleLinkedListMain {
public static void main(String[] args) {
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
// doubleLinkedList.addDoubleLinked(hero1);
// doubleLinkedList.addDoubleLinked(hero2);
// doubleLinkedList.addDoubleLinked(hero3);
// doubleLinkedList.addDoubleLinked(hero4);
doubleLinkedList.addDoubleLinkedByOrder(hero2);
doubleLinkedList.addDoubleLinkedByOrder(hero1);
doubleLinkedList.addDoubleLinkedByOrder(hero4);
doubleLinkedList.addDoubleLinkedByOrder(hero3);
System.out.println("初始化的 双链表数据：");
doubleLinkedList.list();
// 测试修改
System.out.println();
System.out.println("修改后的数据~");
HeroNode hero5 = new HeroNode(4, "公孙胜", "入云龙");
doubleLinkedList.updateNode(hero5);
doubleLinkedList.list();
// 测试删除
System.out.println();
System.out.println("删除后的数据~");
doubleLinkedList.deleteNode(3);
doubleLinkedList.list();
}
}
4.5 测试结果
