单链表学习心得与算法实现
单链表的定义
链表是一种有序的数据存储结构，其也是线性表，与顺序表不同的是，顺序表的存储是连续的，而链表的存储可以是离散的，只需要在逻辑上是连续即可。链表可以分为单链表、双链表、循环链表。单链表是每次只能从头指针开始，每个结点包含当前的结点内容和后一结点的指向，不能向前搜索。链表的好处就是可以离散存储，也是一种动态的存储方式，即插入和删除不需要改变存储位置，可以动态变化。
单链表的java定义：
每个结点包含两部分，即当前结点的内容和后一结点的指向。
//一个结点
public class Node {
//结点内容
int data;
//下一个结点
Node next;
public Node(int data) {
this.data = data;
}
追加结点
当定义好每个结点的信息之后，需要将结点连接起来，就需要给每个结点追加结点，其中头结点只有后一结点，尾结点的后一节点为空。
目的是在链表的头结点处追加结点，而实现的过程则是需要遍历整个链表，找到最后一个 结点之后将加入的结点添加到此结点的后一结点处。这才是真正实现了追加的功能。可以无限追加。
//为结点追加结点
public Node append(Node node) {
//this.next = node;
//当前结点
Node currentNode = this;
//循环向后找
while (true) {
//取出下一个结点
Node nextNode = currentNode.next;
if (nextNode == null) {
break;
}
//赋给当前结点
currentNode = nextNode;
}
//把需要的追回的结点追加为找到的当前结点的下一个结点
currentNode.next = node;
return this;
}
删除结点
单链表要删除一个结点并不可以直接找到删除结点来直接删除，而是需要将删除结点的前一结点找到，然后将删除结点前一结点直接指向删除结点的后一个结点，这样就可以将此结点删除掉。
public void removeNext() {
Node newNext = next.next;
this.next = newNext;
}
获取当前结点的内容或者值
实现很简单，只需要返回当前结点的数据即可。
//获取结点数据
public int getData() {
return this.data;
}
获取当前结点的下一个结点
实现也简单，只需要返回即可以。
public Node next() {
return this.next;
}
显示链表的所有结点信息
只需要遍历整个链表，返回每个结点的值，当判断到结点为null时停止遍历，整个内容打印就可以。
//显示所有结点信息
public void show() {
Node currentNode = this;
while(true) {
System.out.print(currentNode.data+" ");
currentNode = currentNode.next;
if (currentNode == null) {
break;
}
}
System.out.println();
}
插入一个结点
插入一个结点的目的是在整个链表中任意结点处，我们需要找到插入结点的位置，然后在其后面将结点插入。
实现过程是将插入位置的前一个结点的后一结点保存，然后将前一个结点指向此插入结点，再将此插入结点的指向原来保存的后一结点作为下一结点，此时实现了插入功能。
//插入一个结点
public void after(Node node) {
//取出下一个结点作为下下一个结点
Node nextNext = next;
//把新结点作为当前结点的下一个结点
this.next = node;
//把下下结点作为当前结点的下一个结点
node.next = nextNext;
}
整个单链表的实现代码
package 线性结构;
//一个结点
public class Node {
//结点内容
int data;
//下一个结点
Node next;
public Node(int data) {
this.data = data;
}
//为结点追加结点
public Node append(Node node) {
//this.next = node;
//当前结点
Node currentNode = this;
//循环向后找
while (true) {
//取出下一个结点
Node nextNode = currentNode.next;
if (nextNode == null) {
break;
}
//赋给当前结点
currentNode = nextNode;
}
//把需要的追回的结点追加为找到的当前结点的下一个结点
currentNode.next = node;
return this;
}
public Node next() {
return this.next;
}
//获取结点数据
public int getData() {
return this.data;
}
public void removeNext() {
Node newNext = next.next;
this.next = newNext;
}
//显示所有结点信息
public void show() {
Node currentNode = this;
while(true) {
System.out.print(currentNode.data+" ");
currentNode = currentNode.next;
if (currentNode == null) {
break;
}
}
System.out.println();
}
//插入一个结点
public void after(Node node) {
//取出下一个结点作为下下一个结点
Node nextNext = next;
//把新结点作为当前结点的下一个结点
this.next = node;
//把下下结点作为当前结点的下一个结点
node.next = nextNext;
}
public static void main(String[] args) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
n1.append(n2);
n1.append(n3);
// System.out.println(n1.next.next.getData());
// n1.show();
// n1.removeNext();
n1.show();
Node node = new Node(5);
n1.next().after(node);
n1.show();
}
}
运行截图
循环列表
循环列表只需要将尾结点的下一个结点指向头结点就可以实现循环，实现过程与单链表不同的是只需要将下一个结点指向自己就可以。即：
//下一个结点
LoopNode next = this;
##整个实现过程如下：
package 线性结构;
//一个结点
public class LoopNode {
//结点内容
int data;
//下一个结点
LoopNode next = this;
public LoopNode(int data) {
this.data = data;
}
public LoopNode next() {
return this.next;
}
//获取结点数据
public int getData() {
return this.data;
}
public void removeNext() {
LoopNode newNext = next.next;
this.next = newNext;
}
//插入一个结点
public void after(LoopNode node) {
//取出下一个结点作为下下一个结点
LoopNode nextNext = next;
//把新结点作为当前结点的下一个结点
this.next = node;
//把下下结点作为当前结点的下一个结点
node.next = nextNext;
}
public static void main(String[] args) {
LoopNode n1 = new LoopNode(1);
LoopNode n2 = new LoopNode(2);
LoopNode n3 = new LoopNode(3);
LoopNode n4 = new LoopNode(4);
n1.after(n2);
n2.after(n3);
n3.after(n4);
System.out.println(n1.next().getData());
System.out.println(n2.next().getData());
System.out.println(n3.next().getData());
System.out.println(n4.next().getData());
}
}
运行结果
可以看到结点1的下一结点为2，结点2的下一结点为3，结点3的下一个结点为4，结点4的下一个结点为1.实现循环。