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
