数据结构 - 链表
链表是什么？
链表也是多个元素组成的列表。
和数组不同的是，链表的存储不是连续的，用next指针来连接起来。
js中的链表使用Object来实现。
class ListNode {
constructor(val, next) {
this.val = val;
this.next = next;
}
}
举例说明链表
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
d.next = null
数组 vs 链表
- 数组的存储是连续的，增删非首尾元素往往需要移动其他元素。
- 链表的存储不是连续的，增删非首尾元素不需要移动其他元素，只需要修改next的指向即可。
链表的基本操作
遍历链表
思路：
1、声明一个指针，默认指向头部
2、获取完当前值后，指针指向下一个链表元素
3、循环第二步，直至指针指向null结束
let p = a;
while(p) {
console.log(p.val);
p = p.next;
}
插入链表
思路：
1、将要插入的上一个元素的next指向插入元素
2、插入元素的next指向下一个元素
// 在 b 和 c 之间插入元素 e
const e = {val: 'e'};
b.next = e;
e.next = c;
删除链表
思路：
1、将要删除的上一个元素的next指向删除的下一个元素
// 删除c
b.next = d