-
单链表是用一组任意的存储单元存放线性表的元素，这组存储单元可以连续也可以不连续，甚至可以零散分布在内存中的任意位置。为了能正确表示元素之间的逻辑关系，每个存储单元在存储数据元素的同时，还必须存储其后继元素所在的地址信息，这个地址信息称为指针，这两部门组成了数据元素的存储映像，称为结点(node)，结点结构如图
data是数据域，用来存放数据元素；next是指针域(也成链域)，用来存放该结点的后续结点的地址。
单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起，由于每个结点只有一个指针域，故称为单链表。
Java 语言的单链表数据结构
public class Node {
T data;
Node next;
}
单链表中每个结点的存储地址存放在其前驱结点的next域中，而第一个元素无前驱，所以设头指针指向第一个元素所在结点(称为开始结点)，整个单链表的存取必须从头指针开始进行，因而头指针具有标识一个单链表的作用
单链表由于最后一个元素无后继，故最后一个元素所在结点的指针域为空，也称为尾标志.
-
线性表的存储状态:
从单链表的存储示意图可以看到，除了开始结点外，其他每个结点的存储地址都存在其前驱结点的next域中，而开始结点是由头指针指示的。这个特例需要在单链表实现时特殊处理，增加了程序的复杂性和bug的机会。因此，通常在单链表的开始结点之前附设一个类型相同的结点，称为头结点
单链表的基本思想就是用指针表示结点之间的逻辑关系。
设指针p指向某个Node类型的结点，则该结点用p（由于java中引用对象就是指针引用，在c语言中*p表示）来表示，p为结点变量，为了叙述方便，将“指针p”所指结点简称为“结点p”
在单链表中，结点p由两个域组成：存放数据元素的部分和存放后续节点地址的指针部分，分别用p->data 和p->next来表识，且它们各自有自己的值：p->data的值是一个数据元素, p->next的值是一个指针。
代码示例
/**
* @author chunyuliu
*/
public class LinkList {
/** 头指针 */
private Node first;
public class Node {
int data;
Node next = null;
public Node(int data) {
this.data = data;
}
}
// /**
// * 头插法
// * 建立有N个元素的单链表
// * @param array
// */
// public LinkList(Integer[] array) {
// // 设一个类型相同的结点，称为头结点
// first = new Node(0);
// first.next = null;
// // 头插法
// for (int d : array) {
// Node s = new Node(d);
// // 为每个数组元素建立一个结点
// s.next = first.next;
// // 将节点s插入到头结点之后
// first.next = s;
// }
// }
/**
* 尾插法
* 建立有N个元素的单链表
* @param array
*/
public LinkList(Integer[] array) {
// 生成头结点
first = new Node(0);
// 尾指针初始化
Node r = first;
for (int d : array) {
// 为每个数组元素建立一个结点
Node s = new Node(d);
// 将结点s插入到终端结点之后
r.next = s;
r = s;
}
// 单链表建立完毕，将终端节点的指针域置空
r.next = null;
}
/**
* 求链表长度
* @return
*/
public int length() {
Node p = first.next;
int count = 0;
while (p != null) {
p = p.next;
count++;
}
return count;
}
/**
* 按位查找。在单链表中查找第i个节点的元素值
* @param i
* @return
*/
public int get(int i) throws Exception {
Node p = first.next;
int count = 1;
while (p != null && count < i) {
// 工作指针后移
p = p.next;
count++;
}
if (p == null) {
throw new Exception(String.valueOf(count));
}
return p.data;
}
/**
* 按之查找。在单链表中查找值为x的元素序号
* @param x
* @return
*/
public int locate(int x) {
Node p = first.next;
int count = 1;
while (p != null) {
if (p.data == x) {
// 查找成功，结束函数并返回序号
return count;
}
p = p.next;
count++;
}
// 退出循环表明查找失败
return 0;
}
/**
* 插入操作，在第i个位置插入元素值为x的节点
* @param i
* @param x
*/
public void insert(int i, int x) throws Exception {
Node p = first;
int count = 0;
// 查找第i-1个节点
while (p != null && count<i-1) {
// 工作指针p后移
p = p.next;
count++;
}
if (p == null) {
// 未找到第i-1 个节点
throw new Exception(String.valueOf(i));
}
// 新节点, x为数据域
Node s = new Node(x);
// 将节点s插入到节点p之后
s.next = p.next;
p.next = s;
}
/**
* 删除操作，在单链表中删除第i个节点
* @param i
* @return
*/
public int delete(int i) throws Exception {
// 工作指针p指向头节点
Node p = first;
int count = 0;
// 查找第i-1个节点
while (p != null && count<i-1) {
p = p.next;
count++;
}
// 结点p不存在或p的后续节点不存在
if (p == null || p.next == null) {
throw new Exception(String.valueOf(i));
}
// 暂存被删除节点
Node q = p.next;
int x = q.data;
// 摘链
p.next = q.next;
return x;
}
/**
* 遍历操作，按序号依次输出各元素
*/
public void printList() {
Node p = first.next;
while (p != null) {
System.out.println(p.data);
p = p.next;
}
}
}
测试用例
/**
* @author chunyuliu
*/
public class LinkListTest {
@Test
public void linkListTest() {
Integer[] arrayList = new Integer[]{1, 2, 3, 4};
// 生成一个单链表
LinkList linkList = new LinkList(arrayList);
// 打印链表
linkList.printList();
// 获取链表长度
System.out.println("length: " + linkList.length());
// 按表位查找
try {
System.out.println("get index 2: " + linkList.get(2));
} catch (Exception e) {
e.printStackTrace();
}
// 按值查找
System.out.println("locate value 4: " + linkList.locate(4));
// 插入, 在第3个节点插入值0
try {
System.out.println("insert before");
linkList.printList();
linkList.insert(3, 0);
System.out.println("insert after");
linkList.printList();
System.out.println("insert done");
} catch (Exception e) {
e.printStackTrace();
}
// 删除结点
try {
System.out.println("delete before");
linkList.printList();
System.out.println("delete index 3: " + linkList.delete(3));
System.out.println("delete after");
linkList.printList();
System.out.println("delete done");
} catch (Exception e) {
e.printStackTrace();
}
}
}
