//含有rear,尾插时时O（1）的复杂度
package linearList;
//凡是实现后插后删都比较容易，尽量向着这个方向转换
public class linearList {
class node {
private int data;
private node next;
public node(int data,node next){
this.data=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=data;//没有length++；
}
int removefirst()//头删
{if(head.next ==null){return 0;}
if(head.next==rear){
int data=rear.data;
head.next=null;
rear=head;length--; return data;}
int data=head.next.data;
head.next=head.next.next;length--;
return data;
}
int removelast()//尾删
{node n=head;int data=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=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==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==data)return 1;
n=n.next;
}
return -1;
}
node find(int data)//找节点
{node n=head;
while(n!=null){
if(n.data==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;
}
}