简介
双向链表也叫双面链表，它的每个节点由三部分组成：prev 指针指向前置节点，此节点的数据和 next 指针指向后置节点，如下图所示：
特点：
节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针prev）和下一个节点地址（后继指针next）。
首节点的前驱指针prev和尾节点的后继指针均指向空地址。
分类
线性结构有线性结构有两种不同的存储结构,即顺序存储结构(数组)和链式存储结构(链表)。
顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的。
链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息。
添加尾结点
1、
指定节点插入
思路： 假设在BC直接插入新节点N
B 节点的后续节点指向 N
N 节点 的前驱节点指向 B
N 节点的后续节点指向 C
C 节点的前驱节点指向 N
重要的也就是要找到B节点的位置，转存C节点；
和单项链表的对比
和单链表相比，存储相同的数据，需要消耗更多的存储空间。
插入、删除操作比单链表效率更高O(1)级别。以删除操作为例，删除操作分为2种情况：给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为O(n)。对于第二种情况，要进行删除操作必须找到前驱节点，单链表需要从头到尾进行遍历直到p->next = q，时间复杂度为O(n)，而双向链表可以直接找到前驱节点，时间复杂度为O(1)。
对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p，每一次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
代码
public class DoubleList {
private Node head;
private int size;
class Node {
T value;
Node pre;
Node next;
public Node(T value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" +value +
", pre=" +pre +
", next=" +next +
'}';
}
}
//插入头节点
public void addFirst(T value) {
//创建节点
Node node =new Node(value);
if (null ==head) {
head =node;
return;
}
//1、新节点的pre设置为null
//2、新节点的next设置为原有的head
//3、原来的head的pre执行新节点
node.next =head;
head.pre =node;
head =node;
}
//插入尾节点
public void addLast(T value) {
Node node =new Node(value);
if (head ==null) {
head =node;
return;
}
//找到尾节点
Node cur =head;
while (cur.next !=null) {
cur = cur.next;
}
//1、尾节点的next指向新节点
//2、新节点的pre指向尾巴节点
cur.next =node;
node.pre = cur;
}
public void add(T value,int index) {
//校验索引
if (index <0 || index > size()) {
throw new IndexOutOfBoundsException("IndexOutOfBoundsException");
}
//索引为0直接添加表头
if (index ==0) {
addFirst(value);
return;
}
//索引等于链表的长度,添加到表尾巴
if (index == size()) {
addLast(value);
return;
}
Node node =new Node(value);
Node pre =head;
int point =0;
//这里找到的是插入位置的上一个节点
while ((index -1) != point) {
pre = pre.next;
point++;
}
//当前节点的下一个节点
Node nextNode = pre.next;
//上一个节点设置
pre.next =node;
//当前节点设置
node.pre = pre;
node.next =nextNode;
//下一个节点设置
nextNode.pre =node;
}
//删除头节点
public void removeFirst() {
//元素不存在的直接返回
if (size() ==0) {
return;
}
//只有一个节点，头节点设置为null
if (size() ==1) {
head =null;
return;
}
//获取头节点的后续节点
Node next =head.next;
next.pre =null;
head =next;
}
//删除表尾
public void removeLast() {
if (size() ==0) {
return;
}
if (size() ==1) {
head =null;
return;
}
//找到最后一个节点的上一个节点
Node cur =head;
while (cur.next !=null) {
cur = cur.next;
}
cur.pre.next =null;
}
//删除指定节点
public void remove(int index) {
if (index <0 || index >= size()) {
throw new IndexOutOfBoundsException("IndexOutOfBoundsException");
}
// 头节点
if (index ==0) {
removeFirst();
return;
}
// 尾节点
if (index == (size() -1)) {
removeLast();
return;
}
//找到删除节点的前一个节点
Node pre =head;
int point =0;
while ((index-1)!=point){
pre = pre.next;
point++;
}
//获取下一个节点
Node delNode = pre.next;
Node nextCode = pre.next.next;
pre.next =nextCode;
nextCode.pre = pre;
delNode.next =null;
delNode.pre =null;
}
//顺序打印链表
public void display() {
//将表头作为当前节点
Node cur =head;
while (cur !=null) {
System.out.println(cur.value);
cur = cur.next;
}
}
//获取链表的长度
public int size() {
int size =0;
Node cur =head;
while (cur !=null) {
cur = cur.next;
size++;
}
return size;
}
@Override
public String toString() {
return "DoubleList{" +
"head=" +head +
", size=" +size +
'}';
}
}
