概念

  • 多个元素组成的列表
  • 元素存储不连续，用next指针连在一起

image.png
在JavaScript中没有链表，但可以用Object来模拟链表。

数组VS链表

  • 数组： 增删非首尾元素时往往需要移动元素
  • 链表： 增删非首尾元素时，不需要移动元素，只需要更改next的指向即可

Coding

写一个链表类

  1.  function ListNode(val, next) {
  2.    this.val = (val===undefined ? 0 : val)
  3.    this.next = (next===undefined ? null : next)
  4.  }

构建链表

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

console.log(a);

image.png

遍历链表

let p = a
while (p) {
    console.log(p);
    p = p.next
}

image.png

链表的插入节点

在b节点和c节点中插入一个e节点

const e = { val: 'e' }
b.next = e
e.next = c

链表的删除节点

方法一：要删除上面插入的e节点， 只需恢复原指向即可，此时没有节点指向e

b.next = c

方法二： 方法一是在知道e节点的上一节点的情况下才能实现的，当不知道e的上一节点时，可以将e的值改为其下一节点的值，并删除下一节点

e.val = c
e.next = d