链表
1. 简介
所谓链表，通俗的说就是用一条链把数据都串起来
前面我们提到的数组、栈和队列都是顺序存储结构，这里的链表属于链式存储结构
什么是链表呢，我们直接上图
我们可以看到：每个链表结点至少包含两个元素：数据data、地址next（指向下一个数据）
分类：
最基础的链表就是单链表，在单链表的基础上有循环链表、双向链表、双向循环链表。
下面会分别进行介绍和实现。
2. 单链表
你猜的没错，前面我们看到的链表图，其实就是单链表。
单链表除了最后一个结点以外，其他结点都由数据data和t指向下一结点的nex组成
而最后一个结点的next为null
常见操作（方法）：
getData()—获取当前结点数据
next()—返回下一个结点
append()—结点追加-追加在链表最后
insertAfter()—结点插入
removeNode()—结点移除
show()—输出当前链表
isLast()—判断是否是最后一个结点
代码：
public class Node {
//结点数据
private int data;
//指向下一个结点
private Node next;
//构造函数中对结点赋值
public Node(int data){
this.data=data;
}
//返回当前结点数据
public int getData(){
return this.data;
}
//追加结点
public Node append(Node node){
//点前结点
Node currentNode=this;
//从当前结点开始依次往后寻找为null的结点进行追加
while(true){
//如果下一个结点为空，进行追加结点并调出循环
if(currentNode.next==null){
currentNode.next=node;
break;
}
//不是空，将下一个结点指向当前结点，接着向后寻找
currentNode=currentNode.next;
}
//返回当前结点方便调用
return this;
}
//获取下一个结点
public Node next(){
return this.next;
}
//判断是否最后一个结点
public Boolean isLast(){
return this.next==null;
}
//输出链表 (此方法只能输出当前结点及往后的元素结点内容)
public void show(){
//当前结点
Node CurrentNode=this;
while (true){
System.out.print(CurrentNode.data);
//如果没有下一个结点,结束
if(CurrentNode.next==null){
System.out.println();
break;
}else{
System.out.print("->");
//向后查找
CurrentNode=CurrentNode.next;
}
}
}
//删除下一个结点
public void removeNode(){
//将下下个结点指向当前结点的下一个结点
this.next=this.next.next;
}
//插入一个结点（当前结点后面）
public void insetAfter(Node node){
//保存下一个结点
Node nextNode=this.next;
//将插入的元素指向当前结点的下一个结点
this.next=node;
//最后将保存的结点指向刚刚插入结点的下一个结点
node.next=nextNode;
}
}
测试类
public class TestNode {
public static void main(String[] args) {
//创建三个结点，现在他们之间没有任何关联
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
//将node1和node2追加到node上面形成链表
node1.append(node2).append(node3).append(node4);
//通过node1获取node3的数据
System.out.println(node1.next().next().getData());
node1.show();
//移除node2
node1.removeNode();
node1.show();
//插入元素
node1.insetAfter(new Node(100));
node3.insetAfter(new Node(200));
node1.show();
}
}
结果：
3
1->2->3->4
1->3->4
1->100->3->200->4
3. 循环链表
循环链表就是将单链表最后一个结点指向第一个结点，这样让整个链表形成一个循环
循环链表由于没有尾结点，所以不能append结点
注意：循环链表只能插入结点，删除结点
在单链表基础上，我们将结点中的next初始化为this，也就是指向当前结点自己，就变成了循环链表，话不多说，下面直接上代码。
代码：
public class LoopNode {
//结点数据
private int data;
//指向下一个结点
private LoopNode next=this;
//构造函数中对结点赋值
public LoopNode(int data){
this.data=data;
}
//返回当前结点数据
public int getData(){
return this.data;
}
//获取下一个结点
public LoopNode next(){
return this.next;
}
//删除下一个结点
public void removeNode(){
//将下下个结点指向当前结点的下一个结点
this.next=this.next.next;
}
//插入一个结点（当前结点后面）
public void insetAfter(LoopNode node){
//保存下一个结点
LoopNode nextNode=this.next;
//将插入的元素指向当前结点的下一个结点
this.next=node;
//最后将保存的结点指向刚刚插入结点的下一个结点
node.next=nextNode;
}
}
测试类：
public class TestLoopNode {
public static void main(String[] args) {
//新增循环链表结点
LoopNode loopNode1 = new LoopNode(1);
LoopNode loopNode2 = new LoopNode(2);
LoopNode loopNode3 = new LoopNode(3);
//将loopNode2、loopNode3插入
loopNode1.insetAfter(loopNode2);
loopNode2.insetAfter(loopNode3);
//通过next查看下一个结点的值
System.out.println(loopNode1.next().getData());
System.out.println(loopNode2.next().getData());
//循环链表的特征
//注意：这里通过loopNode3.next() 访问到loopNode1
System.out.println(loopNode3.next().getData());
}
}
运行结果
2
3
1
4. 双向循环链表
双向循环链表：顾名思义就是每一个结点都可以访问其前后两个结点，并且是循环链表
特点：每一个结点都有pre和next分别指向相邻结点
特别的：第一个结点的pre指向最后一个结点，而最后一个结点的next指向第一个结点
每一个结点都可以访问到其前后两个结点所我们需要增加一个pre指向上一个结点
同时插入操作相比于单链表较为复杂，需要修改四个指向，见代码
代码：
public class DoubleNode {
//结点数据、指向前一个结点、指向后一个结点
private int data;
//如果没有结点插入（一个结点）默认指向自己
private DoubleNode pre=this;
private DoubleNode next=this;
public DoubleNode(int data){
this.data=data;
}
//返回当前结点的上一个结点
public DoubleNode pre(){
return this.pre;
}
//返回当前结点的下一个结点
public DoubleNode next(){
return this.next;
}
//获取数据
public int getData(){
return this.data;
}
//插入元素
public void insertAfter(DoubleNode doubleNode){
//保存当前结点的下一个结点（简称保存结点）
DoubleNode nextDoubleNode=this.next;
//将插入的结点指向当前结点的下一个结点next
this.next=doubleNode;
//同时将当前结点指向插入结点的上一个结点pre
doubleNode.pre=this;
//将保存结点指向插入结点的下一结点next
doubleNode.next=nextDoubleNode;
//同时将插入结点指向保存结点的上一结点pre
nextDoubleNode.pre=doubleNode;
}
}
测试类：
public class TestDoubleNode {
public static void main(String[] args) {
//初始化双向循环链表
DoubleNode doubleNode1 = new DoubleNode(1);
DoubleNode doubleNode2 = new DoubleNode(2);
DoubleNode doubleNode3 = new DoubleNode(3);
//将doubleNode2、doubleNode3插入doubleNode1
doubleNode1.insertAfter(doubleNode2);
doubleNode2.insertAfter(doubleNode3);
//输出检验
System.out.println(doubleNode1.pre().getData());
System.out.println(doubleNode1.next().getData());
System.out.println(doubleNode2.pre().getData());
System.out.println(doubleNode2.next().getData());
System.out.println(doubleNode3.pre().getData());
System.out.println(doubleNode3.next().getData());
}
}
结果：
3
2
1
3
2
1