【数据结构与算法】5.详解双向链表的基本操作（Java语言实现）

0. 前言

上一篇【数据结构与算法】4.自主实现单链表的增删查改 我们自主实现了单链表的操作，在Java的集合类中LinkedList底层实现是无头双向循环链表。所以今天我们模拟LinkedList的实现。

1. 双链表的定义

学习双链表之前，做个回顾。

单链表的特点：

1. 我们可以轻松的到达下一个节点，但是回到前一节点是很难的。
2. 只能从头遍历到尾或者从尾遍历到头（一般是从头到尾）

双链表的特点：

1. 每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个. 实现起来要困难一些
2. 相对于单向链表, 必然占用内存空间更大一些.
3. 既可以从头遍历到尾, 又可以从尾遍历到头

双链表的定义：

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

指针域（prev）：用于指向当前节点的直接前驱节点；

数据域（data）：用于存储数据元素；

指针域（next）：用于指向当前节点的直接后继节点。

2. LinkedList 模拟实现

2.1 接口

2.2 定义双向链表类

2.3 定义两个指针，分别指向头节点和尾节点

2.4 头插法

判断链表是否为空，如果为空，将新节点的node设置为头节点，将新节点的node设置为尾节点

如果链表不为空，将新节点的node的next域设置为头节点，将当前头节点的prev设置为新节点的node，更新头节点为新节点的node

动画演示：

代码：

2.5 尾插法

判断链表是否为空，如果为空，将新节点的node设置为头节点，将新节点的node设置为尾节点

如果链表不为空，将最后一个节点last的next域指向新节点，新节点的prev域指向最后一个节点，更新尾节点为新节点

动画演示：

代码：

2.6 指定位置插入元素

判断索引idnex是否合法，如果不合法则抛出异常。

判断链表是否为空，如果为空则将新节点设置为头节点和尾节点

如果索引index == 0，则使用头插法，如果索引index = 链表长度，则使用尾插法

找到索引节点（当前节点）

将新节点的next域指向当前节点，新节点的prev域指向当前节点的前一个节点，当前节点的prev域指向新节点，更新新节点的上一个节点的next域指向当前节点。

动画演示：

2.7 查找指定元素

1. 从头节点开始遍历链表，如果当前节点的值与要查找的key相等，则返回ture，如果不相等则移动下一个节点继续查找。如果遍历完链表都没有找到key则返回false.

代码：

2.8 删除指定元素

1. 从头节点开始遍历链表，找到要删除的节点
2. 情况一：删除的节点为头节点，更新头节点为下一个节点，更新下一个节点的prev域置为空。

1. 情况二：链表中只有一个元素，且正好要删除这个元素。
2. 情况三：删除的节点为尾节点，更新尾节点为当前节点的上一个节点，上一个节点的next域置为空

1. 情况四：删除中间节点，当前节点的上一个节点的next域指向当前节点的下一个节点，更新下一个节点的prev域指向当前节点的上一个节点

1. 删除了节点就结束方法的执行

代码：

2.9 删除链表中所有指定元素

从头节点遍历链表，与删除指定元素的方式一样，删除节点后继续遍历链表，直到遍历完链表，删除所有指定的元素即可。

代码：

2.10 统计链表元素个数

代码：

2.11 清空链表

将头节点和尾节点置为空，没有引用指向直接被JVM回收

2.12 打印链表

2.13 测试

3.代码

MyLinkedList类：

接口：

异常类：

4. ArrayList和LinkedList的区别

​