链表
# 链表
# 概念
# 可扩展
链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；
# 插入、删除 O(1)
如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。
# 查找 O(n)
但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问,只能从头节点开始查找；
而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。
# hash 碰撞—拉链法是用链表实现的
hash 碰撞指的是，两个不同的值（比如张三、李四的学号）经过 hash 计算后，得到的hash 值相同，后来的李四要放到原来的张三的位置，但是数组的位置已经被张三占了，导致冲突。
# 开放寻址法
当前数组位置 1 被占用了，就放到下一个位置 2 上去，如果 2 也被占用了，就继续往下找，直到找到空位置。
# 拉链法
拉链法采用的是链表的方式，这个时候位置 1 就不单单存放的是 Entry 了，此时的 Entry 还要额外保存一个 next 指针，指向数组外的另一个位置，将李四安排在这里，张三那个 Entry 中的 next 指针就指向李四的这个位置，也就是保存的这个位置的内存地址。如果还有冲突，就把又冲突的那个 Entry 放到一个新位置上，然后李四的 Entry 指向它，这样就形成一个链表。
# 模拟实现
在 JavaScript 中可以用Object模拟链表：
const a = { val: 'a' };
const b = { val: 'b' };
const c = { val: 'c' };
const d = { val: 'd' };
a.next = b;
b.next = c;
c.next = d;
// 遍历链表
let p = a; // 声明指针 指向链表头部
while (p) {
console.log(p.val);
p = p.next;
}
// 插入(c、d之间插入e)
const e = { val: 'e' };
c.next = e;
e.next = d;
// 删除e
c.next = d;