java单链表插入删除查询

/*本程序是程序的入口，打印菜单并调用相应的功能*/ 
import java.io.InputStreamReader;
import java.io.BufferedReader;
public class TestLinkedList{
  public static void main(String args[]){
  int select=0;
  int value=-1,temp=0;
  MyLinkedList linkedList=new MyLinkedList(10);
  InputStreamReader ir = new InputStreamReader(System.in);
  BufferedReader in = new BufferedReader(ir);
  bh:while(true){
   System.out.println("===========车厢的操作===========");
   System.out.println("          1.插入车厢");
   System.out.println("          2.删除车厢");
   System.out.println("          3.修改车厢号");
   System.out.println("          4.查询车厢");
   System.out.println("          5.打印车厢");
   System.out.println("          6.退出程序");
   System.out.println("===============================");
   System.out.print("请选择车厢的操作：");
   try{
    select=Integer.parseInt(in.readLine());
   }catch(Exception e){
    System.out.println("输入错误！程序回到主菜单！");
    continue;
    }
    switch (select){
      case 1: //1.插入
       System.out.println("请输入要插入的数据：");
       try{
         value=Integer.parseInt(in.readLine());
       }catch(Exception e){
         System.out.println("输入错误！程序回到主菜单！");
         continue;
        }
       linkedList.insert(value);
       break;
      case 2:  //2.删除
        System.out.println("请输入要删除的车厢：");
        try{
         value=Integer.parseInt(in.readLine());
       }catch(Exception e){
         System.out.println("输入错误！程序回到主菜单！");
         continue;
        }
       linkedList.delete(value);
       break;
      case 3: //3.修改  
        System.out.println("请输入要替换的车厢：");
        try{
         value=Integer.parseInt(in.readLine());
       }catch(Exception e){
         System.out.println("输入错误！程序回到主菜单！");
         continue;
       }
       System.out.println("请输入新的车厢：");  
       try{
         temp=Integer.parseInt(in.readLine());
       }catch(Exception e){
         System.out.println("输入错误！程序回到主菜单！");
         continue;
        }
       linkedList.update(value,temp);
       break;
      case 4:  //4.查询
        System.out.println("请输要查询的车厢：");  
       try{
         value=Integer.parseInt(in.readLine());
       }catch(Exception e){
         System.out.println("输入错误！程序回到主菜单！");
         continue;
        }
       linkedList.select(value);
       break;
     case 5:  //5.打印
       linkedList.print();
       break;
     case 6:  //6.退出
       System.out.println("程序退出");
       break bh;
      default:
        System.out.println("选择的功能不存在！程序回到主菜单！");
    } //switch
  }//while
  }
}
/*
类MyLinkeList 是单向链表类，封装了单向链表的各种操作
*/
class MyLinkedList{
   private int maxSize; //数组长度
   private int data[]; //数据域
   private int next[]; //指针域
   private int head=-1; //链表的头指针
   public MyLinkedList(int maxSize){
     this.maxSize=maxSize;
     data=new int[maxSize];
     next=new int[maxSize];
     for(int i=0;i<maxSize;i++) next[i]=-2;
   }
   private int getFreePos(){
     for(int i=0;i<maxSize;i++){
       if (next[i]==-2) return i;
     }
     return -1;
   }
   public void insert(int value){
     int freePos=getFreePos(); //得到空闲的（即可用的）数组下标
     if (freePos==-1){  //判断数组空间是否用完
       System.out.println("存储空间已满，不能插入！");
       return;
     }
     data[freePos]=value; //创建新节点
     next[freePos]=-1;
     if(head==-1){ //如果链表为空，则将新节点放在第一个位置
       head=freePos; //头指针指向第一个节点
       return;
     }
     if(value<data[head]){ //新节点插入头位置
       next[freePos]=head; //新节点指向原来的头节点
       head=freePos;  //这时，新节点变成头节点，所以头指针指向新的头节点
       return;
     }
     int p=head;
     while(next[p]!=-1){  //新节点插入中间位置，即p位置之后
       if(data[p]<=value &&data[next[p]]>value){
         next[freePos]=next[p]; //新节点指向p的下一个节点
         next[p]=freePos;  //p指向的节点的指针指向新节点
         return;
       }
       p=next[p];//p指针向下移，指向下一个节点
     }
     next[p]=freePos;//新节点插入尾位置
   }
   public void delete(int value){
     if(head==-1){//如果是空链表，这不能删除
       System.out.println("车厢为空，不能删除！");
       return;
     }
     int p=head;
     if(data[p]==value){//删除头节点
         p=head; //p指向原来的头节点
         head=next[head];//head指向新的节点，即第二个节点
         data[p]=0;  //释放p所指向的节点
         next[p]=-2;  //释放p所指向的节点
         return;
       }
       p=head;
       int q=p;
       while (p!=-1){  // 删除非头节点
         if(data[p]==value){//查找删除值的节点位置
           next[q]=next[p]; //p的上一个节点指向p的下一个节点，即删除p的节点
           data[p]=0; //释放p所指向的节点
           next[p]=-2;//释放p所指向的节点
           return;
         }
         q=p; //q指向当前节点，p指向下一个节点，这样q就指向p的前一个节点
         p=next[p];
       }
   }
   public void update(int oldValue,int newValue){
    if(head==-1){ //如果是空链表，则不能修改
     System.out.println("车厢为空，不能修改！");
     return;
    }
    int p=head;
    int q=p;
    while (p!=-1){ //遍历数组
      if(data[p]==oldValue){  //查找修改的节点位置
        data[p]=newValue; //查找修改值的位置，找到后赋新值
        next[q]=next[p]; //p的上一个节点指向p的下一个节点，相当于删除p指向的节点
        insert(data[p]); //将修改的节点重新插入，以使其保持有序
        return;
      }
      q=p;  //q指向当前节点，p指向下一个节点，这样q就指向p的前一个节点
      p=next[p];
    }
   }
   public void select(int value){
    if(head==-1){ //如果是空链表，则不能修改
     System.out.println("车厢为空，不能查询！");
     return;
    }
    int p=head;
    while (p!=-1){ //遍历链表，进行查询
      if(data[p]==value){ 
        System.out.println("要找的节点在"+p+"的位置上！");
        return;       
      }
      p=next[p];
   }
   System.out.println("火车没有要查的车厢!");
  }
  public void print(){
    if(head==-1){ //链表为空，不能打印
     System.out.println("车厢空！");
     return;
    }
    System.out.print("车厢的值为：");
   int p=head;
   while (p!=-1){
    System.out.print("车厢"+data[p]+"-->");
    p=next[p];
   }
  System.out.println("结束");
  }
} //MyLinkeList