数据结构——Java实现单链表

一、分析

  单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点由元素和指针构成。在Java中,我们可以将单链表定义成一个类,单链表的基本操作即是类的方法,而结点就是一个个实例化的对象,每个对象中都有“元素值”和“下一结点地址”两个属性。在“下一结点地址”属性中存储的是下一个对象的引用,这样,一个个对象连在一起就成为了单链表。

  单链表有以下基本操作:

    1、初始化单链表

    2、销毁单链表

    3、清空单链表

    4、检测单链表是否为空

    5、返回单链表的元素个数

    6、返回单链表中指定位置元素的值

    7、返回单链表中第一个与指定值相同的元素的位置

    8、返回指定元素的直接前驱

    9、返回指定元素的直接后继

    10、向指定位置插入元素

    11、删除指定位置的元素

    12、遍历单链表

  为了方便对单链表进行操作,我们还需要引入一个头结点,头结点中不存储元素值,只存储单链表第一个结点的地址。初始化单链表即创建头结点,而销毁单链表即销毁头结点。

二、实现

1、定义类属性和构造函数

 class InitList{

     private int [] data = new int[1];   //用来存储元素值,之所以用数组而不用整型,是为了用null来表示头结点

     private InitList nextList;       //下一结点地址

     public InitList() {           //创建头结点的构造函数
this.data = null;
this.nextList = null;
} public InitList(int data) {      //创建普通结点的构造函数
this.data[0] = data;
this.nextList = null;
}
}

2、清空单链表

 public void clearList() {
this.nextList = null;         //将头结点的下一结点地址(即单链表的第一个结点的地址)置空,则单链表会因缺少引用而被jvm回收,实现清空
}

3、检测单链表是否为空

 public boolean listEmpty() {
if(this.nextList == null) {      //通过判断头结点的下一结点地址是否为空,即可判断单链表是否为空
return true;
}
return false;
}

4、返回单链表的元素个数

 public int listLength() {

     InitList theList = this.nextList;        //获取头结点的下一结点地址
int i = 0;                //计数器初始化 for (i = 0; theList != null; i++) {      //循环判断结点地址是否为空,如果不为空,则表明存在结点,计数器i加一;如果为空,则表明已到达单链表尾部,退出循环
theList = theList.nextList;       //取下一结点进行判断
}
return i;                     //返回计数器的值
}

5、返回单链表中指定位置元素的值

 public int [] getElem(int site) {

     if(site < 1) {                      //判断输入的位置是否合法
return null;
} InitList theList = this;         //得到头结点的地址 for (int i = 0; i < site; i++) {     //循环读取结点,直到指定的位置
theList = theList.nextList;      //获取下一结点的地址
if(theList == null) {          //如果下一结点地址为空,则表明已经到达单链表末尾,指定的位置超出了单链表的长度
return null;              //未取到元素,返回null
}
}
return theList.data;            //返回指定位置元素值
}

6、返回单链表中第一个与指定值相同的元素的位置

 public int locateElem(int value) {

     InitList theList = this.nextList;

     for(int i = 1; theList != null; i++) {     //如果取得的结点不为空,执行循环
if(theList.data[0] == value) {       //比较结点值与给定的值是否相等
return i;                //相等返回结点位置
}
theList = theList.nextList;        //取下一结点地址
} return 0;                     //未找到则返回零
}

7、返回指定元素的直接前驱

 public int [] priorElem(int value) {

     InitList theList = this.nextList;

     if(theList == null) {                    //如果头结点的下一结点为空,则表明单链表为空,返回null
return null;
} InitList theNextList = this.nextList.nextList;    //获取单链表的第二个结点
int [] ret = new int[this.listLength()];        //创建一个与单链表长度相同的数组,用来存储找到的直接前驱的值
int i = 1;                          //计数器 while (theNextList != null) {               //因为单链表的第一个结点没有直接前驱,因此从第二个结点开始循环
if(theNextList.data[0] == value) {        //如果与给定值相等,则取得其前驱,计数器加一
ret[i] = theList.data[0];
i++;
}
theList = theNextList;               //取下一地址,准备下一循环
theNextList = theNextList.nextList;
} if(i == 1) {                       //i为1表明未取到直接前驱
return null;
} ret[0] = i - 1;                     //将计数器的值存入数组第0位
return ret;
}

8、返回指定元素的直接后继

 public int [] nextElem(int value) {              //与获取直接前驱类似,这里不再赘述

     InitList theList = this.nextList;

     if(theList == null) {
return null;
} InitList theNextList = this.nextList.nextList;
int [] ret = new int[this.listLength()];
int i = 1; while (theNextList != null) {
if(theList.data[0] == value) {
ret[i] = theNextList.data[0];
i++;
}
theList = theNextList;
theNextList = theNextList.nextList;
} if(i == 1) {
return null;
} ret[0] = i - 1;
return ret;
}

9、向指定位置插入元素

 public boolean listInsert(int site,int value) {

     if(site < 1) {                        //判断指定位置是否合法
return false;
}
6
7   InitList list = new InitList(value);
InitList theNextList = this;
InitList theList = null; for(int i = 0; i < site; i++) {             //循环读取到指定位置
theList = theNextList;
if(theList == null) {                //如果为空,表示已到单链表末尾,返回false
return false;
}
theNextList = theNextList.nextList;
} list.nextList = theNextList;                //将新结点插入指定位置中
theList.nextList = list;
return true;
}

10、删除指定位置的元素

 public boolean listDelete(int site) {

     InitList theList = this;
InitList theNextList = this.nextList; if(site < 1 || theNextList == null) {       //判断指定位置是否合法和单链表是否为空
return false;
}else if(site == 1) {                  //如果要删除的是第一个结点,则直接删除
theList.nextList = theNextList.nextList;
return true;
} for(int i = 1; i < site; i++) {            //循环读取到指定位置
theNextList = theNextList.nextList;
if(theNextList == null) {
return false;
}
theList = theList.nextList;
} theList.nextList = theNextList.nextList;      //删除指定位置的结点
return true;
}

11、遍历单链表

 public String traverseList() {          //这里通过输出单链表来表示遍历

     InitList theList = this.nextList;
String s = "";                //用来存储单链表的值 while(theList != null) {           //循环获取结点值
s += theList.data[0] + "、";
theList = theList.nextList;
} if(s.length() == 0) {            //如未获取到值,直接返回s
return s;
} return s.substring(0,s.length() - 1);  //去除最后的顿号后返回
}

三、小结

  以上就是单链表用Java的实现,由于只定义了整数的数组,因此只能操作整数数据,但单链表的基本思想都已实现。

四、纠正

  隔了一段时间又回来看代码,猛地发现这段代码其实还不够完善。(⊙x⊙;)

  将单链表的基本操作定义成了InitList类的方法,实例化结点时,会使每个结点都拥有这些方法,然而其实只有头结点需要这些方法,其他结点都不需要。

  因此可以将InitList类定义成头节点类,而其他节点定义成头节点的内部类,这样,就只有头节点可以操作其他节点。

  由于要修改的地方太多,这里我就不修改了,放在这里提醒自己。(就是因为懒……(><))

上一篇:【学习总结】Git学习-参考廖雪峰老师教程六-分支管理


下一篇:Android 开发之错误整理 [2014-04-28 09:22:28 - XXXX] Unable to resolve target 'android-18'