双向链表的定义
双向链表也叫双面链表，它的每个节点由三部分组成：prev 指针指向前置节点，此节点的数据和 next 指针指向后置节点。
双向链表的数据结构
具体如下图所示：
双向链表有如下特点：
1）可以使用一个head和一个tail分别指向头部和尾部的节点；
2）每个节点都由三部分组成：前一个节点的指针prev、保存的元素item、后一个节点的指针next；
3）双向链表的第一个节点的prev是null
4）双向链表的最后节点的next是null
为什么需要双向链表？
单向链表的遍历方向单一，只能从链头一直遍历到链尾。所以有一个比较大的缺点：当要查询某一个节点的前一个节点时，只能再次从头进行遍历查询，因此效率比较低。
除此之外，还有两个缺点：
1)单向链表要查询某一个节点的前一个节点时，只能再次从头进行遍历查询，因此效率比较低；
2)单线链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除。
所以，这个时候双向链表就派上用场了，改进了单向链表的缺点。
双向链表的应用场景？
单向链表适用于解决一条道走到黑的访问场景，比如给正在排队测温的人测量，只需要测试一次就下一位，无需重复测试。
循环链表适用于具有环状数据结构的场景，比如丢手绢游戏，双向链表则适合需要提供多个方向访问功能的数据结构，比如老师在考场监考，可以来回走动：假设这个考场座位是顺序的。
双向链表的应用举例
双向链表的实现思路主要包含如下几个核心方法：
1）遍历：和单链表不一样的地方，在于不仅可以向前，还可以向后查找；
2）添加：先找到双向链表的最后这个节点，把数据添加到双向链表的最后；
3）修改：通过遍历找到该节点，然后直接吧数据替换掉就可以了，思路与单链表是一样的；
4）删除
下面是具体的代码示例：
public class DoubleLinkedList<E> {
// 链表元素的数量
private int size;
// 声明头结点
private Node first;
// 声明尾节点
private Node last;
// 创建Node节点
private class Node{
// 存放内容
public E data;
// 指向链表的上一个节点
public Node prev;
// 指向下一个节点
public Node next;
// 构造方法
public Node() {
}
public Node(Node prev, E data, Node next) {
this.prev = prev;
this.data = data;
this.next = next;
}
@Override
public String toString(){
return data.toString();
}
}
// 初始化头结点
public DoubleLinkedList(){
first = null;
last = null;
size = 0;
}
/***
* 获取链表中的元素个数
* @return
*/
public int getSize(){
return size;
}
/***
* 返回链表是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/***
* 根据链表的index位置添加新的元素e
* @param index
* @param data
*/
public void add(int index, E data){
// 调用方法
rangeCheckAdd(index);
if (index == size) { // 往最后面添加元素
addLast(data);
} else if(index == 0){
addLast(data);
} else {
// 新添加节点下一个元素
Node nextNode = node(index);
// 新添加节点的上一个元素
Node prevNode = nextNode.prev;
// 新添加节点
Node newNode = new Node (prevNode, data, nextNode);
// next节点的上一个prev指向新节点
nextNode.prev = newNode;
// prevNode节点的下一个next指向新节点
prevNode.next = newNode;
}
size++;
}
/***
* 在链表头添加新的元素e
* @param data
*/
public void addFirst(E data){
// 创建一个新节点
Node newNode = new Node(null, data, null);
if(isEmpty()){
last = newNode; // last -> newNode
}else {
first.prev = newNode; // first.prev->newNode
}
newNode.next = first; // newNode.next -> first;
first = newNode;
size++;
}
/***
* 在链表末尾添加新的元素e
* @param data
*/
public void addLast(E data){
// 创建一个新节点
Node newNode = new Node(null, data, null);
if(isEmpty()){
first = newNode; // first->newNode
}else{
last.next = newNode; // last指向的节点指向新节点
newNode.prev = last; // 新节点的前驱指向last指针
}
last = newNode; // last指针指向新节点
size++;
}
/**
* 获取index位置对应的节点对象
* @param index
* @return
*/
private Node node(int index) {
rangeCheck(index);
Node node;
if (index < (size >> 1)) {
node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
} else {
node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
}
return node;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("size=").append(size).append(", [");
// 定义一个指针变量
Node cur = first;
while(cur != null){
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL");
res.append("]");
return res.toString();
}
// 索引值检查范围方法
private void rangeCheck(int index){
if(index < 0 || index >=size){
// 调用越界处理方法
outOfBounds(index);
}
}
// 添加方法索引检查范围
private void rangeCheckAdd(int index){
if(index < 0 || index >size){
// 调用越界处理方法
outOfBounds(index);
}
}
// 数组索引越界处理
private void outOfBounds(int index){
throw new IndexOutOfBoundsException("index:" + index + ", Size:" + size);
}
}
关于mikechen
mikechen睿哥，10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获取更多技术干货！
