双向循环链表的基本操作有：增（add)，删(remove)，改(set)，查（find)，插(insert)等。在这里我们只讲解remove，insert和getNode操作，其他实现可看下方源码。
由于双向链表有两个可见的节点（head和end），因此双向循环链表获取节点的操作和单链表有所不同。
把需要获取的节点序号和链表长度/2比较
若小于，说明节点是偏前的，因此从head开始一路next下去
若大于，说明节点是偏后的，因此从end开始一路prev上去
这样的设计能使getNode操作的时间复杂度缩短为O(logN)
获取待删除元素的节点node
把node前一个节点的next指针设置为node的后一个节点。具体实现为：node.prev.next=node.next
把node后一个节点的prev指针设置为node的前一个节点。具体实现为：node.next.prev=node.prev
由于没有指针指向node,node会被自动清理
记录链表长度的变量-1
获取待插入元素的节点node
创建一个节点mynode，next指向node，prev指向node.prev
把node.prev该节点的next指向mynode
把node的前一个节点prev指向mynode
双向循环链表的优劣
相比单链表，双向循环链表所有基本操作均快于单链表(java源码的LinkList类就是双向循环链表)
能直接获取节点的前一个节点，十分灵活
相比单链表，双链表的空间内存明显要大很多
双链表的设计应用了算法设计的“空间换时间”思想，通过消耗更多的空间来缩小操作的时间复杂度。
public class Node<Anytype> {
public Anytype data;//数据
public Node<Anytype> prev;//前一个节点
public Node<Anytype> next;//后一个节点
public Node(Anytype data,Node<Anytype> prev,Node<Anytype> next){
this.data=data;
this.prev=prev;
this.next=next;
----------------------------------------------
public class DoubleLink<AnyType> {
Node<AnyType> head;//头指针
Node<AnyType> end;//尾节点
int size;//记录链表长度
//初始化链表
public void initlist(){
end=new Node<>(null,null,null);
head=new Node<>(null,null,end);
end.prev=head;
end.next=head;
size=0;
//获取长度
public int length(){
return size;
//获取节点
public Node<AnyType> getNode(int index){
Node<AnyType> n;
if(index>=size/2){
n=end;
for(int i=length();i>index;i--){
n=n.prev;
return n;
else{
n=head;
for(int i=0;i<=index;i++){
n=n.next;
return n;
//添加元素
public void add(AnyType a){
Node<AnyType> renode=new Node<>(a,getNode(size-1),end);
renode.prev.next=renode;
renode.next.prev=renode;
size++;
//插入元素
public void insert(int i,AnyType a){
Node<AnyType> n=getNode(i);
Node<AnyType> renode=new Node<>(a,n.prev,n);
n.prev.next=renode;
n.prev=renode;
size++;
//删除元素
public AnyType remove(int i){
Node<AnyType> n=getNode(i);
AnyType data=n.data;
n.prev.next=n.next;
n.next.prev=n.prev;
size--;
return data;
//获取i位置的数据
public AnyType get(int i){
return getNode(i).data;
//为i位置元素重新赋值
public AnyType set(int i,AnyType a){
Node<AnyType> n=getNode(i);
AnyType old=n.data;
n.data=a;
return old;
//清空链表
public void clear(){
initlist();
public void print(){
for(int i=0;i<size;i++){
System.out.println(getNode(i).data);
