什么是链表？

• 多个元素存储的列表
• 链表中的元素在内存中不是顺序存储的，而是通过“next”指针联系在一起的，这个“next”可以自定义。
• JS中的原型链原理就是链表结构，是通过__proto__指针联系在一起的。
  
  

双指针形式

• 对撞指针：一般用于顺序结构中，也称左右指针
  • 对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐向中间逼近。
  • 对撞指针的终止条件一般是两个指针相遇（ left === right ）或者错开（left > right），也可能在循环内部找到结果跳出循环。
• 快慢指针：又称为龟兔赛跑算法
  • 使用两个移动速度不同的指针在数组或者链表等序列结构上移动。
  • 这种方法对于处理环形链表或者数组非常有用。
• 背向指针，对向指针（滑动窗口）

滑动窗口

• 也是通过双指针的思路去解决问题的
• 窗口的扩张得到结果，窗口的缩小优化结果
• 思路
  • 右侧指针移位
  • 判断是否符合预期
  • 左侧指针是否需要移位
  • 进入下一次循环

链表和数组的区别

• 数组是有序存储的，有下标0，1，2，3，在数组中间某个位置删除或添加某个元素，其他元素下标要跟着一起变化。
• 链表中的元素在内存中不是顺序存储的，而是通过“next”指针联系在一起的。
• 数组通过下标查找即可；链表每次查找都需要从头开始找。

链表的几种形式

• 单向链表
  
• 双向链表
  
• 环形链表

操作链表

链表案例

• instanceof 原理

链表习题

leetcode 链表习题