目录
前言
链表中的另一种模式是双链表，不同于单链表，双链表的每一个结点都有两个指针成员，一个指向它的前驱节点，一个指向它的后继结点
一、双链表的定义
不同于单链表，双链表的每一个结点都有两个指针成员，一个指向它的前驱节点，一个指向它的后继结点。
二、双链表的实现
1.结点类的定义
与单链表一致，双链表的构架也需要先定义一个双链表结点类
public class DLinkedNode<E> {
E data; //结点所含的数据
DLinkedNode<E> prior; //结点的前驱结点
DLinkedNode<E> next; //结点的后继结点
public DLinkedNode(){ //重写无参构造函数
prior = null;
next = null;
}
public DLinkedNode(E data){ //带参数的构造函数
this.data = data;
prior = null;
next = null;
}
}2.双链表泛型类的构建
在定义完结点类之后，就可以开始构造双链表类了
public class DLinkedListClass<E> {
DLinkedNode<E> dHead;
public DLinkedListClass(){
dHead = new DLinkedNode<E>(); //双链表头结点
dHead.prior = null; //初始化空的双链表
dHead.next = null;
}
}3.双链表的基本算法
双链表的许多算法与单链表中的相同，如求长度，取值，查找元素等。只有涉及插入和删除的方法不一致。插入结点的操作如下图
1）以头插法整体建立双链表
在知道了如何插入结点，我们就可以整体建立双链表了，建立的思路与单链表一致
/**
* 头插法，得到的双链表与原数组顺序相反
* @param arr
*/
public void creatDListFirst(E[] arr){
DLinkedNode dataNode;
for (int i=0;i<arr.length;i++){
dataNode = new DLinkedNode<E>(arr[i]);
dataNode.next = dHead.next; //如图中的步骤1
if(dHead.next!=null){ //双链表需要判断，因为null是没有前驱结点的
dHead.next.prior = dataNode; //如图中的步骤2
}
dataNode.prior = dHead; //如图中的步骤3
dHead.next = dataNode; //如图中的步骤4
}
}2）以尾插法整体建立双链表
/**
* 尾插法，得到的双链表与原数组顺序一致
* @param arr
*/
public void creatDListLast(E[] arr){
DLinkedNode<E> dataNode;
DLinkedNode<E> pointer = dHead;
for (int i = 0; i < arr.length; i++) {
dataNode = new DLinkedNode<E>(arr[i]);
dataNode.prior = pointer; //将pointer设为dataNode的前驱结点
pointer.next = dataNode; //将dataNode设为pointer和后继结点
pointer = dataNode; //将指针移到pointer上，即尾结点
}
pointer.next = null; //将尾结点的后继结点设为null
}
3）将元素插入i位置
与单链表一致，双链表在插入时也需要获取前一位元素，我们通过getI(i-1)的方式获取
/**
* 在第i号位置插入数据E
* @param i
* @param data
*/
public void insert(int i,E data){
DLinkedNode<E> dataNode = new DLinkedNode<E>(data);
DLinkedNode<E> pointer = getI(i-1); //获取前一位元素
dataNode.next = pointer.next; //如图中步骤1
if(pointer.next!=null) { //双链表需要判断，因为null是没有前驱结点的
pointer.next.prior = dataNode; //如图中步骤2
}
dataNode.prior = pointer; //如图中步骤3
pointer.next = dataNode; //如图中步骤4
}
4）双链表的删除操作
跟单链表一样，双链表的删除操作其原理就是将该结点”孤立“，只要将该结点的前驱结点与其后继结点相连，就可以让双链表在不通过该结点的同时正常运作。但与单链表不同的是，双链表不需要找到该结点的前驱结点，因为可以通过pointer.prior直接获取，具体操作如下图
代码如下
/**
* 删除第i位的元素
* @param i
*/
public void delete(int i){
DLinkedNode<E> pointer = getI(i);
if(pointer.next!=null){
pointer.next.prior = pointer.prior;
}
pointer.prior.next = pointer.next;
}三、双链表的应用
删除双链表中第一个值为x的结点。思路很简单，只要指针指到值为x的结点然后进行删除操作即可。代码如下：
/**
* 删除双链表中第一个为x的值
* @param DList
* @param x
*/
public static void deleteX(DLinkedListClass<Integer> DList, Integer x){
DLinkedNode<Integer> pointer = DList.dHead.next; //创建指针，指向头结点
while (pointer!=null && pointer.data!=x){ //查找第一个为x的值
pointer = pointer.next; //指针后移
}
if(pointer!=null){ //如果指针未指到尾，表示找到了x
if(pointer.next!=null){ //双链表需要判断，因为null是没有前驱结点的
pointer.next.prior = pointer.prior;
}
pointer.prior = pointer.next;
}
}
总结
双链表中的代码很大一部分跟单链表一致，但需要注意的是，在双链表中，有时需要通过（pointer.next!=null）来判断是否为尾结点，如果是的话，便不能调取pointer.next.prior。