-
动态数组有个明显的缺点：可能会造成内存空间的大量浪费，能否用到多少就申请内存？
-
链表可以办到这一点
-
链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的
-
https://visualgo.net/zh 数据结构和算法动态可视化
- 快指针走两步，慢指针走一步，如果有环存在，它们两个一定会相遇。因为模拟一下就知道，它们之间得距离是每次递减1，所以一定会相遇。
- 有时候为了让代码更加精简，统一所节点的处理逻辑可以在最前面增个虚拟头结点（不存储数据）
- 经过连续的多次复杂度比较低的情况后，出现个别复杂度比较高的情况
-
如果内存使用比较紧张，动态数组有多的剩余空间可以考虑进行缩容操作，比如剩余空间占总容量的一半时，就进行缩容
-
如果扩容倍数、缩时机设计不得当，有可能会导致复杂度震荡
-
复杂度震荡的解决办法：让缩容和扩容的倍数相乘不要等于
- 粗略对比一下删除操作的数量
- 单向链表 1 + 2 + 3 + ... + n = ((1 + n) * n) / 2 再除以 n ，最后是 1/2 + n/2 => O(n)。
- 双向链表 (1 + 2 + 3 + ... + n/2) * 2 = (((1 + n/2) * n/2) / 2 )* 2 再除以 n ，最后是 1/2 + n/4 => O(n)
- 把可能的操作次数全部加起来，然后除以数据规模，得出平均复杂度。双向链表计算两个方向，所以乘以 2。
- 虽然双向链表也是 O(n)，但是看到它是 n/4 ，而 单向链表是 n/2，所以双向链表平均操作次数比单向链表少了一半。
-
动态数组 ：开辟、销毁内存空间的次数相对较少，但可能造成浪费（以通过缩容解决）
-
双向链表 ：开辟、销毁内存空间的次数相对较多，但不会造成浪费
-
如果频繁在 尾部 进行 添加 、删除 操作， 动态数组 、双向链表 均可选择
-
如果频繁在 头部 进行 添加 、删除 操作，建议选择使用 双向链表
-
如果有频繁的（ 在任意位置 ）添加 、删除 操作，建议选择使用 双向链表
-
如果有频繁的 查询 操作（随机访问），建议选择使用 动态数组
-
有了双向链表，单向链表是否就没任何用处？并非如此，在哈希表的设计中就用到了单向链表