数据结构--单链表的设计与实现
首先了解其定义：
单链表：如果每个结点只设置一个指向其后结点的指针成员，这样的链表称为线性单向链接表，简称单链表。
何为指针成员呢，在链表中每个结点不仅包含有元素本身的信息(称为数据成员)，而且包含有元素之间的逻辑关系的信息。
指针成员：一个结点包含有后续结点的地址信息或者前驱结点的地址信息，称为指针成员。
与C语言当中的指针类似，C语言当中的指针存放的是地址值；但Java中并不存在指针的概念，这里的指针成员存放的是后继结点或者是前驱结点的引用，引用存放的仍为其相对应的地址值。概念不同，功能相同。
了解了单链表的概念之后来看相应的图解：
单链表只有一个头结点，且在初始化头结点时，是不存放数据的，只有一个指向为null的next结点：
对于每个结点head、s、s1……等我没有直接使用方框代替，我的理解是，每一个new出的结点对象，默认包含其对应构造方法内的全部内容，当你想往构造方法找添加内容时，对应的对象所分配的内存空间也更多。这里使用椭圆内嵌方框也是以我自己的理解进行构图。对于我对构造函数的理解，详见上一期，文章内含有我对构造函数的理解及顺序表的实现。
接着再进行了解，单链表个成员之间是如何建立连接的，具体的建立连接的方式有两种：
头插法建表：相应图解为：
图片文字有点小，可以放大看。过程就全在图中喽
相应代码：
//用头插法建立单链表
public void GreatLoneList(Object[] a){
LoneListOne
尾插法建表：相应图解为：
相应代码：
//用尾插法建表
public void GreatLoneListEnd(Object[] a){
LoneListOne
用尾插法更符合我们平常的操作，其代码也更简洁
了解了单链表的实现原理及建表方法后，我们就可以着力将整个单链表的所有基本模块实现喽：
本次实现单链表需要创建3个类，各类具体功能在后讲解 一.编写一个类建立结点结构：
class LoneListOne
头结点初始时是不存放数据的，只有一个空指针成员null。
- 二.编写另一个类，初始化头结点及实现单链表的基本功能(增删改查)：
- 1.创立一个头结点：
//建立头结点
LoneListOne
- 2.头插法的代码实现：
//用头插法建立单链表
public void GreatLoneList(Object[] a){
LoneListOne 3.尾插法的代码实现：
//用尾插法建表
public void GreatLoneListEnd(Object[] a){
LoneListOne
- 4.求单链表的长度：
//求线性表的长度
public int size(){
LoneListOne
- 5.代码实现向单链表中增加元素：
//增：向单链表中末尾增加一个元素
public void Add(Object e){
LoneListOne
- 6.代码实现在单链表中删除元素： 删除元素时，首先需找到其结点所在位置，再改变其指向
1).找结点 //找到序号为i的结点，为删做准备
public LoneListOne
2).删元素
//删：在单链表中删除第i个元素
public void Delete(int i,Object e){
if (i<0 ||i>size()-1) {
throw new IllegalArgumentException("元素i不在有效范围之内！");
}
LoneListOne
- 7.代码实现单链表中元素修改： 找结点，改元素
//改：设置线性表中序号为i的元素为e
public void SetElem(int i,Object e){
if(i<0||i>size()-1){
throw new IllegalArgumentException("元素i不在有效范围之内！");
}
LoneListOne
- 8.代码实现单链表中元素的查找：
//查：寻找序号为i的结点，返回线性表中序号为i的元素
public Object getElem(int i){
LoneListOne
- 9.代码实现返回单链表中所有元素： 原理为将各个结点遍历，将各结点中的data数据赋给字符串
//将单链表中全部元素转换为字符串并返回
public String ToString(){
String ans = "";
LoneListOne 以上代码均在 class LoneListTwo{} 泛型类中实现
在主类中创建LoneListTwo对象调用方法实现其基本功能:
public class LoneList {
public static void main(String[] args) {
Integer[] a={1,2,3,4,5};
LoneListTwo 完整代码如下：
package com.other;
class LoneListOne
结果如下：
这里主要写的是单链表的实现原理，主类中我没有将各方法全部调用，读者可自行复制代码进行尝试。当理解了原理之后，可尝试独立完成创建。
我这里创建的都是泛型类，使用了Object，其实不必这样定义LoneListOne类和LoneListTwo类，同时也可将Object修饰变量替换成相应的包装类。创建包装类好处就是可以指代任意类型，当你不确定使用什么数据类型时。
前面也说了，创建对象并初始化时，会默认拥有对应构造方法内的全部内容。所以第一个类为创建各结点的"形状"，即第一个类创建的对象都是链表中的每个结点，为什么要再创一个LoneListTwo类实现其方法，初始化后的对象可调用本类中的所有成员及成员方法。即第二个类创建的每一个对象都是一个链表。如果在LoneListOne类创建这些结点对象，那么新创立的结点，如s可调用结点head，这肯定是不合理的，这样创建出来的就不是一个链表了，是一个"怪物"。那么为什么要在主类LoneList创建LoneListTwo类对象利用其调用各方法呢，这当然是Java面向对象的特性了。实现结构与表现分离，也可将LoneListTwo类中定义的所有东西放在主类LoneList中。在一个类中实现这些功能。
若觉得内容稍可，请留下你们的
