链表是什么
链表是一种线性数据结构，其利用 地址引用 来将数据串联起来，上一个数据的 后继next指针 引用下一个数据的 内存地址，正因如此，链表的 内存地址并非一定连续
由上图可以看出，链表的 头结点 和 尾结点 是比较特殊的节点，通过 头结点，可以遍历整个链表，而尾结点的 next指针 指向了 null，说明尾结点后面没有数据了
双向链表较单向链表会消耗更多的内存来提供前驱节点地址的存放，但其可以方便的进行反向遍历
链表 vs 数组
| 结构 | 随机访问 | 插入/删除 | 内存地址连续 |
|---|---|---|---|
| 数组 | O(1) | O(n) | 连续 |
| 链表 | O(n) | O(1) | 不连续 |
数组的优点就是支持 随机访问，缺点是因为其 内存地址必须连续，所以有可能创建的时候有相应大小的空间但是不能申请成功，而且在做插入删除的时候需要做大量的数据搬移工作
链表的优点是不用一定连续的内存空间，插入删除时也不需要做数据搬移工作，缺点是不能支持随机访问，只能通过遍历链表来查找数据，而且当链表进行频繁的插入删除操作时，会进行大量的申请释放内存操作，可能产生内存碎片
理解链表
指针
理解链表首先要知道指针或者引用是什么东西，链表的 next 指针是如何找到下一个链表节点的
指针实际上存放的是 所指向的变量的内存地址，在 Java 等语言中没有指针的概念，取而代之的是引用，其实引用就是讲指针简化了，使其更容易理解。
将某个变量赋值给指针，实际上就是讲变量的内存地址存放在指针，然后寻找变量的时候就可以通过指针指向的内存地址，找到该变量。
引用其实是一个道理，将某个对象赋值给一个变量，这个变量其实存放的是该对象的引用(地址)，访问变量就是通过该变量引用的地址去找到对应的对象
指针引用不要丢失
在删除或者插入链表时，操作顺序的不同，会导致不同的结果，可能会产生引用丢失的问题
比如在插入操作时：
正确的步骤应该为:
- 将新节点的 next指针 指向插入位置的节点
- 将插入位置节点的前驱的 next指针 指向新节点
但是，如果将操作顺序互换的话，插入节点及其后继就会与链表脱节，导致引用丢失，如下图
哨兵
可以利用一个头哨兵来统一化插入和删除操作，正常插入第一个节点和删除最后一个节点是需要特殊处理的
练习
- 单链表反转
- 链表中环的检测
- 有序链表合并
- 删除倒数第 n 个节点
- 求中间节点
