1.实现链表的步骤
2.类的实现
/*节点类*/
class Node
{
private String data; //节点保存的数据
private Node next; //下个节点
public Node(String data){
this.data = data;
}
public String getData()
{
return data;
}
public void setData(String data)
{
this.data = data;
}
public Node getNext()
{
return next;
}
public void setNext(String data)
{
this.next = new Node(data);
}
/*Description: 添加节点
*return :
*/
public void addNode(String data)
{
if(getNext()!=null)
{
this.next.addNode(data);
}
else
{
this.setNext(data);
}
}
/*Description: 获取节点数据
*return :
*/
public String getData(int index)
{
String ret =null ;
if(index == 0) //如果递归到0,则返回当前数据
{
ret=data;
}
else //否则继续递归查找
{
ret=this.next.getData(--index);
}
return ret;
}
/*Description: 递归地查找data位于链表哪个序号
*return : -1(表示未找到)
*/
public int findIndex(String data,int index)
{
if(this.data.equals(data)) //已找到
{
return index;
}
else if (getNext()==null) //未找到
{
return -1;
}
return this.next.findIndex(data,++index);
}
/*Description: 递归地查找data,并删除
*data: 要找的data
*PreNode: 上个节点,如果为null则当前位于表头
*index: 表示当前位于链表哪个序号
*return : -1(表示未找到) 0~(len-1) (表示data位于链表哪个序号)
*/
public int delData(String data,Node PreNode,int index)
{
int ret = -1;
if(this.data.equals(data)) //删除
{
PreNode.next = this.next;
return index;
}
else if (getNext()==null) //未找到
{
return ret;
}
return this.next.delData(data,this,++index);
}
}
/*链表类*/
class LinkList
{
private Node next; //负责管理的节点
private int len; //统计节点长度
public LinkList(String data)
{
next = new Node(data);
len =1;
}
/*Description: 添加一个节点数据
*return :
*/
public void addData(String data)
{
this.next.addNode(data);
len++;
}
/*Description: 删除一个节点数据
*return : -1(未找到要删除的数据) 0~(len-1) (表示data位于链表哪个序号)
*/
public int delData(String data)
{
int ret=-1;
if(len>=0) //链表有数据
{
if(this.next.getData().equals(data)) //删除表头需要特殊处理
{
this.next = this.next.getNext();
ret = 0;
}
else
ret = next.delData(data,this.next,1);
}
if(ret!= -1) //已删除
{
len--;
}
return ret;
}
/*Description: 根据index找到对应的节点数据
*return : 返回节点数据
*/
public String getNodeData(int index)
{
String ret=null;
if(index>=0 && index<(len))
{
ret = next.getData(index);
}
return ret;
}
/*Description: 根据data查找节点Node位于链表哪个序号
*return : -1(表示未找到) 0~(len-1) (表示data位于链表哪个序号)
*/
public int findNodeIndex(String data)
{
int ret=-1;
if(len>=0) //链表有数据
{
ret = next.findIndex(data,0); //从序号0开始找
}
return ret;
}
/*Description: 将链表中所有的节点数据转为数组
*return :
*/
public String[] toArrays()
{
Node tmp=this.next;
String[] arr = new String[len];
for(int i=0; i< len; i++)
{
arr[i] = tmp.getData();
tmp = tmp.getNext();
}
return arr;
}
public int length()
{
return len;
}
}
3.测试代码
public class Test{
public static void main(String args[]){
LinkList list = new LinkList("小A");
//添加节点数据
list.addData("小B");
list.addData("小C");
list.addData("小D");
list.addData("小E");
//打印节点数据
System.out.println("print Node data:");
for(int i=0;i<list.length();i++)
{
System.out.println(list.getNodeData(i));
}
System.out.println("---------------------");
//查找节点数据的序号
System.out.println("小A的index位于:"+list.findNodeIndex("小A"));
System.out.println("小D的index位于:"+list.findNodeIndex("小D"));
System.out.println("小F的index位于:"+list.findNodeIndex("小F")); //返回-1,表示未找到
//删除节点数据
System.out.println("删除小A,并打印小A之前的位置:"+list.delData("小A"));
System.out.println("删除小E,并打印小E之前的位置:"+list.delData("小E"));
//通过数组打印数据
System.out.println("\r\nprint Node data by toArrays() :");
String[] arr=list.toArrays();
for(int i=0;i<arr.length;i++)
{
System.out.println(arr[i]);
}
System.out.println("---------------------");
}
}
运行打印:
PS:这样写,只是简单的实现某个数据类型的链表.在后面我们学习了JAVA-Object类,由于Object类是所有类的超类,所以,我们可以来实现满足所有类型的链表
接下来开始重新修改链表.
4.修改链表-将节点数据改为Object类型
class Node
{
private Object data; //节点保存的数据
private Node next; //下个节点
public Node(Object data){
this.data = data;
}
public Object getData() //获取数据
{
return data;
}
public void setData(Object data)
{
this.data = data;
}
public Node getNext()
{
return next;
}
public void setNext(Object data)
{
this.next = new Node(data);
}
/*Description: 添加节点
*return :
*/
public void addNode(Object data)
{
if(getNext()!=null)
{
this.next.addNode(data);
}
else
{
this.setNext(data);
}
}
/*Description: 获取节点数据
*return :
*/
public Object getData(int index)
{
Object ret =null ;
if(index == 0) //如果递归到0,则返回当前数据
{
ret=data;
}
else //否则继续递归查找
{
ret=this.next.getData(--index);
}
return ret;
}
/*Description: 递归地查找data位于链表哪个序号
*return : -1(表示未找到)
*/
public int findIndex(Object data,int index)
{
if(this.data.equals(data)) //已找到
{
return index;
}
else if (getNext()==null) //未找到
{
return -1;
}
return this.next.findIndex(data,++index);
}
/*Description: 递归地查找data,并删除
*data: 要找的data
*PreNode: 上个节点,如果为null则当前位于表头
*index: 表示当前位于链表哪个序号
*return : -1(表示未找到) 0~(len-1) (表示data位于链表哪个序号)
*/
public int delData(Object data,Node PreNode,int index)
{
int ret = -1;
if(this.data.equals(data)) //删除
{
PreNode.next = this.next;
return index;
}
else if (getNext()==null) //未找到
{
return ret;
}
return this.next.delData(data,this,++index);
}
}
/*链表类*/
class LinkList
{
private Node next; //负责管理的节点
private int len; //统计节点长度
public LinkList(Object data)
{
next = new Node(data);
len =1;
}
/*Description: 添加一个节点数据
*return :
*/
public void addData(Object data)
{
this.next.addNode(data);
len++;
}
/*Description: 删除一个节点数据
*return : -1(未找到要删除的数据) 0~(len-1) (表示data位于链表哪个序号)
*/
public int delData(Object data)
{
int ret=-1;
if(len>=0) //链表有数据
{
if(this.next.getData().equals(data)) //删除表头需要特殊处理
{
this.next = this.next.getNext();
ret = 0;
}
else
ret = next.delData(data,this.next,1);
}
if(ret!= -1) //已删除
{
len--;
}
return ret;
}
/*Description: 根据index找到对应的节点数据
*return : 返回节点数据
*/
public Object getNodeData(int index)
{
Object ret=null;
if(index>=0 && index<(len))
{
ret = next.getData(index);
}
return ret;
}
/*Description: 根据data查找节点Node位于链表哪个序号
*return : -1(表示未找到) 0~(len-1) (表示data位于链表哪个序号)
*/
public int findNodeIndex(Object data)
{
int ret=-1;
if(len>=0) //链表有数据
{
ret = next.findIndex(data,0); //从序号0开始找
}
return ret;
}
/*Description: 将链表中所有的节点数据转为数组
*return :
*/
public String[] toArrays()
{
Node tmp=this.next;
String[] arr = new String[len];
for(int i=0; i< len; i++)
{
arr[i] = tmp.getData().toString();
tmp = tmp.getNext();
}
return arr;
}
public int length()
{
return len;
}
}
5.测试修改后的链表
接下来,我们便来写一个student学生类,然后通过我们修改后的链表来保存该类
5.1 student学生类如下所示:
/*学生类*/
class Student
{
String name; //名字
String clas; //班级
int score; //成绩
Student(String name,String clas,int score)
{
this.name = name;
this.clas = clas;
this.score = score;
}
/*覆写Object类的equals方法*/
public boolean equals(Object obj)
{
if(obj == null) //地址为null
return false;
if(obj instanceof Student == false) //非本类
{
System.out.println("ERR");
return false;
}
if(this == obj) //地址相同
return true;
Student st = (Student)obj;
if(this.name.equals(st.name) &&
this.clas.equals(st.clas) &&
this.score == st.score )
return true;
return false;
}
/*覆写Object类的toString方法*/
public String toString()
{
return "姓名:"+name+" 班级:"+clas+" 成绩:"+score;
}
}
5.2 student学生类的测试代码如下所示:
Student xiaoA = new Student("小A","初1-6班",77);
Student xiaoB = new Student("小B","初2-1班",99);
Student xiaoC = new Student("小C","初1-2班",66);
Student xiaoD = new Student("小D","初2-2班",49);
Student xiaoE = new Student("小E","初2-3班",88);
Student xiaoF = new Student("小F","初2-3班",89);
//创建链表,并添加 xiaoA 链表节点
LinkList list = new LinkList(xiaoA);
//继续添加节点数据
list.addData(xiaoB);
list.addData(xiaoC);
list.addData(xiaoD);
list.addData(xiaoE);
//打印节点数据
System.out.println("print Node data:");
for(int i=0;i<list.length();i++)
{
System.out.println(list.getNodeData(i));
}
System.out.println("---------------------");
//查找节点数据的序号
System.out.println("小A的index位于:"+list.findNodeIndex(xiaoA));
System.out.println("小D的index位于:"+list.findNodeIndex(xiaoD));
System.out.println("小F的index位于:"+list.findNodeIndex(xiaoF)); //返回-1,表示未找到
//删除节点数据
System.out.println("删除小A,并打印小A之前的位置:"+list.delData(xiaoA));
System.out.println("删除小E,并打印小E之前的位置:"+list.delData(xiaoE));
//通过数组打印数据
System.out.println("\r\nprint Node data by toArrays() :");
String[] arr=list.toArrays();
for(int i=0;i<arr.length;i++)
{
System.out.println(arr[i]);
}
System.out.println("---------------------");
5.3 打印如下: