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

/**
* 雙向循環(huán)鏈表
* 兩個(gè)指針，next指針指向下一個(gè)結(jié)點(diǎn),prior指針指向上一個(gè)結(jié)點(diǎn),最后一個(gè)結(jié)點(diǎn)的next指針指向頭結(jié)點(diǎn)，
* 頭結(jié)點(diǎn)的prior指針指向最后一個(gè)結(jié)點(diǎn)
* */
public class LinkedList {
 private Node head;//頭節(jié)點(diǎn)
 private int size;//鏈表長度

 static private class Node{
 private int data;//數(shù)據(jù)
 private Node next;//下一個(gè)結(jié)點(diǎn)
 private Node prior;//上一個(gè)結(jié)點(diǎn)

 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;
 }

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

 return true;
 }

 //根據(jù)下標(biāo)獲取元素
 public int get(int index){
 checkElementIndex(index);
 return node(index).data;
 }
 //獲取第一個(gè)元素
 public Integer getFirst(){
 Node f=head;
 if (f==null){
  throw new NoSuchElementException();
 } else {
  return f.data;
 }
 }
 //獲取最后一個(gè)元素
 public Integer getLast(){
 if (size==0){
  throw new NoSuchElementException();
 }

 return head.prior.data;
 }

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

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


 //根據(jù)索引刪除元素
 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;//記錄下一個(gè)結(jié)點(diǎn)
  p=null;//刪除當(dāng)前結(jié)點(diǎn)
  p=next;//指向下一個(gè)結(jié)點(diǎn)
 }
 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);
  }
 }
 }



 //返回鏈表元素個(gè)數(shù)
 public int size(){
 return size;
 }


 public Boolean isEmpty(){
 return size==0;
 }
 /**雙向鏈表插入一個(gè)結(jié)點(diǎn)，要改變的指針如下:
 *
 *(1)前一個(gè)結(jié)點(diǎn)的next指針
 *(2)后一個(gè)結(jié)點(diǎn)的prior指針
 *(3)新創(chuàng)建的結(jié)點(diǎn)的prior指針和next指針
 * */
 //尾部添加結(jié)點(diǎn)
 private void linkLast(int element){
 if (size==0){//沒有結(jié)點(diǎn)時(shí)
  head=new Node(element);
  head.next=head;
  head.prior=head;
  size++;
 } else {
  //得到最后一個(gè)結(jié)點(diǎn)
  Node oldTail=head.prior;
  //new新的尾結(jié)點(diǎn) newTail
  //newTail的前一個(gè)結(jié)點(diǎn)設(shè)置為舊的尾結(jié)點(diǎn),
  //newTail的后一個(gè)結(jié)點(diǎn)指向head
  Node newTail=new Node(oldTail,element,head);
  //head的下一個(gè)結(jié)點(diǎn)指向newTail
  head.prior=newTail;
  //舊的尾結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向新的尾結(jié)點(diǎn)
  oldTail.next=newTail;
  size++;
 }

 }


 //在某結(jié)點(diǎn)之前插入結(jié)點(diǎn)
 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;
  }

  }


 }

 }
 /*
 * 雙向鏈表刪除一個(gè)結(jié)點(diǎn):
 * (1)找到該結(jié)點(diǎn)
 * (2)找到該結(jié)點(diǎn)的前一結(jié)點(diǎn)(prior)p和下一結(jié)點(diǎn)(next)q
 * (3)p的next指針指向q,q的prior指針指向p
 * (4)如果是刪除的是頭結(jié)點(diǎn)，指明當(dāng)前頭結(jié)點(diǎn)
 * */

 //刪除結(jié)點(diǎn)
 private Integer unlink(Node node){
 Integer deleteNodeData=node.data;
 Node p=null,q=null;
 if (deleteNodeData==head.data){//該結(jié)點(diǎn)為頭結(jié)點(diǎn)
  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;
 }

 //數(shù)組下標(biāo)是否越界
 private Boolean isElementIndex(int index){
 return index>=0&&index<size;
 }
 //插入位置是否越界
 public Boolean isPositionIndex(int index){
 return index>=0&&index<=size;
 }

 //檢驗(yàn)下標(biāo)是否越界，拋出異常
 private void checkElementIndex(int index){
 if(!isElementIndex(index)){
  try {
  throw new IndexOutOfBoundsException("下標(biāo)越界");
  } catch (Exception e) {
  e.printStackTrace();
  }
 }
 }

 //檢驗(yàn)插入下標(biāo)是否越界，拋出異常
 private void checkPositionIndex(int index){
 if(!isPositionIndex(index)){
  try {
  throw new IndexOutOfBoundsException("下標(biāo)越界");
  } 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();

 }
}