链表

概念

链表是一个线性结构，同时也是一个天然的递归结构。链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

链表 - 图1

实现

单向链表

  1. class Node {
  2.   constructor(v, next) {
  3.     this.value = v
  4.     this.next = next
  5.   }
  6. }
  7. class LinkList {
  8.   constructor() {
  9.     // 链表长度
  10.     this.size = 0
  11.     // 虚拟头部
  12.     this.dummyNode = new Node(null, null)
  13.   }
  14.   find(header, index, currentIndex) {
  15.     if (index === currentIndex) return header
  16.     return this.find(header.next, index, currentIndex + 1)
  17.   }
  18.   addNode(v, index) {
  19.     this.checkIndex(index)
  20.     // 当往链表末尾插入时，prev.next 为空
  21.     // 其他情况时，因为要插入节点，所以插入的节点
  22.     // 的 next 应该是 prev.next
  23.     // 然后设置 prev.next 为插入的节点
  24.     let prev = this.find(this.dummyNode, index, 0)
  25.     prev.next = new Node(v, prev.next)
  26.     this.size++
  27.     return prev.next
  28.   }
  29.   insertNode(v, index) {
  30.     return this.addNode(v, index)
  31.   }
  32.   addToFirst(v) {
  33.     return this.addNode(v, 0)
  34.   }
  35.   addToLast(v) {
  36.     return this.addNode(v, this.size)
  37.   }
  38.   removeNode(index, isLast) {
  39.     this.checkIndex(index)
  40.     index = isLast ? index - 1 : index
  41.     let prev = this.find(this.dummyNode, index, 0)
  42.     let node = prev.next
  43.     prev.next = node.next
  44.     node.next = null
  45.     this.size--
  46.     return node
  47.   }
  48.   removeFirstNode() {
  49.     return this.removeNode(0)
  50.   }
  51.   removeLastNode() {
  52.     return this.removeNode(this.size, true)
  53.   }
  54.   checkIndex(index) {
  55.     if (index < 0 || index > this.size) throw Error('Index error')
  56.   }
  57.   getNode(index) {
  58.     this.checkIndex(index)
  59.     if (this.isEmpty()) return
  60.     return this.find(this.dummyNode, index, 0).next
  61.   }
  62.   isEmpty() {
  63.     return this.size === 0
  64.   }
  65.   getSize() {
  66.     return this.size
  67.   }
  68. }