数据结构 - 链表

链表是什么？

链表也是多个元素组成的列表。
和数组不同的是，链表的存储不是连续的，用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