【JavaScript】数据结构之链表（双指针、滑动窗口）
什么是链表？
- 多个元素存储的列表
- 链表中的元素在内存中不是顺序存储的，而是通过“next”指针联系在一起的，这个“next”可以自定义。
- JS中的原型链原理就是链表结构，是通过__proto__指针联系在一起的。
双指针形式
- 对撞指针：一般用于顺序结构中，也称左右指针
- 对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐向中间逼近。
- 对撞指针的终止条件一般是两个指针相遇（ left === right ）或者错开（left > right），也可能在循环内部找到结果跳出循环。
- 快慢指针：又称为龟兔赛跑算法
- 使用两个移动速度不同的指针在数组或者链表等序列结构上移动。
- 这种方法对于处理环形链表或者数组非常有用。
- 背向指针，对向指针（滑动窗口）
滑动窗口
- 也是通过双指针的思路去解决问题的
- 窗口的扩张得到结果，窗口的缩小优化结果
- 思路
- 右侧指针移位
- 判断是否符合预期
- 左侧指针是否需要移位
- 进入下一次循环
链表和数组的区别
- 数组是有序存储的，有下标0，1，2，3，在数组中间某个位置删除或添加某个元素，其他元素下标要跟着一起变化。
- 链表中的元素在内存中不是顺序存储的，而是通过“next”指针联系在一起的。
- 数组通过下标查找即可；链表每次查找都需要从头开始找。
链表的几种形式
- 单向链表
- 双向链表
- 环形链表
操作链表
链表案例
- instanceof 原理
链表习题
leetcode 链表习题