链表

链表是什么

链表是一种线性数据结构，其利用 地址引用 来将数据串联起来，上一个数据的 后继next指针 引用下一个数据的 内存地址，正因如此，链表的 内存地址并非一定连续

单向链表 双向链表

由上图可以看出，链表的 头结点 和 尾结点 是比较特殊的节点，通过 头结点，可以遍历整个链表，而尾结点的 next指针 指向了 null，说明尾结点后面没有数据了

双向链表较单向链表会消耗更多的内存来提供前驱节点地址的存放，但其可以方便的进行反向遍历

链表 vs 数组

结构	随机访问	插入/删除	内存地址连续
数组	O(1)	O(n)	连续
链表	O(n)	O(1)	不连续

数组的优点就是支持 随机访问，缺点是因为其 内存地址必须连续，所以有可能创建的时候有相应大小的空间但是不能申请成功，而且在做插入删除的时候需要做大量的数据搬移工作

链表的优点是不用一定连续的内存空间，插入删除时也不需要做数据搬移工作，缺点是不能支持随机访问，只能通过遍历链表来查找数据，而且当链表进行频繁的插入删除操作时，会进行大量的申请释放内存操作，可能产生内存碎片

理解链表

指针

理解链表首先要知道指针或者引用是什么东西，链表的 next 指针是如何找到下一个链表节点的

指针实际上存放的是 所指向的变量的内存地址，在 Java 等语言中没有指针的概念，取而代之的是引用，其实引用就是讲指针简化了，使其更容易理解。

将某个变量赋值给指针，实际上就是讲变量的内存地址存放在指针，然后寻找变量的时候就可以通过指针指向的内存地址，找到该变量。

引用其实是一个道理，将某个对象赋值给一个变量，这个变量其实存放的是该对象的引用(地址)，访问变量就是通过该变量引用的地址去找到对应的对象

指针引用不要丢失

在删除或者插入链表时，操作顺序的不同，会导致不同的结果，可能会产生引用丢失的问题

比如在插入操作时：

正确的步骤应该为:

1. 将新节点的 next指针 指向插入位置的节点
2. 将插入位置节点的前驱的 next指针 指向新节点

但是，如果将操作顺序互换的话，插入节点及其后继就会与链表脱节，导致引用丢失，如下图

操作正确
操作错误

哨兵

可以利用一个头哨兵来统一化插入和删除操作，正常插入第一个节点和删除最后一个节点是需要特殊处理的

练习

1. 单链表反转
2. 链表中环的检测
3. 有序链表合并
4. 删除倒数第 n 个节点
5. 求中间节点