Question

求java 单链表基本操作的实现

[问题描述]
本演示程序用JAVA编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。
① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数类型。
② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。
③ 程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作。
④ 测试数据：
A． 插入操作中依次输入11，12，13，14，15，16，生成一个单链表
B． 查找操作中依次输入12，15，22返回这3个元素在单链表中的位置
C． 删除操作中依次输入2，5，删除位于2和5的元素
[基本要求]用链式存储结构实现存储
[实现提示]链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地寻找，比较给定键值，确定查找位置，再进行相关操作。

谢谢谢谢！！！通过的加分！！

Answer 1

/*
注意：链表的结点数量用size表示，结点的位置为0~size-1
*/
import java.util.Scanner;

public class Test7 {
public static void main(String[] args) {
try{
LinkList list = new LinkList();
Integer value;
int pos = 0;
Scanner input = new Scanner(System.in);
String choice = null;

//测试A
while(true){
System.out.print("请输入待插入结点的值(x或X退出)：");
choice = input.next();
if(choice.toUpperCase().equals("X")){
break;
}
value = Integer.valueOf(choice);
if(list.addAt(pos, value) == true){
System.out.println("插入值为 " + value + " 的结点到当前链表成功!");
pos++;
}
else{
System.out.println("插入结点失败!");
}
}

System.out.print("当前链表所有结点：");
list.listAll();

//测试B
while(true){
System.out.print("请输入待查询结点的值(x或X退出)：");
choice = input.next();
if(choice.toUpperCase().equals("X")){
break;
}
value = Integer.valueOf(choice);
pos = list.findByValue(value);
if(pos == -1){
System.out.println("当前链表中不存在值为 " + value + " 的结点");
}
else{
System.out.println("值为 " + value + " 的结点在当前链表中的位置为 " + pos);
}
}

//测试C
while(true){
System.out.print("请输入待删除结点的位置[0~" + (list.getSize()-1) + "](x或X退出)：");
choice = input.next();
if(choice.toUpperCase().equals("X")){
break;
}
pos = Integer.valueOf(choice);
if(list.removeAt(pos) == true){
System.out.println("删除当前链表中 " + pos + " 位置的结点成功!");
}
else{
System.out.println("删除结点失败!");
}
}

System.out.print("当前链表所有结点：");
list.listAll();
}
catch(Exception e){
e.printStackTrace();
}
}
}

/**
* 链表结点类
*/
class Node{
private Object data; //链表结点的数据域
private Node next; //链表结点的指针域，指向直接后继结点

public Node(){
data = null;
next = null;
}

public Node(Object data, Node next){
this.data = data;
this.next = next;
}

public Object getData(){
return this.data;
}

public void setData(Object data){
this.data = data;
}

public Node getNext(){
return this.next;
}

public void setNext(Node next){
this.next = next;
}
}

/**
* 链表类
*/
class LinkList{
private Node head = null; //头结点指针
private int size = 0;

public LinkList(){
head = new Node();
size = 0;
}

//在i位置插入元素elem
public boolean addAt(int i, Object elem) {
if(i < 0 || i > size){
return false;
}

Node pre,curr;
int pos;
for(pre=head; i>0 && pre.getNext()!=null; i--,pre=pre.getNext());
curr = new Node(elem, pre.getNext());
pre.setNext(curr);
size++;
return true;
}

//删除i位置的元素
public boolean removeAt(int i) {
if(i < 0 || i >= size){
return false;
}

Node pre,curr;
for(pre=head; i>0 && pre.getNext()!=null; i--,pre=pre.getNext());
curr = pre.getNext();
pre.setNext(curr.getNext());
size--;
return true;
}

//根据值value查询结点是否存在，若存在返回位置，否则返回-1
public int findByValue(Object value){
Node curr;
int pos;
for(pos=0,curr=head.getNext(); curr!=null; pos++,curr=curr.getNext()){
if(curr.getData().toString().equals(value.toString())){
break;
}
}

if(curr==null){
return -1;
}
return pos;
//return (curr!=null ? pos : -1);
}

public int getSize(){
return size;
}

public boolean isEmpty(){
return (size==0);
}

public void listAll(){
for(Node curr=head.getNext(); curr!=null; curr=curr.getNext()){
System.out.print(curr.getData() + "\t");
}
System.out.println();
}
}