【数据结构】链表LinkedList

1.ArrayList的缺陷

2.单链表的实现

3.LinkedList的使用（模拟实现）

我们之前介绍过ArrayList了，它的底层是数组，数组是一段连续的空间，当我们想要插入或者删除数据的时候，插入元素，就要让插入位置的元素整体都往后移动，删除元素同样要让后面的元素往前移动，当要进行元素很多的插入或者删除的时候，ArrayList是效率很低的，所以当我们要大量插入元素或者大量删除元素，不推荐使用ArrayList

（由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景）

因此：java集合中又引入了LinkedList，即链表结构。

（1）链表的概念：链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 

链表我们之前也介绍过，它在物理空间上是不连续，但在逻辑上连续，也就是说它的元素所在的存储空间中不是连在一起的，不是说元素1空间后面就是元素2的空间，但它在逻辑上连续，元素1跟元素2相当于拿一根绳子连接，虽然不是紧挨着的，但通过元素1就能找到元素2，这就像我们生活中的火车，或火车的车厢都是链在一起的

 链表中的元素我们称为节点，一个节点包含着本身的值，和下一个节点的信息（下一个节点的地址），分别是value和next（对于单链表而言）

---

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

（1）带头不带头

（2）单向双向

（3）循环非循环

我们把他们排列组合一下就能排列出8中情况，我们重要学习的链表结构有两种

1.不带头单向非循环

2.不带头双向非循环

自然这两种是面试笔试中常考的，当然也是比较难懂的，因为给的条件不多嘛~

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多

无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

这里解释一下这几个词的含义

带头 | | 不带头：头的意思就是头节点的意思，头节点的值一般没有什么含义，它与第一个元素链接，它拥有第一个元素的地址，只要有头，我们就能轻松找到第一个元素，你可以把它当做一个虚拟节点（虚拟节点的操作经常用来解题）

单向 || 双向：什么叫做单向，我们不是说了嘛，每一个节点它都包含下一个节点的地址，单向顾名思义就是一个方向，你只能从1找到2，而不能返回来从2找到1，因为1有2的地址，2只有3的地址，没有1的地址，所以说它是单向的；那么双向就是可以从1找到2，也可以从2找到1啦，双向链表的节点中，包含了两个地址，一个是下一个节点的地址，另外一个是上一个节点的地址

 上图就是单链表和双链表的图解

循环 |