//含有rear,尾插时时O（1）的复杂度
package linearList;
//凡是实现后插后删都比较容易，尽量向着这个方向转换
public  class linearList {
      class node {
     private  int data;
     private  node next;
     public node(int data,node next){
      this.data=http://www.mamicode.com/data;
      this.next=next;}
     }
    private node head;
    private node rear;//两个引用，指向空
    private  int length=0;
    public linearList(){
      head=new node(0,null);
      rear=head;
     }
    void addfirst(int data)//头插
    {if(head.next==null){
      node n=new node(data,null);
      head.next=n; rear=n;length++;}
     else {node n=new node(data,head.next);head.next=n;length++;}}
    void addlast(int data)//尾插
    {node n=new node(data,null);
     rear.next=n;
     rear=n;length++;}
    void addafter(node n,int data)//后插
    {node n1=n.next;
    if(n1==null){
     node n2=new node(data,null);
    n.next=n2;rear=n2;length++;
    }
    else{
     node n2=new node(data,n.next);
     n.next=n2;length++;
    }
    } 
    void addbefore(node n,int data)//前插
    {addafter(n,n.data);
    n.data=http://www.mamicode.com/data;//没有length++；
    }
    int removefirst()//头删
    {if(head.next ==null){return 0;}
    if(head.next==rear){
    int data=http://www.mamicode.com/rear.data;
    head.next=null;
    rear=head;length--; return data;}
    int data=http://www.mamicode.com/head.next.data;
    head.next=head.next.next;length--; 
    return data;
    }
    int removelast()//尾删
    {node n=head;int data=http://www.mamicode.com/rear.data;
     while(n!=null){
      if(n.next.equals(rear))
      {n.next=null;rear=n;}
      n=n.next;
     }length--; 
     return data;
    }
   
    int removeafter(node n)//后删
    {if(n.next==null)return 0;
     node n1=n.next;int data=http://www.mamicode.com/n1.data;
     if(n1.next==null){
      n.next =null;
      rear=n;}
     n.next=n1.next;
     length--; 
     return data;}
    int removebefore(node n)//前删
    {node n1=head.next;
    if(n1==n)return 0;
     while(n1!=null){
      if(n1.next.next.equals(n)){
       return removeafter(n1);}//遇到第一个满足条件的节点便跳出
      n1=n1.next;
     }//没有length--；
     return 0;
    }
    int ofdex(int data)//找序
    {node n=head;int i=0;
     while(n!=null){
      if(n.data=http://www.mamicode.com/=data)break;
      n=n.next;i++;
     }
        return i;
    }
    boolean Isempty()//判空
    {if(head.next==null)
     return true;
    return false;}
   
    int contains(int data)//判含
    {node n=head;
    while(n!=null){
     if(n.data=http://www.mamicode.com/=data)return 1;
     n=n.next;
    }
    return -1; 
    }
 node find(int data)//找节点
 {node n=head;
 while(n!=null){
  if(n.data=http://www.mamicode.com/=data)return n;
 n=n.next;
 }
 return null;
 }
 public void clear()//清空
 {head.next=null;
 rear=head; length=0;
 }
 int size()//链表长度
    {return length;}
 void traverse()//遍历
 {if(head.next==null){System.out.println("该链表为空");return;}
 node n=head.next;
 for(int i=0;i<length;i++){
 System.out.println(n.data);
 n=n.next;
 }
 }

LinkList(JAVA版，contain rear)