数据结构 ~ 链表

什么是链表

---

链表由多种元素组成，元素储存不连续，用 next 指针联系在一起；
数组：非首尾增删需要移动元素；
链表：只需要更改 next 指向即可；
JavaScript 没有链表，但可以使用 Object 模拟：**

const a = { name: 'zhangsan' }
const b = { name: 'lisi' }
const c = { name: 'wangwu' }
const d = { name: 'zhaoliu' }

模拟链表：

a.next = b
b.next = c
c.next = d

遍历 ：

let pointer = a // 指针，初始化指向首个元素
while (pointer) {
  console.log(pointer.name) // zhangsan lisi wangwu zhaoliu
  pointer = pointer.next
}

插入 ：

const c2 = { name: 'sunqi' }
c.next = c2
c2.next = d

删除 ：

b.next = d

算法

---

删除一个元素：

const a = { val: 4 }
const b = { val: 5 }
const c = { val: 1 }
const d = { val: 9 }
a.next = b
b.next = c
c.next = d

步骤一：将当前元素的 val 设置为当前元素下一个元素的 val
步骤二：将当前元素的指针 next 指向当前元素后第二个元素

const deleteNode = function (node) {
  node.val = node.next.val
  node.next = node.next.next
}
deleteNode(b)

反转指针

const a = { val: 2 }
const b = { val: 4 }
const c = { val: 6 }
const d = { val: 8 }

a.next = b
b.next = c
c.next = d
d.next = null

步骤一：保存当前元素的下一位元素
步骤二：当前元素的指针指向上一位元素
步骤三：保存当前元素
步骤四：当前指针指向下一位元素

const reverseList = function (head) {
  let p1 = head // 当前指针
  let p2 = null // 当前元素上一个元素的指针
  while (p1) {
    const tmp = p1.next // 保存当前元素的下一位元素
    p1.next = p2 // 当前元素的指针指向上一位元素
    p2 = p1 // 保存当前元素
    p1 = tmp // 当前指针指向下一位元素
  }
  return p2
}
reverseList(a)