【数据结构与算法】什么是双向链表？并用代码手动实现一个双向链表

一、什么是双向链表

我们来看一下这个例子：

在一个教室里，所有的课桌排成一列，如图

相信在你们的读书生涯中，老师肯定有要求你们记住自己的前后桌是谁。所以该例子中，老师就要求学生们记住自己的前后桌，其中坐在第一排的学生需要记住自己是第一排的学生以及自己的后桌是谁；最后一排的学生要记住自己的前桌是谁以及自己是最后一排的学生。如图：

这一列座位就相当于一个 双向链表。

假如有一天，老师还没记住每个学生的名字，于是就问：这一列第三个人叫什么名字？这时就要从第一个学生开始数，例如从图中坐在第一个的 小5 开始数：第一个人是 小5，他的后桌是 小7；因此第二个人就是 小7，他的后桌是 小1；因此第三个人就是 小1 了。此时老师问 小1：你的前桌叫什么名字？你的后桌叫什么名字？

因为刚开始老师就让每个学生记住了自己的前桌以及后桌，所以此时 小1 能很快地告诉老师他的前桌是 小7，他的后桌是 小6。

但是，我们设想一下，如果是上一篇文章的 链表结构 的例子中，如果老师在得知了第三个人是 小1 以后，询问 小1 的前桌叫什么名字，小1 能回答上来吗？并不能，因为老师只让每个学生记住了自己的后桌，所以此时想要得知 小1 的前桌叫什么名字，只能这样：第三个学生叫 小1，那么他的前桌就坐在第二个位置，所以从第一个学生开始数，第一个学生是 小5，他的后桌是 小7；因此第二个学生就是 小7。当然本文举得例子中学生数量有点少，但一旦数量多起来了，每次问一个学生他的前桌叫什么名字的时候，都要从头开始数。

从中可以看出，让每个学生记住自己的前桌后桌是非常有必要的，因为在某些情况下，可以快速地解决问题。

上面讲了那么多，接下来我们就来看一下 双向链表 是什么样的，如图

可以看到，对比 链表结构，双向链表 多了一个指针 tail，它是指向最后一个元素的，就相当于例子中的学生记住了自己是最后一排。

双向链表与单链表基本相似，但是最大的区别在于双向链表在节点中除了指向下一节点的next指针外，还有指向前一节点的prev指针，这使得双向链表在可以在任意节点从头尾两个方向进行遍历，是“双向”的。

和单链表相比，双向链表在删除和查询等方面明显在操作上更具有灵活性，但是会消耗更多的内存，需要根据使用条件进行取舍。

java中的LinkedHashMap的本质即是一个双向链表。

二、双向链表的简单实现

修改原来的Node类，在里面添加一个新成员变量Node prev

/*** @Author：huang* @Date：2023-03-23 20:10* @Description：节点类*/
public class Node {//节点序号int num;//数据Object data;//下一个节点Node next;//上一节点Node prev;public Node(int num, Object data) {this.num = num;this.data = data;}@Overridepublic String toString() {return "Node{" +"num=" + num +", data=" + data +'}';}
}

1. 添加
   添加与单向链表代码逻辑一样，但是新节点在添加时需要修改prev指针指向原来的尾节点。
   举个例子，对于无排序插入，原本有节点A，现在要插入一个B：

• 找到A，然后让A.next指向B
• 让B.prev指向A

而对于排序插入，就是原有节点A，C，要在中间插入B：

• 找到A，让B.prev指向A
• 让B.next指向A.next，也就是让B的next指向C
• 让A.next.prev指向B，也就是让C的prev指向B
• 让A.next指向B

/*** 添加节点到链表* @param node 要插入的节点*/
public void add(Node node) {Node temp = head;//遍历链表while (true) {if (temp.next == null) {break;}//不是尾节点就继续遍历下一个节点temp = temp.next;}//将尾节点指向即将插入的新节点temp.next = node;node.prev = temp;
}/*** 按顺序添加节点到链表* @param node 要插入的节点*/
public void addByOrder(Node node) {Node temp = head;//遍历链表while (true) {//如果链表到底了就直接插入if (temp.next == null) {temp.next = node;node.prev = temp;return;}else if (temp.next.num > node.num){//如果后一节点比当新节点大，就插入当前节点node.prev = temp;node.next = temp.next;temp.next.prev = node;temp.next = node;return;}else if (temp.next.num == node.num){//如果后一节点等于新节点，抛异常throw new RuntimeException("插入节点与已有节点序号重复！");}//如果后一节点比当前节点小，就继续遍历temp = temp.next;}
}

2. 删除
   由于相对单链表，双向链表的节点可以自己找到上一节点，所以删除的时候可以直接找到要删除的节点进行操作。

举个例子，假设有节点A，B，C，现在要删除B：

• 找到B，让B.prev.next=B.next，也就是让A的next指向C
• 让B.next.prev=B.prev，也就是让C的prev指向A

如果要删除的节点已经是尾节点了，那就跟单链表一样了。

/*** 删除节点* @param num 要删除的节点编号*/
public void delete(int num) {Node temp = head;//判断链表是否为空if (temp.next == null) {throw new RuntimeException("链表为空！");}//遍历链表while (true) {//如果链表到底了if (temp.next == null) {throw new RuntimeException("编号为" + num + "的节点不存在！");}//如果找到了待删除节点的前一个节点if (temp.num == num) {//判断待删除节点是否为尾节点if (temp.next == null){temp.prev.next = null;}else {temp.prev.next = temp.next;temp.next.prev = temp.prev;}return;}//继续遍历下一节点temp = temp.next;}
}

3. 修改，查询（与单链表一致）
   由于修改和查询与单链表基本一致，这里就不在赘述了，直接放代码：

/*** 展示链表*/
public void show() {//判断链表是否为空if (head.next == null) {throw new RuntimeException("链表为空！");}Node temp = head.next;//遍历链表while (true) {if (temp == null) {break;}System.out.println(temp.toString());temp = temp.next;}
}/*** 根据序号获取节点* @param num 要获取的节点序号* @return*/
public Node get(int num){//判断链表是否为空if (head.next == null) {throw new RuntimeException("链表为空！");}Node temp = head.next;//遍历链表while (true) {if (temp == null) {throw new RuntimeException("编号为" + num + "的节点不存在！");}if (temp.num == num) {return temp;}temp = temp.next;}
}/*** 修改节点* @param node 要更新的节点*/
public void update(Node node) {Node temp = head;//判断链表是否为空if (temp.next == null) {throw new RuntimeException("链表为空！");}//获取要更新的节点序号int nodeNum = node.num;//遍历链表while (true) {//如果已经遍历完链表if (temp == null) {throw new RuntimeException("编号为" + temp.num + "的节点不存在！");}//如果找到了该节点if (temp.num == nodeNum) {temp.data = node.data;return;}//继续遍历下一节点temp = temp.next;}
}