前言：前面介绍了循环链表，虽然循环链表可以解决单链表每次遍历只能从头结点开始，但是对于查询某一节点的上一节点，还是颇为复杂繁琐，所以可以在结点中加入前一个节点的引用，即双向链表

一、简介

　　 双向链表：在链表中，每一个节点都有对上一个节点和下一个节点的引用或指针，即从一个节点出发可以有两条路可选择。

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

　　 特性：

• 遍历可逆性：可以反向遍历；
• 相比于单链表，循环单链表无论是插入还是遍历，更便利，更快捷；
• 双向链表可以有效的提高算法的时间性能，说白了就是用空间换时间；

二、双向链表实现

　　 1、创建节点类Node，其中有三个属性pre、object、next，pre为上一个节点的引用，也叫作前驱节点，object存储数据，next为下一个节点的引用，也叫作后继节点：

public class BothwayLoopChain<T> {//头结点直接引用private Node<T> head;//链长度private Integer size;//初始化    BothwayLoopChain() {
        head = new Node<T>();
        head.setNext(null);
        size = 0;
    }class Node<T> {private Node<T> pre;private Object object;private Node<T> next;public Node<T> getPre() {return pre;
        }public void setPre(Node<T> pre) {this.pre = pre;
        }public Object getObject() {return object;
        }public void setObject(Object object) {this.object = object;
        }public Node<T> getNext() {return next;
        }public void setNext(Node<T> next) {this.next = next;
        }

    }
    
}

BothwayLoopChain.java

　　 2、获取位置的结点：

public T get(Integer index) throws Exception {return (T) getNode(index).getObject();
    }private Node<T> getNode(Integer index) throws Exception {if (index > size || index < 0) {throw new Exception("index outof length");
        }
        Node<T> p = head;for (int i = 0; i < index; i++) {
            p = p.next;
        }return p;
    }

　　 3、插入节点：

//在尾节点后插入节点public void add(T t) throws Exception {this.add(t,size);
    }//在index位置后插入一个节点public void add(T t, Integer index) throws Exception {//创建新节点Node<T> p = new Node<>();
        p.setObject(t);//获取该位置的节点Node<T> s = getNode(index);
        p.setPre(s);if (s.getNext() != null) {//将本节点的next节点放入新节点的next节点            p.setNext(s.getNext());
            s.getNext().setPre(p);
        } else {
            p.setNext(null);
        }
        size++;
    }

　　 4、移除节点：

//移除节点并返回public Node<T> remove(Integer index) throws Exception {//获取该位置的节点Node<T> s = getNode(index);//获取该位置节点的下一个节点Node<T> next = s.getNext();//将本节点的pre节点的next节点设置为next        s.getPre().setNext(next);
        next.setPre(s.getPre());return s;
    }

　　至此，双向链表的基本实现已完成，其实它就是 用空间换时间来提高性能的；

　　之前了解了单链表的循环结构即单向循环链表，举一反三，双向链表也有循环结构，即双向循环链表；

三、双向链表扩展—双向循环链表

在双向链表的基础上进行改造：

• 尾节点的next指向头结点；
• 头结点的pre指向尾节点；

　　除了插入方法，其他方法可保持不变：

//在index位置后插入一个节点public void add(T t, Integer index) throws Exception {//创建新节点Node<T> p = new Node<>();
        p.setObject(t);//获取该位置的节点Node<T> s = getNode(index);
        p.setPre(s);//将本节点的next节点放入新节点的next节点        p.setNext(s.getNext());
        s.getNext().setPre(p);
        size++;
    }