【数据结构与算法】链表（Linked List）
文章目录
1. 初识链表
动态数组的缺点：
- 可能会造成内存空间的大量浪费。
用多少申请多少内存？
- 链表解决
链表是一种链式存储的线性表，所有元素的内存地址不一定连续。
如何往列表里添加元素：首先创建一个节点对象，在这个节点内部分配一块存储空间出来，来存储真正的数据。
添加新的元素分配新的存储空间，此时内存地址是随机的。
最后一个元素的下一个node地址为null。
链表里至少两个元素：size和first
first第一个节点里应该有element和next
element：存放的元素
next：下一个节点
2. 链表的继承关系
链表的大部分接口与动态数组是一致的。它两都是线性表。
用接口的方法。
二者公共的代码
利用继承，抽象线性表，来封装。
让他们的父类abstractList去实现List接口
父类引用指向子类对象
3. 虚拟头节点
有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面加上一个虚拟的头节点（不存储数据）。
4. 均摊时间负责度
什么情况下适合使用均摊复杂度？
- 经过连续多次复杂度比较低的情况后，出现个别复杂度比较高的情况。
5. 动态数据的缩容
如果内存使用比较紧张，动态数组有比较多的剩余空间，可以考虑缩容操作。
6. 复杂度振荡
如果扩容倍数，缩容时机设计不得当，有可能会导致复杂度振荡。
7. 双向链表
此前所学链表是单向链表
使用双向链表可以提升列表的综合性能
单向列表只能从头开始搜索。
动态数组、双向链表如何选择？
动态数组：开辟、销毁内控空间的次数相对较少，但可能造成内存空间浪费（可以通过缩容解决）。
双向链表：开辟、销毁内控空间的次数相对较多，但不会造成内存空间浪费]\
- 如果频繁在尾部进行添加、删除操作，动态数组，双向链表都可以选择。
- 如果如果频繁在头部进行添加、删除操作，建议选择双向链表。
- 如果有频繁的（在任意位置）进行添加、删除操作，建议使用双向链表
- 如果有频繁的查询操作（随机访问操作），建议使用动态数组。
有了双向链表，单项链表是否没有用处了？
哈希表的设计中用到了单链表
JAVA的 gc root对象
JAVA的 gc root对象，如果对象不是被gc对象引用着，就会回收内存。
- 被栈指针（局部变量）指向的对象，栈：局部变量
举例：List list = new ArrayList<>();
list是栈里面的指针，new出来的ArrayList是在堆空间中，所以new ArrayList这个对象就可以称之为 gc root 对象。
判断是否被回收：finalize（）
8. 单向循环链表
10. 双向循环链表
add()、 remove() 考虑情况
add():
- 往最后一个位置插入元素的情况，原来链表只有一个节点的情况
- 其他位置的话，往第一个节点位置插入的情况。
remove()：
- 只有一个节点的情况，size == 0
- 多个节点的话，删除第一个节点和最后一个节点的情况
11. 约瑟夫问题
发挥循环链表的最大威力
可以考虑增设一个成员变量、3个方法
current : 指向某个节点
void reset() : 让current指向头节点 first
E next() : 让current 往后走一步，即current = current.next
E remove() : 删除current指向的节点，删除成功后让current指向下一个节点。
12. 静态链表
前面所学链表都是依赖指针（引用）实现的。
可以通过数组来模拟链表，称为静态链表。
数组的每个元素存放2个数据: 值、下个元素的索引
数组0位置存放的是头节点的信息。
结果：11 -> 44 -> 22 -> 55 -> 33
如果数组的每个元素只能存放一个数据？
那就使用2个数组，1个存放索引关系，1个存放值。