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

/*
* 鏈表
* 物理存儲上非連續(xù)的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現
* 
* */
public class LinkedList {
 private Node head;//頭節(jié)點
 private int size;//鏈表長度
 static private class Node{
 private int data;
 private Node next;
 public Node(){

 }
 private Node(int data,Node next){
  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();
 }
 int index=size-1;
 return node(index).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(){

 for (Node p=head;p!=null;){
  System.out.println(p.data);
  p=p.next;
 }
 }

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


 //尾部添加結點
 private void linkLast(int element){
 Node cur =null,p;
 if (size==0){//沒有結點時
  head=new Node(element,null);
  size++;
  return;
 }
 for (p=head;p!=null;){//有結點時候
  cur=p;
  p=cur.next;
 }
 cur.next= new Node(element,null);//尾部添加元素
 size++;
 }


 //在某結點之前插入結點
 private void linkBefore(int element,Node node){
 if (node==null){
  linkLast(element);
 } else {
  Node p=head,q=p.next;
  if (node.data==p.data){//node為結點時候
  head= new Node(element, p);//在頭部插入元素
  size++;
  } else {
  while (p!=null){
   if (q.data==node.data) {
   p.next= new Node(element,q);//在q之前(p之后)插入一個元素
   size++;
   break;
   }
   p=p.next;
   q=p.next;
  }

  }
 }

 }

 //刪除結點
 private Integer unlink(Node node){
 Integer deleteNodeData=null;
 Node p=null;
 deleteNodeData=node.data;
 if (node.data==head.data){//該節(jié)點為頭結點
  p=head;
  head=p.next;
  p=null;
  size--;
 } else {
  Node q=head;
  for (p=q.next;p!=null;){//使用兩個指針,p,q
  if (p.data==node.data){
   break;
  }
  q=q.next;//p始終為q的next結點
  p=q.next;
  }
  q.next=p.next;
  p=null;//刪除p
  size--;
 }
 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!=null;){
  if (nowIndex==index){
   return p;
  }
  p=p.next;
  nowIndex++;
  }
 }
 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(6);
 linkedList.add(0);
 linkedList.add(3);
 linkedList.add(8);
 linkedList.add(10);
 System.out.println(linkedList.get(0));
 System.out.println(linkedList.getFirst());
 System.out.println(linkedList.getLast());
 System.out.println(linkedList.get(5));
 System.out.println(linkedList.remove(5));
 System.out.println(linkedList.remove(4));

 linkedList.remove(2);
 linkedList.remove(0);
 linkedList.remove(0);
 linkedList.remove(0);

 linkedList.add(2);
 linkedList.add(6);
 linkedList.add(0);
 linkedList.add(3);
 linkedList.add(8);
 linkedList.add(10);

 linkedList.removeFirst();
 linkedList.removeFirst();
 linkedList.removeLast();
 System.out.println(linkedList.size());


 System.out.println("遍歷鏈表");
 linkedList.traverseList();
 linkedList.add(0,4);
 linkedList.add(0,5);
 linkedList.add(2,5);

 linkedList.add(4,5);

 linkedList.add(6,9);
 linkedList.add(8,11);
 linkedList.add(9,222);
 // linkedList.linkBefore(3,new Node(3,null));
// linkedList.linkBefore(3,new Node(2,null));
// linkedList.linkBefore(3,new Node(2,null));
// linkedList.linkBefore(7,new Node(2,null));
// linkedList.linkBefore(9,new Node(7,null));
// linkedList.linkBefore(9,new Node(8,null));
 System.out.println("遍歷鏈表");
 linkedList.traverseList();
 linkedList.clearList();



 }
}