前言
双向链表在单链表的基础上做了一些改进，所以本篇博客对于那些相似的地方，不再赘述，但不同的地方一定会讲到，读者有迷惑的地方，或者有兴趣，可以去看看我上周写的单链表博客。
一、双向、不带头、非循环链表的结构
模拟五个节点，每个节点有三个域：
第一个是数据域，存放的是元素
第二个是前驱指针域，存放的是当前节点的前一个节点的地址
第三个是后继指针域，存放的是当前节点的下一个节点的地址
二、代码实现
1. 第一个 java 文件放的是两个类
一个类实现节点 Node，另一个类实现链表 Double_LinkedList
class Node{ public int val; public Node prev; public Node next; public Node(int newval){ this.val = newval; } } public class Double_LinkedList { public Node head; public Node last; //初始化链表 ✓ public void initialList() { Node node1 = new Node(12); Node node2 = new Node(23); Node node3 = new Node(34); Node node4 = new Node(45); Node node5 = new Node(56); this.head = node1; node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node2.prev = node1; node3.prev = node2; node4.prev = node3; node5.prev = node4; this.last = node5; } //打印链表中每个节点对应的 val ✓ public void print() { Node cur = this.head; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); } //得到单链表的长度 ✓ public int size() { int count = 0; Node cur = this.head; while (cur != null) { count++; cur = cur.next; } return count; } //头插法 ✓ public void addFirst(int data) { Node newnode = new Node(data); if (this.head == null) { this.head = newnode; this.last = newnode; return; } newnode.next = this.head; this.head.prev = newnode; this.head = newnode; } //尾插法 ✓ public void addLast(int data) { Node newnode = new Node(data); if (this.head == null) { this.head = newnode; this.last = newnode; return; } newnode.prev = this.last; this.last.next = newnode; this.last = newnode; } //findPos函数是为下面的 insertData 函数所添加，目的就是为了找到指针cur的位置 ✓ public Node findPos(int pos) { Node cur = this.head; for (int i = 0; i < pos - 1; i++) { cur = cur.next; } return cur; } //任意位置插入,第一个数据节点为0号下标 ✓ public void insertData(int pos, int data) { if (pos < 0 || pos > size()) { System.out.println("插入的位置不合法！"); } else if (pos == 0) { addFirst(data); } else if (pos == size()) { addLast(data); } else { Node cur = findPos(pos); Node newnode = new Node(data); newnode.next = cur.next; newnode.prev = cur; cur.next = newnode; //注意，这里必须最后改变 cur.next 的指向 //否则，原先的链表就会发生截断，也就是说找不到原先的那个 cur.next } } //查找是否包含关键字key是否在单链表当中 ✓ public boolean contains(int key) { Node cur = this.head; while (cur != null) { if (cur.val == key) { return true; } cur = cur.next; } return false; } //删除第一次出现关键字为key的节点 ✓ public void remove(int key) { //头删 if (this.head.val == key) { //考虑到链表中只有一个节点的情况 if (this.head.next == null) { this.head = null; this.last = null; return; } this.head.next.prev = null; this.head = this.head.next; return; } //尾删 if (this.last.val == key) { this.last.prev.next = null; this.last = this.last.prev; return; } //考虑其他情况 //用flag记录当前链表中是否有这个 key 值 Node cur = this.head; int flag = 0; while (cur != null) { if (cur.val == key) { flag = 1; break; } cur = cur.next; } if (flag == 0) { System.out.println("你所要删除的 key 在链表中找不到对应的节点值"); return; } //中间删 cur.prev.next = cur.next; cur.next.prev = cur.prev; } //删除所有值为key的节点 ✓ //只遍历了链表一次 public void removeAllKey(int key) { Node cur = this.head; int flag = 0; while (cur != null) { if (cur.val == key) { //头删 if (this.head.val == key) { //考虑到链表中只有一个节点的情况 if (this.head.next == null) { this.head = null; this.last = null; flag = 1; return; } flag = 1; this.head.next.prev = null; this.head = this.head.next; } else if (cur.next != null) { //中间删 cur.prev.next = cur.next; cur.next.prev = cur.prev; flag = 1; } else { //尾删 this.last.prev.next = null; this.last = this.last.prev; flag = 1; } } cur = cur.next; } if (flag == 0) { System.out.println("你所要删除的key在链表中找不到对应的节点值val"); } } //清空链表 public void clear() { if(head == null){ System.out.println("链表本身就为空，无法清空链表！"); }else{ Node cur = this.head; Node cur2 = cur.next; cur.prev = null; cur.next = null; cur = cur2; this.head = null; this.last = null; } } }
2. 第二个 java 文件放的是一个类 Test
目的是使用主函数来测试双向链表的一系列功能
public class Test { public static void main(String[] args) { Double_LinkedList test = new Double_LinkedList(); test.initialList(); test.print(); } }
三、框架分析
0. 对框架进行说明
（1）我所创建的框架是拆解了代码的方法（函数），把类中的每一个方法都拿出来仔细分析。
（2）我画图的地方可能有些不规范，比如地址的表示形式，比如箭头指向等等，我旨在表达逻辑，所以请读者自行理解，也请大佬多多指点。
1. 创建一个类 Node，表示节点
双向链表比单向链表多了一个前驱指针
class Node{ public int val; public Node prev; public Node next; public Node(int newval){ this.val = newval; } }
2. 模拟链表内部结构
这里的思想和单链表相似，这里不再说明。
3. 初始化一个链表
public class Double_LinkedList { public Node head; public Node last; //初始化链表 ✓ public void initialList() { Node node1 = new Node(12); Node node2 = new Node(23); Node node3 = new Node(34); Node node4 = new Node(45); Node node5 = new Node(56); this.head = node1; node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node2.prev = node1; node3.prev = node2; node4.prev = node3; node5.prev = node4; this.last = node5; } }
这里相较于单链表，多了一个 last 指针，它指向尾节点，在用代码实现的时候，要考虑进去，有些书上可能没有给出 last 这一指针，其实是一样的，只是给出 last 指针，会更好记录尾节点的前后情况。
4. 打印每个节点对应的 val
//打印链表中每个节点对应的 val ✓ public void print() { Node cur = this.head; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); }
5. 得到链表的长度
//得到单链表的长度 ✓ public int size() { int count = 0; Node cur = this.head; while (cur != null) { count++; cur = cur.next; } return count; }
6. 头插法
//头插法 ✓ public void addFirst(int data) { Node newnode = new Node(data); if (this.head == null) { this.head = newnode; this.last = newnode; return; } newnode.next = this.head; this.head.prev = newnode; this.head = newnode; }
头插法的关键在于改变头指针 head 的地址，既然是双向链表，那么我们不仅要关心后继 next，同时也要考虑前驱 prev. 而此时，当链表为空的时候，头指针 head 和 尾指针 last 也要进行相关操作。
7. 尾插法
//尾插法 ✓ public void addLast(int data) { Node newnode = new Node(data); if (this.head == null) { this.head = newnode; this.last = newnode; return; } newnode.prev = this.last; this.last.next = newnode; this.last = newnode; }
尾插法和头插法思想相同，不再赘述。但我们可以思考一个问题：当我们没有 last 指针的时候，我们该怎么找到最后一个节点呢？我们能做的只能是遍历链表了，这增加了时间复杂度。然而，有 last 指针，情况就大不相同了！
8. 在任一位置插入节点
//findPos函数是为下面的 insertData 函数所添加，目的就是为了找到指针cur的位置 ✓ public Node findPos(int pos) { Node cur = this.head; for (int i = 0; i < pos - 1; i++) { cur = cur.next; } return cur; } //任意位置插入,第一个数据节点为0号下标 ✓ public void insertData(int pos, int data) { if (pos < 0 || pos > size()) { System.out.println("插入的位置不合法！"); } else if (pos == 0) { addFirst(data); } else if (pos == size()) { addLast(data); } else { Node cur = findPos(pos); Node newnode = new Node(data); newnode.next = cur.next; newnode.prev = cur; cur.next = newnode; //注意，这里必须最后改变 cur.next 的指向 //否则，原先的链表就会发生“截断”，也就是说找不到原先的那个 cur.next } }
这里和单链表的插入思想相同，这里不再赘述，唯一注意的地方就是下面三行代码的顺序，我们必须记住的是：当使用代码实现我们想要的结果时，地址不能被覆盖。
newnode.next = cur.next; newnode.prev = cur; cur.next = newnode;
9. 查找关键字key是否在单链表当中
//查找是否包含关键字key是否在单链表当中 ✓ public boolean contains(int key) { Node cur = this.head; while (cur != null) { if (cur.val == key) { return true; } cur = cur.next; } return false; }
10. 删除第一次出现关键字为 key 的节点
//删除第一次出现关键字为key的节点 ✓ public void remove(int key) { //头删 if (this.head.val == key) { //考虑到链表中只有一个节点的情况 if (this.head.next == null) { this.head = null; this.last = null; return; } this.head.next.prev = null; this.head = this.head.next; return; } //尾删 if (this.last.val == key) { this.last.prev.next = null; this.last = this.last.prev; return; } //考虑其他情况 //用flag记录当前链表中是否有这个 key 值 Node cur = this.head; int flag = 0; while (cur != null) { if (cur.val == key) { flag = 1; break; } cur = cur.next; } if (flag == 0) { System.out.println("你所要删除的 key 在链表中找不到对应的节点值"); return; } //中间删 cur.prev.next = cur.next; cur.next.prev = cur.prev; }
这里代码实现可能写的有点啰嗦，本来想优化一下的，但是我发现这样的可读性更高，所以我决定就这样保留下来了，希望等我以后回过头看，会更清晰地理解。
//情况（1）头删
//情况（2）整个链表只有一个节点
//情况（3）中间删
//情况（4）尾删
11. 删除所有出现 key 的节点
//删除所有值为key的节点 ✓ public void removeAllKey(int key) { Node cur = this.head; int flag = 0; while (cur != null) { if (cur.val == key) { //头删 if (this.head.val == key) { //考虑到链表中只有一个节点的情况 if (this.head.next == null) { this.head = null; this.last = null; flag = 1; return; } flag = 1; this.head.next.prev = null; this.head = this.head.next; } else if (cur.next != null) { //中间删 cur.prev.next = cur.next; cur.next.prev = cur.prev; flag = 1; } else { //尾删 this.last.prev.next = null; this.last = this.last.prev; flag = 1; } } cur = cur.next; } if (flag == 0) { System.out.println("你所要删除的 key 在链表中找不到对应的节点值"); } }
这里的代码与上一层的代码基本一致，只是去掉了 return。而我们真正要思考的是：双向链表与单链表实现此功能的区别在哪里，虽然两者思路一样，但是双向链表遍历链表的时候要容易想的多，因为这里给出了前驱 prev 指针，这使得串联节点的时候，就不怎么需要绕弯子了。
12. 清空链表
//清空链表 public void clear() { if(head == null){ System.out.println("链表本身就为空，无法清空链表！"); }else{ Node cur = this.head; Node cur2 = cur.next; cur.prev = null; cur.next = null; cur = cur2; this.head = null; this.last = null; } }
思路一：
可以遍历整个链表，把每个节点的指针域置成 null，这里要注意：要拿一个 cur2 指针来始终记录某个节点的后一个位置，这很关键。
思路二：
当然也可以直接写成如下代码，至于其余的，Java 的机制可以自动回收内存。
this.head = null; this.last = null;
四、测试程序
1. 初始化链表
public class Test { public static void main(String[] args) { Double_LinkedList test = new Double_LinkedList(); test.initialList(); test.print(); } }
输出结果：
2. 插入功能
public class Test { public static void main(String[] args) { Double_LinkedList test = new Double_LinkedList(); test.addFirst(1); test.addFirst(3); test.addFirst(5); test.addFirst(7); test.print(); test.addLast(2); test.addLast(4); test.addLast(6); test.addLast(8); test.print(); test.insertData(8,77); test.print(); test.insertData(0,99); test.print(); test.insertData(2,88); test.print(); } }
输出结果：
3. 删除单节点
public class Test { public static void main(String[] args) { Double_LinkedList test = new Double_LinkedList(); test.addLast(1); test.addLast(3); test.addLast(5); test.addLast(7); test.addLast(9); test.print(); test.remove(9); test.print(); test.remove(1); test.print(); test.remove(5); test.print(); test.remove(10); } }
输出结果：
4. 删除指定的重复节点
public class Test { public static void main(String[] args) { Double_LinkedList test = new Double_LinkedList(); test.addLast(2); test.addLast(3); test.addLast(5); test.addLast(2); test.addLast(2); test.addLast(9); test.addLast(2); test.print(); test.removeAllKey(2); test.print(); } }
输出结果：
5. 清空链表
public class Test { public static void main(String[] args) { Double_LinkedList test = new Double_LinkedList(); test.addLast(2); test.addLast(3); test.addLast(5); test.addLast(2); test.addLast(2); test.addLast(9); test.addLast(2); test.clear(); test.print(); } }
输出结果：
总结
- 经过大约 10 天左右的时间，我才把链表完整学完，对于链表的原理，光用眼看是不够的，必须得用代码实现，自己画画图，思路就很清晰了。记得上周实现单链表的时候，跟着老师的节奏，花了两天的时间才做出来，而今天早上花了半天时间，就自己把双向链表做出来了，而且只有很少一部分看了老师的代码。
- 这期间刷了牛客网和力扣的一些题目，才发现数据结构和算法是离不开的，有些题目的解法确实很难想到，希望自己能够继续努力，持续不断地积累。
Over. 谢谢观看哟~
