最近在回顾数据结构与算法，有部分的算法题用到了栈的思想，说起栈又不得不说链表了。数组和链表都是线性存储结构的基础，栈和队列都是线性存储结构的应用～
本文主要讲解单链表的基础知识点，做一个简单的入门～如果有错的地方请指正
说起链表，我们先提一下数组吧，跟数组比较一下就很理解链表这种存储结构了。
数组我们无论是C、Java都会学过：
- 数组是一种连续存储线性结构，元素类型相同，大小相等
数组的优点：
- 存取速度快
数组的缺点：
- 事先必须知道数组的长度
- 插入删除元素很慢
- 空间通常是有限制的
- 需要大块连续的内存块
- 插入删除元素的效率很低
看完了数组，回到我们的链表：
- 链表是离散存储线性结构
n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。
链表优点：
- 空间没有限制
- 插入删除元素很快
链表缺点：
- 存取速度很慢
链表相关术语介绍，我还是通过上面那个图来说明吧：
确定一个链表我们只需要头指针，通过头指针就可以把整个链表都能推导出来了～
链表又分了好几类：
- 单向链表
- 一个节点指向下一个节点
- 双向链表
- 一个节点有两个指针域
- 循环链表
- 能通过任何一个节点找到其他所有的节点，将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环
操作链表要时刻记住的是：
- 节点中指针域指向的就是一个节点了！
算法：
- 遍历
- 查找
- 清空
- 销毁
- 求长度
- 排序
- 删除节点
- 插入节点
首先，我们定义一个类作为节点
- 数据域
- 指针域
为了操作方便我就直接定义成public了。
向链表中插入数据：
- 找到尾节点进行插入
- 即使头节点.next为null，不走while循环，也是将头节点与新节点连接的(我已经将head节点初始化过了，因此没必要判断头节点是否为null)～
上面我们已经编写了增加方法，现在遍历一下看一下是否正确～～～
从首节点开始，不断往后面找，直到后面的节点没有数据：
结果：
- 插入一个节点到链表中，首先得判断这个位置是否是合法的，才能进行插入～
- 找到想要插入的位置的上一个节点就可以了～
获取链表的长度就很简单了，遍历一下，每得到一个节点+1即可～
删除某个位置上的节点其实是和插入节点很像的， 同样都要找到上一个节点。将上一个节点的指针域改变一下，就可以删除了～
前面已经讲过了8种的排序算法了【八种排序算法总结】，这次挑简单的冒泡排序吧(其实我是想写快速排序的，尝试了一下感觉有点难.....)
这个算法挺有趣的：设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点
跟冒泡排序差不多，只要它相等，就能删除了～
这个算法也挺有趣的：一个每次走1步，一个每次走两步，走两步的遍历完，然后走一步的指针，那就是中间节点
反转链表参考自：
- http://www.cnblogs.com/hanxue112253/p/8533426.html
理解链表本身并不难，但做相关的操作就弄得头疼，(算法这方面我还是薄弱啊..脑子不够用了.....)写了两天就写了这么点东西...
操作一个链表只需要知道它的头指针就可以做任何操作了
- 添加数据到链表中
- 遍历找到尾节点，插入即可(只要，退出循环就会找到尾节点)
- 遍历链表
- 从首节点(有效节点)开始，只要不为null，就输出
- 给定位置插入节点到链表中
- 首先判断该位置是否有效(在链表长度的范围内)
- 找到想要插入位置的上一个节点
- 将原本由上一个节点的指向交由插入的节点来指向
- 上一个节点指针域指向想要插入的节点
- 获取链表的长度
- 每访问一次节点，变量++操作即可
- 删除给定位置的节点
- 首先判断该位置是否有效(在链表长度的范围内)
- 找到想要插入位置的上一个节点
- 将原本由上一个节点的指向后面一个节点
- 对链表进行排序
- 使用冒泡算法对其进行排序
- 找到链表中倒数第k个节点
- 设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点
- 删除链表重复数据
- 操作跟冒泡排序差不多，只要它相等，就能删除了～
- 查询链表的中间节点
- 这个算法也挺有趣的：一个每次走1步，一个每次走两步，走两步的遍历完，然后走一步的指针，那就是中间节点
- 递归从尾到头输出单链表
- 只要下面还有数据，那就往下找，递归是从最后往前翻。
- 反转链表
- 有递归和非递归两种方式，我觉得是挺难的。可以到我给出的链接上查阅～
PS：每个人的实现都会不一样，所以一些小细节难免会有些变动，也没有固定的写法，能够实现对应的功能即可～
参考资料：
- http://www.cnblogs.com/whgk/p/6589920.html
- https://www.cnblogs.com/bywallance/p/6726251.html
如果文章有错的地方欢迎指正，大家互相交流。习惯在微信看技术文章，想要获取更多的Java资源的同学，可以关注微信公众号:Java3y
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/java-jiao-cheng/8756.html