线性表的链式存储结构（java版）
package com.stucture.list;/** * 线性表顺序存储结构的接口 * 指的是用一段地址连续的存储单元一次存储线性表的数据元素 * @ClassName: ISqList * @author 小学徒 * @date 2013-2-27 */public interface IList<T> {/** * 获得元素 * @param loc 需要获得的第loc个元素 * @return */public T getElem(int loc);/** * 插入元素 * @param loc 元素的插入位置 * @param t 需要插入的元素 * @return 是否成功插入 */public boolean insertElem(int loc, T t);/** * 删除元素 * @param i 需要删除元素的位置 * @return */public T deleteElem(int i);}

?

第二步，定义我们的节点类：

package com.stucture.list.linkList;/** * 链表中的结点 * @ClassName: Node  * @author 小学徒 * @date 2013-2-27 */public class Node<T> {private T data;       //需要存储的数据信息private Node<T> next; //后继结点 public T getData() {return data;}public void setData(T data) {this.data = data;}public Node<T> getNext() {return next;}public void setNext(Node<T> next) {this.next = next;}}

?

第三步，定义我们的链表及其基本操作，代码如下：

package com.stucture.list.linkList;import com.stucture.list.IList;/** * 单链表 * @ClassName: LinkList  * @author 小学徒 * @date 2013-2-27 */public class LinkList<T> implements IList<T>{private Node<T> head;//链表的结点private int length;//链表的长度public LinkList(Node<T> head) {this.head = head;}//获取元素public T getElem(int loc) {int j = 1;//计数器Node<T> n = head;//指向第一个结点while(n != null) {//n不为空时，循环继续寻找第loc个结点if(j == loc) {//找到第一个元素时返回return n.getData();}n = n.getNext();j++;}return null;}//插入元素public boolean insertElem(int loc, T t) {if(length + 1 < loc) {System.out.println("非法插入");return false;}if(head == null && loc == 1) {//当第一次插入的时候head = new Node<T>();//第一次使用，必须创建对象head.setData(t);length++;} else if(head != null && loc == 1) {//但不是第一次插入，但是插入的位置是第一个时Node<T> tempNode = new Node<T>();//生成一个新的结点tempNode.setData(t);tempNode.setNext(head);head = tempNode;//把头换成新插入的结点length++;} else {//当不是第一次插入并且插入的不是第一个时Node<T> n = this.head;int j = 1;//计数器while(n != null && j < loc - 1) {n = n.getNext();j++;}Node<T> tempNode = new Node<T>();//生成一个新的结点tempNode.setData(t);tempNode.setNext(n.getNext());//将n的后继结点赋值给新的结点的后继n.setNext(tempNode);length++;}return true;}//删除元素public T deleteElem(int loc) {if(head == null || loc > length) {System.out.println("非法删除");return null;}T old;if(head != null && loc == 1) {old = head.getData();head = head.getNext();} else {Node<T> n = this.head;int j = 1;//计数器while(n != null && j < loc - 1) {n = n.getNext();j++;}old = n.getNext().getData();n.setNext(n.getNext().getNext());}length--;return old;}public Node<T> getHead() {return head;}public void setHead(Node<T> head) {this.head = head;}public int getLength() {return length;}public void setLength(int length) {this.length = length;}}

?

第四步，我们下面就写一个比较完善的代码测试，在下面的代码中，我是通过随机数来生成一些必要的数据来测试的，只要多运行几遍，还是能够测试比较完善的，不过封装的可能有点不太好，如果读者看了以后有什么更好的建议，还希望能够指出，当然因为该链式存储结构和顺序存储结构都是同一个接口的实现，所以测试方法是可以一样的，只是把实现类转换了而已。但是由于时间问题，我就没有去修改了，有兴趣的读者可以自行修改，有问题的可以在此留言共同讨论共同进步，我有空的时候也会更改并上传到博客的，下面继续代码：

package com.stucture.list.linkList;import java.util.Random;public class LinkListTest {final int MAX = 25;Random r = new Random();LinkList<Integer> linkList;public LinkListTest() {initSeqList();}//创建一个线性表顺序存储结构public void initSeqList() {linkList = new LinkList<Integer>(null);int length = Math.abs(r.nextInt(MAX));//使用Random随机产生一个25左右的值,使用Math.abs()函数来取绝对值System.out.println("产生的链表长度为 ：" + length);for (int i = 1; i <= length; i++) {//为生成的链表赋值，同时也测试了插入值的方法int j =r.nextInt(MAX);System.out.print(j + " ");if(!linkList.insertElem(i, j)) {System.exit(0);}}System.out.println("\n原始链表是 ：");display(linkList);}//测试删除方法public void deleteElem() {int i = r.nextInt(MAX);System.out.println("\n\n删除的位置是：" + i);Integer deleteNumber = linkList.deleteElem(i);if( deleteNumber == null) {System.exit(0);} else {System.out.println("删除的元素是 ： " + deleteNumber);System.out.println("删除元素后链表是 ：");display(linkList);}}//测试随机插入方法public void insertByRandom() {int i = r.nextInt(MAX);System.out.println("\n\n随机插入位置是 ：" + i);int elem = r.nextInt(MAX);System.out.println("随机插入数据是 ：" + elem);linkList.insertElem(i, elem);System.out.println("随机插入数据后链表是 ：");display(linkList);}//数据展示public  void display(LinkList<Integer> linkList) {Node<Integer> node = linkList.getHead();while(node != null) {System.out.print(node.getData() + " ");node = node.getNext();}System.out.println("链表的长度为 ：" + linkList.getLength());}//获取元素public void getElem() {int i = r.nextInt(MAX);System.out.println("\n获取位置为 ：" + i);System.out.println("获取到的元素为 : " + linkList.getElem(i));}public static void main(String[] args) {LinkListTest s = new LinkListTest();s.insertByRandom();s.deleteElem();s.getElem();}}

?

?运行结果同样我不一一把各种结果列出啦，读者可以自己运行多几遍来进行学习：

产生的链表长度为 ：235 19 18 12 6 12 15 19 16 21 13 16 5 4 18 9 9 18 17 13 16 6 17 原始链表是 ：5 19 18 12 6 12 15 19 16 21 13 16 5 4 18 9 9 18 17 13 16 6 17 链表的长度为 ：23随机插入位置是 ：24随机插入数据是 ：0随机插入数据后链表是 ：5 19 18 12 6 12 15 19 16 21 13 16 5 4 18 9 9 18 17 13 16 6 17 0 链表的长度为 ：24删除的位置是：11删除的元素是 ： 13删除元素后链表是 ：5 19 18 12 6 12 15 19 16 21 16 5 4 18 9 9 18 17 13 16 6 17 0 链表的长度为 ：23获取位置为 ：125 19 18 12 6 12 15 19 16 21 16 5 获取到的元素为 : 5

?