Java实现双向循环链表

package algorithm.datastructure.doublelinkedlist;
import java.util.NoSuchElementException;

/**
* 双向循环链表
* 两个指针，next指针指向下一个结点,prior指针指向上一个结点,最后一个结点的next指针指向头结点，
* 头结点的prior指针指向最后一个结点
* */
public class LinkedList {
 private Node head;//头节点
 private int size;//链表长度

 static private class Node{
  private int data;//数据
  private Node next;//下一个结点
  private Node prior;//上一个结点

  public Node(){
  }
  public Node(int data){
   this.data=data;
  }
  private Node(int data,Node next){
   this.data=data;
   this.next=next;
  }

  public Node(Node prior,int data,Node next){
   this.prior=prior;
   this.data=data;
   this.next=next;
  }

 }

 //初始化空链表
 public LinkedList(){
  //head=null;
 }

 //添加元素
 public Boolean add(int element){
  linkLast(element);
  return true;
 }

 //在某个位置之前添加元素
 public Boolean add(int index,Integer element){
  checkPositionIndex(index);
  if (index==size){
   linkLast(element);
  } else {
   linkBefore(element,node(index));
  }

  return true;
 }

 //根据下标获取元素
 public int get(int index){
  checkElementIndex(index);
  return node(index).data;
 }
 //获取第一个元素
 public Integer getFirst(){
  Node f=head;
  if (f==null){
   throw new NoSuchElementException();
  } else {
   return f.data;
  }
 }
 //获取最后一个元素
 public Integer getLast(){
  if (size==0){
   throw new NoSuchElementException();
  }

  return head.prior.data;
 }

 //删除第一个元素
 public Integer removeFirst(){
  Node f=head;
  if (f==null){
   throw new NoSuchElementException();
  } else {
   return unlink(head);
  }
 }

 //删除最后一个元素
 public Integer removeLast(){
  if (size==0){
   throw new NoSuchElementException();
  }
  int index=size-1;
  return unlink(node(index));
 }


 //根据索引删除元素
 public Integer remove(int index){
  checkElementIndex(index);
  return unlink(node(index));
 }

 //销毁链表
 public void destroyList(){
  clearList();
 }
 //将链表置为空表
 public void clearList() {

  for (Node p=head;p!=null;){
   Node next=p.next;//记录下一个结点
   p=null;//删除当前结点
   p=next;//指向下一个结点
  }
  size=0;
  head=null;
 }
 //遍历链表
 public void traverseList(Boolean isReverseVisited){
  if (!isEmpty()){
   if (!isReverseVisited){
    for (Node p=head;p!=head.prior;p=p.next){
     System.out.println(p.data);
    }
    System.out.println(head.prior.data);
   } else {
    for (Node p=head.prior;p!=head;p=p.prior){
     System.out.println(p.data);
    }
    System.out.println(head.data);
   }
  }
 }



 //返回链表元素个数
 public int size(){
  return size;
 }


 public Boolean isEmpty(){
  return size==0;
 }
 /**双向链表插入一个结点，要改变的指针如下:
  *
  *(1)前一个结点的next指针
  *(2)后一个结点的prior指针
  *(3)新创建的结点的prior指针和next指针
  * */
 //尾部添加结点
 private void linkLast(int element){
  if (size==0){//没有结点时
   head=new Node(element);
   head.next=head;
   head.prior=head;
   size++;
  } else {
   //得到最后一个结点
   Node oldTail=head.prior;
   //new新的尾结点 newTail
   //newTail的前一个结点设置为旧的尾结点,
   //newTail的后一个结点指向head
   Node newTail=new Node(oldTail,element,head);
   //head的下一个结点指向newTail
   head.prior=newTail;
   //旧的尾结点的下一个结点指向新的尾结点
   oldTail.next=newTail;
   size++;
  }

 }


 //在某结点之前插入结点
 private void linkBefore(int element,Node node){
  if (node==null){
   linkLast(element);
  } else {
   Node p=head;
   if (node.data==p.data){
    Node q=p.prior;
    Node newNode=new Node(q,element,p);
    q.next=newNode;
    p.prior=newNode;
    size++;
   } else {
    for (p=p.next;p!=head;){
     if (node.data==p.data){
      Node q=p.prior;
      Node newNode=new Node(q,element,p);
      q.next=newNode;
      p.prior=newNode;
      size++;
     }
     p=p.next;
    }

   }


  }

 }
 /*
 * 双向链表删除一个结点:
 * (1)找到该结点
 * (2)找到该结点的前一结点(prior)p和下一结点(next)q
 * (3)p的next指针指向q,q的prior指针指向p
 * (4)如果是删除的是头结点，指明当前头结点
 * */

 //删除结点
 private Integer unlink(Node node){
  Integer deleteNodeData=node.data;
  Node p=null,q=null;
  if (deleteNodeData==head.data){//该结点为头结点
   Node cur=head;
   p=head.prior;
   q=head.next;
   p.next=q;
   q.prior=p;
   head=q;
   cur=null;
   size--;
  } else {
   Node m;
   for (m=head.next;m!=head;){
    if (m.data==deleteNodeData){
     p=m.prior;
     q=m.next;
     p.next=q;
     q.prior=p;
     m=null;
     size--;
     break;
    }
    m=m.next;
   }

  }
  return deleteNodeData;
 }

 //数组下标是否越界
 private Boolean isElementIndex(int index){
  return index>=0&&index<size;
 }
 //插入位置是否越界
 public Boolean isPositionIndex(int index){
  return index>=0&&index<=size;
 }

 //检验下标是否越界，抛出异常
 private void checkElementIndex(int index){
  if(!isElementIndex(index)){
   try {
    throw new IndexOutOfBoundsException("下标越界");
   } catch (Exception e) {
    e.printStackTrace();
   }
  }
 }

 //检验插入下标是否越界，抛出异常
 private void checkPositionIndex(int index){
  if(!isPositionIndex(index)){
   try {
    throw new IndexOutOfBoundsException("下标越界");
   } catch (Exception e) {
    e.printStackTrace();
   }
  }
 }



 //返回指定位置的元素
 private Node node(int index){
  int nowIndex = 0;
  if(size>0){
   for (Node p=head;p!=head.prior;){
    if (nowIndex==index){
     return p;
    }
    p=p.next;
    nowIndex++;
   }
   if (nowIndex==index){
    return head.prior;
   }
  }
  return null;

 }

 public static void main(String[] args) {

  java.util.LinkedList linkedList0=new java.util.LinkedList();
  linkedList0.add(6);
  linkedList0.remove(0);
  linkedList0.size();
  linkedList0.peek();
  //linkedList0.getFirst();
  linkedList0.clear();

  //测试
  LinkedList linkedList=new LinkedList();
  linkedList.add(2);
  linkedList.add(3);
  linkedList.add(5);
  linkedList.add(7);
  linkedList.add(1);
  linkedList.add(33);

  linkedList.add(4,0);
  linkedList.add(3,1);
  linkedList.add(7,6);
  linkedList.add(0,10);
  linkedList.add(10,11);
  linkedList.remove(0);
  linkedList.remove(0);
  linkedList.remove(0);
  linkedList.remove(1);
  linkedList.remove(4);
  linkedList.remove(5);
  linkedList.remove(0);
//  linkedList.remove(0);
//  linkedList.remove(0);
//  linkedList.remove(0);
  // linkedList.remove(0);
  System.out.println(linkedList.get(0));
  System.out.println(linkedList.get(1));
  System.out.println(linkedList.get(2));
  System.out.println(linkedList.get(3));
  System.out.println(linkedList.getFirst());
  System.out.println(linkedList.getLast());
  linkedList.removeFirst();
  linkedList.removeLast();

  System.out.println("遍历链表");
  linkedList.traverseList(false);
//  System.out.println("逆向遍历链表");
//  linkedList.traverseList(true);
  System.out.println("链表长度");

  System.out.println(linkedList.size());
  linkedList.clearList();

 }
}