线性表的Java实现--链式存储（单向链表）

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。

链式存储结构的线性表将采用一组任意的存储单元存放线性表中的数据元素。由于不需要按顺序存储，链表在插入、删除数据元素时比顺序存储要快，但是在查找一个节点时则要比顺序存储要慢。

使用链式存储可以克服顺序线性表需要预先知道数据大小的缺点，链表结构可以充分利用内存空间，实现灵活的内存动态管理。但是链式存储失去了数组随机存取的特点，同时增加了节点的指针域，空间开销较大。

下图就是最简单最一般的单向链表：

新增节点：

将值为element的新节点插入到第index的位置上。

首先要先找到索引为index-1的节点，然后生成一个数据为element的新节点newNode，并令index-1处节点的next指向新节点，新节点的next指向原来index处的节点。

删除节点：

删除第index个节点，第index节点是由index-1出的节点引用的，因此删除index的节点要先获取index-1处的节点，然后让index-1出节点的next引用到原index+1处的节点，并释放index处节点即可。

单向链表的Java实现

下面的程序分别实现了线性表的初始化、获取线性表长度、获取指定索引处元素、根据值查找、插入、删除、清空等操作。

package com.liuhao.algorithm;

public class LinkList<T> {

	// 定义一个内部类Node，代表链表的节点
	private class Node {

		private T data;// 保存数据
		private Node next;// 指向下个节点的引用

		// 无参构造器
		public Node() {
		}

		// 初始化全部属性的构造器
		public Node(T data, Node next) {
			this.data = http://www.mamicode.com/data;> 
测试代码
package com.liuhao.test;

import org.junit.Test;

import com.liuhao.algorithm.LinkList;

public class LinkListTest {

	@Test
	public void test() {

		// 测试构造函数
		LinkList<String> list = new LinkList("好");
		System.out.println(list);

		// 测试添加元素
		list.add("ni");
		list.add("没");
		System.out.println(list);

		// 在头部添加
		list.addAtHead("五月");
		System.out.println(list);

		// 在指定位置添加
		list.insert("摩卡", 2);
		System.out.println(list);

		// 获取指定位置处的元素
		System.out.println("第2个元素是（从0开始计数）：" + list.get(2));

		// 返回元素索引
		System.out.println("摩卡在的位置是：" + list.locate("摩卡"));
		System.out.println("moka所在的位置：" + list.locate("moka"));

		// 获取长度
		System.out.println("当前线性表的长度：" + list.length());

		// 判断是否为空
		System.out.println(list.isEmpty());

		// 删除最后一个元素
		list.remove();
		System.out.println("调用remove()后：" + list);

		// 获取长度
		System.out.println("当前线性表的长度：" + list.length());

		// 删除指定位置处元素
		list.delete(3);
		System.out.println("删除第4个元素后：" + list);

		// 获取长度
		System.out.println("当前线性表的长度：" + list.length());

		// 清空
		list.clear();
		System.out.println(list);

		// 判断是否为空
		System.out.println(list.isEmpty());
	}

}
 
代码获取地址：https://github.com/liuhao123/JavaMore.git