线性表的链式存储结构（java版）

在前面，我们已经讲了线性表的顺序存储结构（java版） ，我们也知道了他的代码实现，在了解之后，我们很容易就能够发现他有一个最大的缺点，就是插入和删除需要移动大量的元素，这显然是很耗费时间的，于是，为了解决这个问题，就出现了链式存储结构。

 

我学习的时候是看程杰的《大话数据结构》的，同时结合我们的经典教材清华出版社的《数据结构》，但是在学习过程中，我不小心把“插入到第i个位置之后”理解成了“插入到第i个位置”，所以我后面的程序跟书上的范例有些不一样，但是万变不离其宗，它运用的始终是我们的数据结构——线性表的链式存储结构。

 

由于理解错了课本的一些意思，所以代码显得更复杂了一点点，好吧，言归正传，继续讲我们代码是如何实现的。

 

第一步，定义一个接口，其实这个接口跟前面顺序存储结构的接口定义是一样的，后面我只是改了下名字和重新更换了包名而已，但这不影响我们的代码：

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();
	}
}

 

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

产生的链表长度为 ：23
5 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

获取位置为 ：12
5 19 18 12 6 12 15 19 16 21 16 5 获取到的元素为 : 5