单链表，用一组地址任意的存储单元去存放线性表中的数据元素。链表中的数据是以结点来表示的。
结点的构成：元素(数据元素的映象) + 指针(指示后继结点存储位置)。
1. 概述
单链表，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的。
结点的构成：元素(数据元素的映象) + 指针(指示后继结点存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
循环链表：它的特点是单链表中最后一个结点的指针域指向第一个节点，整个链表形成一个环。
如下，data 是元素，next 是指针。
private int data; // 节点的值
private ListNode next; // 下一个节点单链表、数组和循环链表的性能对比：
单链表：插入、删除一个节点时间复杂度：O(1)，查询一个节点时间复杂度：O(n)
数组：插入、删除一个节点时间复杂度：O(n)，查询一个节点时间复杂度：O(1)
循环链表：插入、删除一个节点时间复杂度：O(1)，查询一个节点时间复杂度：O(n)，循环链表中从任意一个节点开始，都可以遍历整个链表，因为它是一个环。
2. 单链表的代码实现和测试
2.1 单链表代码实现
单链表的代码实现如下所示，实现了获得当前节点的下一个节点、在单链表的末尾追加一个节点、删除当前节点的下一个节点、在当前节点之后插入一个节点等方法。
package linearStructure;
/**
* 单链表实现
* 插入、删除一个节点时间复杂度：O(1)
* 查询一个节点时间复杂度：O(n)
*/
public class ListNode {
private int data; // 节点的值
private ListNode next; // 下一个节点
/**
* 构造函数
* @param data 节点的值
*/
public ListNode(int data) {
this.data = data;
}
/**
* 获得当前节点的下一个节点
* @return 下一个节点
*/
public ListNode next() {
return next;
}
/**
* 获得当前节点的值
* @return 当前节点的值
*/
public int getData() {
return data;
}
/**
* 设置当前节点的值
* @param data 将要被设置的值
*/
public void setData(int data) {
this.data = data;
}
/**
* 在单链表的末尾追加一个节点
* @param listNode 追加的节点
*/
public ListNode append(ListNode listNode) {
ListNode nowListNode = this;
while(true) {
ListNode nextListNode = nowListNode.next;
if (null == nextListNode) {
break;
}
nowListNode = nextListNode;
}
nowListNode.next = listNode;
return this;
}
/**
* 删除当前节点的下一个节点
*/
public void deleteNext() {
// 取出下下个节点
ListNode nextNextNode = this.next().next();
// 删除下一个节点
this.next = nextNextNode;
}
/**
* 在当前节点之后插入一个节点
* @param listNode 插入的节点
*/
public void insertNode(ListNode listNode) {
listNode.next = this.next();
this.next = listNode;
}
/**
* 返回整个链表
* @return 整个链表
*/
public String show() {
ListNode temp = this;
StringBuilder res = new StringBuilder("[" + String.valueOf(temp.getData()));
while(temp.next != null) {
temp = temp.next();
res.append(" ").append(String.valueOf(temp.getData()));
}
res.append("]");
return res.toString();
}
}2.2 单链表测试
测试代码如下，
package linearStructure;
/**
* 单链表测试
*/
public class Test {
public static void main(String[] args) {
// 测试追加节点 append(), next()
ListNode listNode = new ListNode(2);
listNode.append(new ListNode(3));
listNode.append(new ListNode(4));
listNode.append(new ListNode(5)).append(new ListNode(6));
System.out.print("测试追加节点结果输出：");
System.out.print(listNode.getData() + " ");
System.out.print(listNode.next().getData() + " ");
System.out.print(listNode.next().next().getData() + " ");
System.out.print(listNode.next().next().next().getData() + " ");
System.out.println(listNode.next().next().next().next().getData() + " ");
// 测试删除节点 deleteNext()
// 删除节点 3
System.out.print("测试删除节点3结果输出：");
listNode.deleteNext();
System.out.println(listNode.show());
// 删除节点 6
System.out.print("测试删除节点6结果输出：");
listNode.next().next().deleteNext();
System.out.println(listNode.show());
// 测试插入节点
// 插入节点 3
System.out.print("测试插入节点3结果输出：");
listNode.insertNode(new ListNode(3));
System.out.println(listNode.show());
// 插入节点 6
System.out.print("测试插入节点6结果输出：");
listNode.next().next().next().insertNode(new ListNode(6));
System.out.println(listNode.show());
}
}测试代码运行结果如下：
3. 循环链表代码实现和测试
3.1 循环链表代码实现
相较于单链表的实现，要先修改构造参数，头结点要指向自己。
public ListNode(int data) {
this.data = data;
this.next = this;
}append() 在单链表的末尾追加一个节点，这个方法需要删去，没有最后一个节点了。
show() 方法需要修改，原方法会一直打圈，死循环。
完整代码如下所示：
package linearStructure;
/**
* 单链表实现
* 插入、删除一个节点时间复杂度：O(1)
* 查询一个节点时间复杂度：O(n)
*/
public class ListNode {
private int data; // 节点的值
private ListNode next; // 下一个节点
/**
* 构造函数
* @param data 节点的值
*/
public ListNode(int data) {
this.data = data;
this.next = this;
}
/**
* 获得当前节点的下一个节点
* @return 下一个节点
*/
public ListNode next() {
return next;
}
/**
* 获得当前节点的值
* @return 当前节点的值
*/
public int getData() {
return data;
}
/**
* 设置当前节点的值
* @param data 将要被设置的值
*/
public void setData(int data) {
this.data = data;
}
/**
* 删除当前节点的下一个节点
*/
public void deleteNext() {
// 取出下下个节点
ListNode nextNextNode = this.next().next();
// 删除下一个节点
this.next = nextNextNode;
}
/**
* 在当前节点之后插入一个节点
* @param listNode 插入的节点
*/
public void insertNode(ListNode listNode) {
listNode.next = this.next();
this.next = listNode;
}
/**
* 返回整个链表
* @return 整个链表
*/
public String show() {
ListNode temp = this;
StringBuilder res = new StringBuilder("[" + String.valueOf(temp.getData()));
while(temp.next != this) {
temp = temp.next();
res.append(" ").append(String.valueOf(temp.getData()));
}
res.append("]");
return res.toString();
}
}3.2 循环链表测试
测试代码如下：
package linearStructure;
/**
* 单链表测试
*/
public class Test {
public static void main(String[] args) {
// 创建循环链表
ListNode listNode = new ListNode(1);
// 测试插入节点
// 插入节点 3
System.out.print("测试插入节点3结果输出：");
listNode.insertNode(new ListNode(3));
System.out.println(listNode.show());
// 插入节点 5
System.out.print("测试插入节点5结果输出：");
listNode.next().next().next().insertNode(new ListNode(5));
System.out.println(listNode.show());
// 首节点通过next()来访问自己
System.out.print("首节点通过next()来访问自己：");
System.out.println(listNode.next().next().next().getData());
// 首节点通过next()转一圈来访问自己的下一个节点
System.out.print("首节点通过next()转一圈来访问自己的下一个节点：");
System.out.println(listNode.next().next().next().next().getData());
// 测试删除节点 deleteNext()
// 删除节点 3
System.out.print("测试删除节点3结果输出：");
listNode.deleteNext();
System.out.println(listNode.show());
}
}测试代码运行截图：
