package code;

class Node
{
 Node next;
 int data;
 public Node(int data)
 {
 this.data=data;
 }
 
}
class LinkList
{
 Node first;
 //頭部
 public LinkList()
 {
 this.first=null;
 }
 public void addNode(Node no)
 {
 no.next=first;
 first=no;//在頭部添加
 }
 public void delectNode()
 {
 Node n=first.next;
 first=null;
 first=n;//在頭部刪除
 }
 //刪除指定位置
 public int Number()
 {
 int count=1;
 //查看有多少元素
 Node nd=first;
 while(nd.next!=null)
 {
  nd=nd.next;
  count++;
 }
 return count;
 }
 public void delectExact(int n)
 {
 //刪除指定位置
 if(n>1)
 {
  int count=1;
  Node de=first;
  while(count<n-1)
  {
  de=de.next;
  count++;
  
  }
  de.next=de.next.next;
 }
 else
  first=first.next;
 
 }
 public void addExact(int n,Node nd)
 {
 if(n>1)//添加指定位置
 {
  int count=1;
  Node de=first;
  while(count<n-1)
  {
  de=de.next;
  count++;
  
  }
  nd.next=de.next;
  de.next=nd;

 }
 else
  first=first.next;
 }
 public int findNode(int n)
 {
 int count=1;//查找一個(gè)數(shù)對(duì)應(yīng)的位置
 Node de=first;
 while(de.data!=n)
 {
  de=de.next;
  count++;
  if(de==null)
  {
  return -1;
  }
 }
 return count;
 }
 public void print()
 {
 Node no=first;//打印所有
 while(no!=null)
 {
  System.out.println(no.data);
  no=no.next;
 }
 }
}
public class TextNode
{
 public static void main(String[] args)
 {
 LinkList ll=new LinkList();
 ll.addNode(new Node(12));
 ll.addNode(new Node(15));
 ll.addNode(new Node(18));
 ll.addNode(new Node(19));
 ll.addNode(new Node(20));
 /*System.out.println(ll.first.data);

 ll.delectNode();
 System.out.println(ll.first.data);*/
 System.out.println(ll.Number());
 ll.delectExact(3);
 ll.addExact(3, new Node(100));
 System.out.println(ll.Number());
// ll.print();
 System.out.println(ll.findNode(112));
 
 }
}

public class DoubleLink
{
 public static void main(String[]args)
 {
 Node2 no=new Node2(5);
 no.addLeft(new Node2(6));
 no.addRight(new Node2(7));
 /*no.print();
 no.print2();*/
 no.addExact2(1, new Node2(8));
 no.print();
 System.out.println("--------------");
 no.print2();
 }
}
class Node2
{
 public Node2 first;
 public Node2 end;
 public Node2 left;
 public Node2 right;
 int data=0;
 public Node2(int n)
 {
 
 first=this;
 end=this;
 
 first.data=n;
 }
 //從頭部添加
 public void addLeft(Node2 before)
 {
 first.left=before;
 before.right=first;
 first=before;
 }
 //從尾部添加
 public void addRight(Node2 after)
 {
 end.right=after;
 after.left=end;
 end=after;
 }
 //插入正數(shù)(第三聲)的第幾個(gè)
 public void addExact(int n,Node2 no)
 {
 int count=0;
 if(n==0)
 {
  addLeft(no);
 }
 else
 { 
  Node2 f=first;
  while(true)
  {
  f=f.right;
  count++;
  if(count==n)
  {
   //此處為四個(gè)指針的指向的變化
   no.left=f.left;
   f.left.right=no;
 //  first.left=no;
   no.right=f;
   f.left=no;
   break;
  }
 
  }
 }
 }
 //插入倒數(shù)的第幾個(gè)
 public void addExact2(int n,Node2 no)
 {
 int count=0;
 if(n==0)
 {
  addRight(no);
 }
 else
 {
  Node2 f=end;
  while(true)
  {
  f=f.left;
  count++;
  if(count==n)
  {
   
   no.left=f;
   no.right=f.right;
   f.right.left=no;
   f.right=no;
   break;
   
  }
  }
 }
 }
 //正序遍歷
 public void print()
 {
 System.out.println(first.data);
 while(first.right!=null)
 {
  System.out.println(first.right.data);
  first=first.right;
 }
// System.out.println(end.data);
 }
 //倒序遍歷
 public void print2()
 {
 System.out.println(end.data);
 while(end.left!=null)
 {
  System.out.println(end.left.data);
  end=end.left;
 }
 }
 

}
/*值得注意的是，每一次插入一個(gè)新的對(duì)象的時(shí)候，需要注意指針指向的改變。
首先是這個(gè)新的對(duì)象兩邊的指向（左和右），其次是時(shí)左邊的對(duì)象向右的指向
和右邊對(duì)象向左的指向。
這四個(gè)指針的指向必須正確，否則可能導(dǎo)致正序或者倒序遍歷無(wú)法實(shí)現(xiàn)。
*/
/*對(duì)比單鏈表，單鏈表只能從一個(gè)方向遍歷，因?yàn)橹挥幸粋€(gè)頭，而雙向鏈表，有頭和尾，可以從
 * 頭遍歷，也可以從尾遍歷，而且其中一個(gè)對(duì)象因?yàn)橛袃蓚€(gè)方向的指針，所以他可以獲得左邊的
 * 對(duì)象也可以獲得右邊的對(duì)象。
 * 但是單鏈表的話，因?yàn)橹挥幸粋€(gè)方向，所以只能向左或右。添加對(duì)象的時(shí)候，雙向也可以從頭添加，也可以從尾添加。
 * 如果單鏈表要實(shí)現(xiàn)兩個(gè)方向添加比較難得，或者說(shuō)不行，因?yàn)樗挥邢蜃蠡蛳蛴业囊粋€(gè)方向的指針
 * 而雙向鏈表每個(gè)對(duì)象都有兩個(gè)方向的指針沒(méi)這樣更靈活，但是這同樣有缺點(diǎn)，因?yàn)檫@樣的話每個(gè)對(duì)象
 * 都會(huì)包含兩個(gè)指針，這同樣內(nèi)存會(huì)消耗更多。
 * 
 * */