一、前言
最近在回顾数据结构与算法，有部分的算法题用到了栈的思想，说起栈又不得不说链表了。数组和链表都是线性存储结构的基础，栈和队列都是线性存储结构的应用～
本文主要讲解单链表的基础知识点，做一个简单的入门～如果有错的地方请指正
二、回顾与知新
说起链表，我们先提一下数组吧，跟数组比较一下就很理解链表这种存储结构了。
2.1回顾数组
数组我们无论是c、java都会学过：
- 数组是一种连续存储线性结构，元素类型相同，大小相等
数组的优点：
- 存取速度快
数组的缺点：
- 事先必须知道数组的长度
- 插入删除元素很慢
- 空间通常是有限制的
- 需要大块连续的内存块
- 插入删除元素的效率很低
2.2链表说明
看完了数组，回到我们的链表：
- 链表是离散存储线性结构
n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。
链表优点：
- 空间没有限制
- 插入删除元素很快
链表缺点：
- 存取速度很慢
链表相关术语介绍，我还是通过上面那个图来说明吧：
确定一个链表我们只需要头指针，通过头指针就可以把整个链表都能推导出来了～
链表又分了好几类：
1、单向链表
- 一个节点指向下一个节点
2、双向链表
- 一个节点有两个指针域
3、循环链表
- 能通过任何一个节点找到其他所有的节点，将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环
操作链表要时刻记住的是：
节点中指针域指向的就是一个节点了！
三、java实现链表
算法：
- 遍历
- 查找
- 清空
- 销毁
- 求长度
- 排序
- 删除节点
- 插入节点
首先，我们定义一个类作为节点
- 数据域
- 指针域
为了操作方便我就直接定义成public了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public class node { //数据域 public int data; //指针域，指向下一个节点 public node next; public node() { } public node(int data) { this.data = data; } public node(int data, node next) { this.data = data; this.next = next; }} |
3.1创建链表(增加节点)
向链表中插入数据：
- 找到尾节点进行插入
- 即使头节点.next为null，不走while循环，也是将头节点与新节点连接的(我已经将head节点初始化过了，因此没必要判断头节点是否为null)～
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/*** 向链表添加数据** @param value 要添加的数据*/public static void adddata(int value) {//初始化要加入的节点node newnode = new node(value);//临时节点node temp = head;// 找到尾节点while (temp.next != null) {temp = temp.next;}// 已经包括了头节点.next为null的情况了～temp.next = newnode;} |
3.2遍历链表
上面我们已经编写了增加方法，现在遍历一下看一下是否正确～～～
从首节点开始，不断往后面找，直到后面的节点没有数据：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
/*** 遍历链表** @param head 头节点*/public static void traverse(node head) {//临时节点，从首节点开始node temp = head.next;while (temp != null) {system.out.println("关注公众号java3y：" + temp.data);//继续下一个temp = temp.next;}} |
结果：
3.3插入节点
- 插入一个节点到链表中，首先得判断这个位置是否是合法的，才能进行插入～
- 找到想要插入的位置的上一个节点就可以了～
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
/*** 插入节点** @param head 头指针* @param index 要插入的位置* @param value 要插入的值*/public static void insertnode(node head, int index, int value) {//首先需要判断指定位置是否合法，if (index < 1 || index > linklistlength(head) + 1) {system.out.println("插入位置不合法。");return;}//临时节点，从头节点开始node temp = head;//记录遍历的当前位置int currentpos = 0;//初始化要插入的节点node insertnode = new node(value);while (temp.next != null) {//找到上一个节点的位置了if ((index - 1) == currentpos) {//temp表示的是上一个节点//将原本由上一个节点的指向交由插入的节点来指向insertnode.next = temp.next;//将上一个节点的指针域指向要插入的节点temp.next = insertnode;return;}currentpos++;temp = temp.next;}} |
3.4获取链表的长度
获取链表的长度就很简单了，遍历一下，每得到一个节点+1即可～
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/*** 获取链表的长度* @param head 头指针*/public static int linklistlength(node head) {int length = 0;//临时节点，从首节点开始node temp = head.next;// 找到尾节点while (temp != null) {length++;temp = temp.next;}return length;} |
3.5删除节点
删除某个位置上的节点其实是和插入节点很像的， 同样都要找到上一个节点。将上一个节点的指针域改变一下，就可以删除了～
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
/*** 根据位置删除节点** @param head 头指针* @param index 要删除的位置*/public static void deletenode(node head, int index) {//首先需要判断指定位置是否合法，if (index < 1 || index > linklistlength(head) + 1) { system.out.println("删除位置不合法。"); return;}//临时节点，从头节点开始node temp = head;//记录遍历的当前位置int currentpos = 0;while (temp.next != null) { //找到上一个节点的位置了 if ((index - 1) == currentpos) { //temp表示的是上一个节点 //temp.next表示的是想要删除的节点 //将想要删除的节点存储一下 node deletenode = temp.next; //想要删除节点的下一个节点交由上一个节点来控制 temp.next = deletenode.next; //java会回收它，设置不设置为null应该没多大意义了(个人觉得,如果不对请指出哦～) deletenode = null; return; } currentpos++; temp = temp.next;}} |
3.6对链表进行排序
前面已经讲过了8种的排序算法了【八种排序算法总结】，这次挑简单的冒泡排序吧(其实我是想写快速排序的，尝试了一下感觉有点难.....)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
/*** 对链表进行排序** @param head**/public static void sortlinklist(node head) {node currentnode;node nextnode;for (currentnode = head.next; currentnode.next != null; currentnode = currentnode.next) { for (nextnode = head.next; nextnode.next != null; nextnode = nextnode.next) { if (nextnode.data > nextnode.next.data) { int temp = nextnode.data; nextnode.data = nextnode.next.data; nextnode.next.data = temp; } }}} |
3.7找到链表中倒数第k个节点
这个算法挺有趣的：设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
/*** 找到链表中倒数第k个节点(设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点** @param head* @param k 倒数第k个节点*/public static node findknode(node head, int k) {if (k < 1 || k > linklistlength(head)) return null;node p1 = head;node p2 = head;// p2比怕p1快k个节点for (int i = 0; i < k - 1; i++) p2 = p2.next;// 只要p2为null，那么p1就是倒数第k个节点了while (p2.next != null) { p2 = p2.next; p1 = p1.next;}return p1;} |
3.8删除链表重复数据
跟冒泡排序差不多，只要它相等，就能删除了～
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
/*** 删除链表重复数据(跟冒泡差不多，等于删除就是了)** @param head 头节点*/public static void deleteduplecate(node head) {//临时节点，(从首节点开始-->真正有数据的节点)node temp = head.next;//当前节点(首节点)的下一个节点node nextnode = temp.next;while (temp.next != null) { while (nextnode.next != null) { if (nextnode.next.data == nextnode.data) { //将下一个节点删除(当前节点指向下下个节点) nextnode.next = nextnode.next.next; } else { //继续下一个 nextnode = nextnode.next; } } //下一轮比较 temp = temp.next;}} |
3.9查询链表的中间节点
这个算法也挺有趣的：一个每次走1步，一个每次走两步，走两步的遍历完，然后走一步的指针，那就是中间节点
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
/*** 查询单链表的中间节点*/public static node searchmid(node head) {node p1 = head;node p2 = head;// 一个走一步，一个走两步，直到为null，走一步的到达的就是中间节点while (p2 != null && p2.next != null && p2.next.next != null) { p1 = p1.next; p2 = p2.next.next;}return p1;} |
3.10通过递归从尾到头输出单链表
|
1
2
3
4
5
6
7
8
9
10
11
|
/*** 通过递归从尾到头输出单链表** @param head 头节点*/public static void printlistreversely(node head) {if (head != null) { printlistreversely(head.next); system.out.println(head.data);}} |
3.11反转链表
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/*** 实现链表的反转** @param node 链表的头节点*/public static node reverselinklist(node node) {node prev ;if (node == null || node.next == null) { prev = node;} else { node tmp = reverselinklist(node.next); node.next.next = node; node.next = null; prev = tmp;}return prev;} |
反转链表参考自：http://www.zzvips.com/article/155099.html
四、最后
理解链表本身并不难，但做相关的操作就弄得头疼，head.next next next next ....(算法这方面我还是薄弱啊..脑子不够用了.....)写了两天就写了这么点东西...
操作一个链表只需要知道它的头指针就可以做任何操作了
1、添加数据到链表中
- 遍历找到尾节点，插入即可(只要while(temp.next != null)，退出循环就会找到尾节点)
2、遍历链表
- 从首节点(有效节点)开始，只要不为null，就输出
3、给定位置插入节点到链表中
- 首先判断该位置是否有效(在链表长度的范围内)
-
找到想要插入位置的上一个节点
将原本由上一个节点的指向交由插入的节点来指向
上一个节点指针域指向想要插入的节点 -
4、获取链表的长度
- 每访问一次节点，变量++操作即可
5、删除给定位置的节点
- 首先判断该位置是否有效(在链表长度的范围内)
-
找到想要插入位置的上一个节点
将原本由上一个节点的指向后面一个节点 -
6、对链表进行排序
- 使用冒泡算法对其进行排序
7、找到链表中倒数第k个节点
- 设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点
8、删除链表重复数据
- 操作跟冒泡排序差不多，只要它相等，就能删除了～
9、查询链表的中间节点
- 这个算法也挺有趣的：一个每次走1步，一个每次走两步，走两步的遍历完，然后走一步的指针，那就是中间节点
10、递归从尾到头输出单链表
- 只要下面还有数据，那就往下找，递归是从最后往前翻。
11、反转链表
- 有递归和非递归两种方式，我觉得是挺难的。可以到我给出的链接上查阅～
ps：每个人的实现都会不一样，所以一些小细节难免会有些变动，也没有固定的写法，能够实现对应的功能即可～
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对服务器之家的支持。
参考资料：
- http://www.cnblogs.com/whgk/p/6589920.html
- https://www.cnblogs.com/bywallance/p/6726251.html
原文链接：https://segmentfault.com/a/1190000014045776
