?
?
?日升时奋斗，日落时自省
目录
? 首先我们为什么要学习链表，上节中已经学习了ArrayList，那是因为ArrayList不能够在所有效率上都是优先的，例如，我们每次增加，删除等都是需要遍历属于数组的，也是相当浪费时间的，效率相对来说是较低的，而我们就需要另一种方式来解决该问题，链表就出来了，链表可以使增加和删除时间复杂度为O(1)，达到了可观的效率。
一、链表
1.链表结构
链表顾名思义就是像锁链一样的表，锁链一样环环相扣
链表是有节点构成的，就像每一个锁链中每一个铁环
?
链表有两部分构成一部分是数据，另一部分是下一个节点地址
那看一下我们的链表的代码结构
?我将它们的地址都用蓝色的框起来，观察方便，头结点用地址连接这下一个节点的
这里是有序的吗，只是逻辑上有序，就如现在看到的
物理上是不一定有序的
基本就是这样，画的不好见谅哈
连接是指向我们想要的位置，不是按照系统给分的指定存储顺序
2.链表划分
链表以这几个点可以分开
?
那又这几个点可以分为多少种链表类型? ? ? ?可以分为八种（如下图）
?
?我们初次学习链表先以 单向? 不可循环? 无头结点的链表为先
3.链表实现
如何创建一个java中的链表结构
3.1链表的长度（不如顺序表计算那么快）
?这里解释一下下面这行代码的意思，它表示的是我们把我们需要的头结点给一个替身，让替身替我们走完这个链表而不影响我们的头结点的位置
?
3.2 链表的打印
链表的打印与计算长度是相仿的
?3.3链表的头插
代码用图解?
（1）首先创建一个新节点，传值后成为一个真正的新节点?
（2）将新节点的下一个节点连接head节点
（3）我们每次调用的head，最后node=head将head恢复到头结点的位置
3.4链表的尾插
（1）首先还是创建一个新节点
（2）这里不同于头插，尾插的时候，head不能先为空（null），所以当插入第一个时，先给头结点
（3）开始遍历当前链表至最后一个节点，该节点连接新节点的位置
3.5链表的任意位置插入
（1）插入位置的限制（不能为负值 head不能空）
（2）特殊情况：头插，尾插
（3）普通情况：找到插入节点的前一个位置
?
?
?插入的图解，先走第一步 ，再走第二步不能改变顺序，改变顺序的话那不就找不到连接0x12连接0x13的节点了
3.6链表包含值
（1）排除当前链表为空
（2）遍历当前链表值，if(cur.val==key)找到对应的值
（3）遍历完没有找到，返回false?
?3.7链表删除
（1）首先排除空链表
（2）因为是找前一个节点，所以第一个没有前一个节点，就需要把，头结点作为特殊情况处理
（3）找到我们要删除值的前一个节点
（4）判断是否有该节点
?
遍历查找当前节点，?与前面相同，就不解释了
?
?删除图解
3.8删除链表中所有相同的节点
（1）首先判断链表是否为空
（2）如何删除所有呢，全部是怎么办，设立一个前置节点，一个遍历链表的节点，下来我们图解来解释这个
（3）虽然遍历完了，但是不能删除头结点位置的值，如果恰好是头结点的位置，应该如何删除，将头结点作为特殊情况下进行删除
?
?
?
?
?
?3.9清空链表（防止内存溢出）
（1）遍历每一个节点置空 （与前面遍历是一样的，只是把值变成了null）
?