单链表只有一个后继指针，所以只能从前往后遍历，无法向前遍历寻找前面的结点。双链表除了有后继指针之外，还有一个指向前一个结点的前驱指针，这样既可以往后遍历，也可以往前遍历。

双链表结点

双链表有两个指针域和一个数据域，数据域存放数据，两个指针域分别指向前驱结点和后继结点。

public class DoubleListNode {
    int id;
    DoubleListNode previous;
    DoubleListNode next;

    public DoubleListNode(int id) {
        this.id = id;
    }
}

双链表

双链表有前驱指针，所以寻找当前结点的前一个结点只需要 O(1) 的时间复杂度即可。单链表只能从前向后遍历，双链表可以从头遍历，也可以从后往前遍历，在操作上更灵活。

创建双链表

和单链表一样，双链表也可以使用头插法和尾插法建立双链表。在建立链表时，使用带头结点的链表进行插入和删除操作时更方便。使用头结点，在对首结点和尾结点进行操作时，和其他普通结点操作一样，如果没有头结点，操作首结点和尾结点时要进行额外的判断处理。

头插法建立双链表

头插法建立双链表，每次插入的新结点都插入到头结点后面作为新的首结点。在插入的过程中，要保证链表不能出现断链的情况，否则无法找到后面的结点。

DoubleListNode head = new DoubleListNode(0);

/**
  * 头插法建立双链表
  * @param n 节点个数
  */
public void headCreateDoubleLinkedList(int n) {
    if (n <= 0) {
        System.out.println("参数不合法！");
        return;
    }
    // 建立第一个节点
    DoubleListNode first = new DoubleListNode(1);
    // 头节点前驱指针和第一个节点后继指针置为空
    head.previous = null;
    head.next = first;
    first.previous = head;
    first.next = null;
    // 循环建立节点插入头节点后面
    for (int i = 2; i <= n; i++) {
        DoubleListNode node = new DoubleListNode(i);
        node.next = head.next;
        head.next.previous = node;
        node.previous = head;
        head.next = node;
    }
}

尾插法建立双链表

尾插法建立双链表，每次插入的新结点都插入到上一次插入的结点后面作为新的尾结点。

/**
  * 尾插法建立双链表
  * @param n 节点个数
  */
public void tailCreateDoubleLinkedList(int n) {
    if (n <= 0) {
        System.out.println("参数不合法！");
        return;
    }
    DoubleListNode temp = head;
    for (int i = 1; i <= n; i++) {
        DoubleListNode node = new DoubleListNode(i);
        temp.next = node;
        node.previous = temp;
        temp = temp.next;
    }
}

插入结点

双链表插入结点只需要修改结点的指针指向即可，不需要移动元素，所以插入结点的时间复杂度为 O(1)，但是链表只能按顺序遍历，所以查找结点要插入的位置的时间复杂度为 O(n)，综合来看，**双链表插入结点的时间复杂度还是 O(n)**。

/**
  * 插入节点，在要插入节点后面插入
  * @param n 插入位置
  * @param m 节点数据
  */
public void addDoubleListNode(int n, int m) {
    // 获取链表长度
    int length = getDoubleLinkedListLength();
    if (n < 0 || n > length) {
        System.out.println("插入位置非法！");
        return;
    }
    DoubleListNode temp = head;
    int count = 0;
    // 只有头节点
    if (length == 0) {
        DoubleListNode node = new DoubleListNode(m);
        temp.next = node;
        node.previous = temp;
        return;
    }
    // 移动指针到要插入的节点位置
    while (count < n) {
        count++;
        temp = temp.next;
    }
    // 在结尾插入节点
    if (n == length) {
        DoubleListNode node = new DoubleListNode(m);
        temp.next = node;
        node.previous = temp;
        return;
    }
    DoubleListNode node = new DoubleListNode(m);
    node.next = temp.next;
    temp.next.previous = node;
    node.previous = temp;
    temp.next = node;
}

删除结点

删除结点只需要将要删除结点的前驱结点的后继指针指向删除结点的后继结点，再将后继结点的前驱指针指向删除结点的前驱结点，无须移动元素，所以双链表删除结点的时间复杂度是 O(1)。同样，删除结点前，需要先遍历找到该结点，遍历需要的时间复杂度是 O(n)，所以删除结点的时间复杂度也是 O(n)。

/**
  * 删除节点
  * @param n 节点位置
  */
public void deleteDoubleListNode(int n) {
    int length = getDoubleLinkedListLength();
    if (n <= 0 || n > length) {
        System.out.println("节点不存在！");
        return;
    }
    DoubleListNode temp = head;
    int value;
    int count = 0;
    // 只有一个节点，head的next置为null
    if (length == 1) {
        value = temp.next.id;
        System.out.println("删除的节点值为：" + value);
        temp.next = null;
        return;
    }
    while (count < n) {
        count++;
        temp = temp.next;
    }
    // 删除最后一个节点，next置为null
    if (n == length) {
        value = temp.id;
        System.out.println("删除的节点值为：" + value);
        temp.previous.next = null;
        return;
    }
    value = temp.id;
    System.out.println("删除的节点值为：" + value);
    temp.previous.next = temp.next;
    temp.next.previous = temp.previous;
}