数据结构在JS中的实现

0.写在开头

本篇文章旨在实现各种数据结构，实现为主，介绍为辅(或者说基本不介绍)，要看具体详情可以参考《在 JavaScript 中学习数据结构与算法》 (opens new window)这篇博客

1.栈

栈(Stack)：后进先出LIFO

class Stack {
  constructor(items = []) {
    this.items = items
  }
  push(el) { // 入栈
    this.items.push(el)
  }
  pop() { // 出栈
    return this.items.pop()
  }
  clear() { //清空
    this.items = []
  }

  get peek() { // 末位
    return this.items[this.items.length - 1]
  }
  get isEmpty() {
    return !this.items.length
  }
  get size() {
    return this.items.length
  }
}

2.队列

队列(Queue)：先进先出FIFO

class Queue {
  constructor(items = []) {
    this.items = items
  }
  addEl(el) { // 入队
    this.items.push(el)
  }
  delEl() { // 出队
    return this.items.shift()
  }
  clear() { // 清空
    this.items = []
  }

  get header() { // 首位
    return this.items[0]
  }
  get isEmpty() {
    return !this.items.length
  }
  get size() {
    return this.items.length
  }
}

2.1 优先队列

优先队列是队列的变种，由项的priority的值决定其在队列中的优先级

class PriorityQueue extends Queue {
  constructor(items) {
    super(items)
  }
  addEl(el, priority) { // priority越小优先级越高
    const queueEl = { el, priority }
    let preIndex = this.items.findIndex(item => item.priority > queueEl.priority)
    if (preIndex > -1) this.items.splice(preIndex, 0, queueEl)
    else this.items.push(queueEl)
  }
}

2.2 循环队列

循环队列是队列的另一个变种，可以实现队列索引循环

class LoopQueue extends Queue {
  constructor(items) {
    super(items)
  }
  getIndex(index) {
    return index < this.size ? index : (index % this.size)
  }
  find(index) {
    return this.items[this.getIndex(index)]
  }
}

3.链表

链表(LinkedList)：每个元素都有一个next保存下一个元素的指针，第一个元素为head，如下图所示：

class LinkedList {
  constructor() {
    this.head = null
    this.length = 0
  }
  static createNode(el) {
    const node = {}
    node.el = el
    node.next = null
    return node
  }
  append(el) { // 添加
    const node = LinkedList.createNode(el)
    if (!this.head) this.head = node
    else {
      let preNode = this.head
      while (preNode.next) preNode = preNode.next
      preNode.next = node
    }
    this.length++
  }
  insert(index, el) { // 插入
    if (index >= 0 && index <= this.size) {
      const node = LinkedList.createNode(el)
      let curEl = this.head
      if (index === 0) {
        this.head = node
        node.next = curEl
      }
      else {
        let curIndex = 0
        while (curIndex++ != index) {
          preEl = curEl
          curEl = curEl.next
        }
        preEl.next = node
        node.next = curEl
      }
      this.length++
      return true
    }
    return false
  }
  removeAt(index) {
    if (index >= 0 && index < length) {
      let curEl = this.head
      if (index === 0) {
        this.head = curEl.next
      }
      else {
        let preEl = null
        let curIndex = 0
        while (curIndex++ != index) {
          preEl = curEl
          curEl = curEl.next
        }
        preEl.next = curEl.next
      }
      this.length--
      return curEl.el
    }
    return null
  }
  remove(el) {
    return this.removeAt(this.findIndex(el))
  }
  findIndex(el) {
    let curEl = this.head
    let index = 0
    while (curEl) {
      if (el === curEl.el) return index
      curEl = curEl.next
      index++
    }
    return index > this.size - 1 ? -1 : index
  }
  selectNode(cb) { // 筛选
    let curNode = this.head
    while (curNode) {
      if (cb(curNode.el)) return curNode
      curNode = curNode.next
    }
    return null
  }
  get isEmpty() {
    return !this.length
  }
  get size() {
    return this.length
  }
}

3.1 双向链表

指定最后一个元素为end，

class DoublyLinkedList extends LinkedList {
  constructor() {
    super()
    this.end = null
  }
  insert(el, index) {
    if (index >= 0 && index <= this.size) {
      const node = super.createNode(el)
      let curNode = this.head
      let curIndex = 0
      if (index == 0) { // 首位
        if (!this.head) {
          this.head = node
          this.end = node
        } else {
          this.head = node
          node.next = curNode
          curNode.pre = node
        }
      }
      else if (index == this.size) { // 末位
        curNode = this.end
        this.end = node
        curNode.next = node
        node.pre = curNode
      }
      else { // 中间
        while (curIndex++ != index) {
          curNode = curNode.next
        }
        let preNode = curNode.pre
        preNode.next = curNode.pre = node
        node.pre = preNode
        node.next = curNode
      }
      this.length++
      return true
    }
    return false
  }
}
// 循环链表、双向循环链表（略）

4.集合

集合(set)：每一个元素形如{value:value}，无key，每个元素都是唯一的

class Set {
  constructor() {
    this.items = {}
  }
  has(value) {
    return this.items.hasOwnProperty(value)
  }
  add(value) {
    if (!this.has(value)) { // 保证唯一
      this.items[value] = value
      return true
    }
    return false
  }
  remove(value) {
    if (this.has(value)) {
      delete this.items[value]
      return true
    }
    return false
  }
  get size() {
    return Object.keys(this.items).length
  }
  get isEmpty() {
    return !this.size
  }
  get values() {
    return Object.keys(this.items)
  }
  union(set) { // 并集
    let res = new Set()
    this.values.forEach((key, val) => res.add(val))
    set.values.forEach((key, val) => res.add(val))
    return res
  }
  intersection(set) { // 交集
    let res = new Set()
    this.values.forEach((key, val) => set.has(val) && res.add(val))
    return res
  }
  difference(set) { // 差集
    let res = new Set()
    this.values.forEach((key, val) => !set.has(val) && res.add(val))
    return res
  }
  isSubsetOf(set) { // 子集
    return this.size <= set.size && this.values.every((key, val) => set.has(val))
  }
}

5.字典

字典(Dictionary)：每一个元素形如{ key: value }，且能保证每个key-value是唯一的

class Dictionary {
  constructor(){
    this.items = {}
  }
  set(key,val){
    this.items[key] = val
    return this // 链式调用
  }
  get(key){
    return this.items[key]
  }
  remove(key){
    delete this.items[key]
    return this
  }
  get keys(){
    return Object.keys(this.items)
  }
  get values(){
    return Object.values(this.items) // ES7
    // **
    return Object.keys(this.items).reduce((pre,cur)=>{
       pre.push(this.items[cur])
       return pre
     },[])
    // **
  }
}

6.哈希表

哈希表(HashTable)：使用hash值代替key，使用[]代替{key:value}，从而避免遍历整个数据结构来达到最快取值的功能，典型的牺牲空间换取时间，如下图所示：

class HashTable {
  constructor() {
    this.table = []
  }
  static key2Hash(key) {
    let hash = 0
    for (let code of key) hash += code.charCodeAt()
    return hash % 37
  }

  put(key, val) {
    this.table[HashTable.key2Hash(key)] = val
  }
  get(key) {
    return this.table[HashTable.key2Hash(key)]
  }
  remove(key) {
    this.table[HashTable.key2Hash(key)] = undefined
  }
}

6.1 哈希值重复的冲突解决

使用哈希表有一个潜在的问题，那就是使用hash值代替key值时，有时候可能不同的key值会得到相同的hash值，例如'az'和'by'，这里介绍三种解决方法

6.1.1 链地址法

核心思想：链表+哈希表，哈希表项以链表结构存储，

class HashTable{
  constructor(){
    this.table = []
  }
  static key2Hash(key){
    let hash = 0
    for(let code of key) hash += code.charCodeAt()
    return hash%37
  }
  put(key,val){
    const hash = HashTable.key2Hash(key)
    if(this.table[hash]===undefined) this.table[hash] = new LinkedList()
    this.table[hash].append({key,val})
  }
  get(key){
    const hash = HashTable.key2Hash(key)
    let linkList = this.table[hash]

    return linkList===undefined? undefined :linkList.selectNode(node=>Object.is(node.key,key))
    // function getNodeVal(node){
    //   if(!node||!node.el) return undefined // 到末位
    //   if(Object.is(node.el.key,key)) return node.el.value
    //   return getNodeVal(node.next)
    // }
    // return getNodeVal(linkList.head)
  }

  remove(key){
    const hash = HashTable.key2Hash(key)
    let linkList =this.table[hash]

    if(linkList===undefined) return undefined
    const node = linkList.selectNode(node=>Object.is(node.key,key))
    return linkList.remove(node)

    // function removeNodeVal(node) {
    //   if(!node||!node.el) return false // 到末位
    //   if(Object.is(node.el.key,key)){
    //     linkList.remove(node.el)
    //     if(linkList.isEmpty) this.table[hash] = undefined // 由于指针的原因，这里要使用this.table[hash]
    //     return true
    //   }
    //   return removeNodeVal(node)
    // }
    // return removeNodeVal(linkList.head)
  }
}

6.1.2 线性探查

核心思想：若存在重复的hash值，则hash++，直到没有重复

class HashTable{
  constructor(){
    this.table = []
  }
  static key2Hash(key){
    let hash = 0
    for(let code of key) hash += code.charCodeAt()
    return hash%37
  }
  put(key,value){
    const hash = HashTable.key2Hash(key)
    while (this.table[hash]!==undefined){
      if(Object.is(this.table[hash].key,key)) return // 唯一key
      hash++
    }
    this.table[hash] = {key,value}
  }
  get(key){
    const hash = HashTable.key2Hash(key)
    while(this.table[hash]){
      if(Object.is(this.table[hash].key,key)) return this.table[hash].value
      hash++    
    }
    return undefined
  }
  remove(key){
    const hash = HashTable.key2Hash(key)
    while(this.table[hash]){
      if(Object.is(this.table[hash].key,key)){
        this.table[hash] =undefined
        return true
      }
      hash++
    }
    return false
  }
}

6.1.3 优化key2Hash算法

降低hash值重复率

 static key2Hash(key){
   let hash = 0
   for(let code of key) hash += code.charCodeAt()
   return hash%37
 }
// 改进，hash重复率更低，也可以插入时间戳
 static key2Hash2(key) { 
   let hash = 5381
   for (let code of key) hash = hash * 33 + code.charCodeAt()
   return hash % 1013
 }

7.树

7.0 二叉搜索树

二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点 二叉搜索树(BST，Binary Search Tree)是二叉树的一种，在左侧节点存储（比父节点）小的值， 在右侧节点存储（比父节点）大（或者等于）的值，结构如下图所示

class BinarySearchTree {
  constructor() {
    this.root = null
  }
  static getNode(key) {
    const node = {}
    node.key = key
    node.left = null
    node.right = null
    return node
  }
  insert(key) {
    const newNode = BinarySearchTree.getNode(key)
    if (!this.root) return this.root = newNode
    function insetNode(node, newNode) {
      if (newNode.key < node.key) { // left
        if (node.left == null) return node.left = newNode
        else arguments.callee(node.left, newNode)
      }
      else { // right
        if (node.right === null) return node.right = newNode
        else arguments.callee(node.right, newNode)
      }
    }
    insetNode(this.root, newNode)

    //** 用while循环代替递归函数
    let curNode = this.root
    let key = newNode.key
    let direction = key < curNode.key ? 'left' : 'right'
    while (curNode[direction]) {
      curNode = curNode[direction]
      direction = key < curNode.key ? 'left' : 'right'
    }
    curNode[direction] = newNode
    //**
  }
}

创建二叉树

const tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(5)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)

结构如下，自己看

7.1 树的遍历

遍历一颗树是指访问树的每个节点并对它们进行某种操作（这里操作这个词翻译成编程术语就是cb回调）的过程，有三种方式：中序、先序、后序

7.1.1 中序

中序遍历是一种以上行（即最小到最大）的顺序访问BST所有节点的遍历方式

class BinarySearchTree {
  // ...
  inOrderTranverse(node = this.root, cb) {
    if (!node) return
    arguments.callee(node.left)
    cb(node.key)
    arguments.callee(node.right)
  }
}

// 中序遍历可以用于排序
let arr = []
tree.inOrderTranverse(undefined,node=>arr.push(node))
console.log(arr) // [3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 25]

过程如下

7.1.2 先序

先序遍历是以优先于后代节点的顺序访问每个节点

class BinarySearchTree{
  // ...
  preOrderTraverse(cb){
    if (!node) return
    cb(node.key)
    arguments.callee(node.left)
    arguments.callee(node.right)
  }
}

过程如下

7.1.3 后序

后序遍历则是先访问节点的后代节点，再访问节点本身，与先序正好相反

class BinarySearchTree{
  // ...
  postOrderTraverse(cb){
    if (!node) return
    arguments.callee(node.left)
    arguments.callee(node.right)
    cb(node.key)
  }
}

过程如下，自己看

7.2 节点操作

7.2.1 搜索最大值和最小值

前面说过了二叉搜索树的特点就是小的放左边，大的放右边

min(node=this.root){
  while(node.left) node = node.left
  return node
  
  //**
  function getMin(node){
    if(node.left) return getMin(node.left)
    else return node
  }
  getMin(node)
  //**
}

max(node=this.root){
  while(node.right) node = node.right
  return node
}

7.2.2 搜索特定节点

search(key){
  let curNode = this.root
  while (curNode.key != key) {
    if(!node) return false
    
    if (key < curNode.key) curNode = curNode.left
    else curNode = curNode.right
  }
  return curNode

  //**
  function searchNode(node, key) {
    if (!node) return false
    if (node.key == key) return node

    if (key < node.key) return searchNode(node.left, key)
    else return searchNode(node.right, key)
  }
  searchNode(this.root, key)
  //**
}

7.2.3 移除特定节点

removeNode(node = this.root, key) {
  if (!node) return
  if (key < node.left) return this.removeNode(node.left, key)
  if (key > node.right) return this.removeNode(node.right, key)

  // 当前key相同
  if (!node.left) return node = node.right // 无左节点
  if (!node.right) return node = node.left // 无右节点

  // 左右节点都有
  let nodeClone = node.right
  while (nodeClone && nodeClone.left) nodeClone = nodeClone.left
  node.key = nodeClone.key // 设置为右节点中的最小节点
  removeNode(node.right, nodeClone.key) // 将右节点中的最小节点置null
}

AVL树，RB树(todo)

8.图

class Graph{
  constructor(vertices=[]){
    if(Object.prototype.toString.call(vertices)!=='[object Array]') throw new Error(`只能传数组噢`)
    this.vertices=vertices
    this.adjList = new Dictionary() // 邻接表
    this.vertices.forEach(v=>this.adjList.set(v,[]))
  }
  addVertex(v){
    this.vertices.push(v)
    this.adjList.set(v,[])
  }
  addEdge(v,w){
    this.adjList.get(v).push(w)
    this.adjList.get(w).push(v)
  }
  toString(){
    return this.vertices.reduce((pre,cur)=>{
      return this.adjList.get(cur).reduce((pre,cur)=>{
        return  `${pre} ${cur}`
      },`${pre}\n${cur}:`)
    },'')

    //** 以下可以增加代码维护难度 (若你老板对你不好，可以这样写)
    return this.vertices.reduce((pre,cur)=>this.adjList.get(cur).reduce((pre,cur)=>`${pre} ${cur}`,`${pre}\n${cur}`),'')
    //**
  }

创建树

const graph = new Graph(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'])
graph.addEdge('A', 'B')
graph.addEdge('A', 'C')
graph.addEdge('A', 'D')
graph.addEdge('C', 'D')
graph.addEdge('C', 'G')
graph.addEdge('D', 'G')
graph.addEdge('D', 'H')
graph.addEdge('B', 'E')
graph.addEdge('B', 'F')
graph.addEdge('E', 'I')
console.log(''+graph)
/**
 *  A: B C D
 *  B: A E F
 *  C: A D G
 *  D: A C G H
 *  E: B I
 *  F: B
 *  G: C D
 *  H: D
 *  I: E
 */

8.1 图遍历

图遍历算法的思想是：先指定第一次被访问的节点，并且追踪其下还有哪些节点还没有被完全探索 有两种遍历算法：广度优先搜索(Breadth-First Search，BFS)、深度优先搜索(Depth-First Search，DFS)

8.1.1 广度优先搜索

广度优先搜索(Breadth-First Search，BFS)是先宽后深地访问节点，实现思想：维护两个队列，分别用于存储已读和待读节点，两者具有互斥性，不断递归访问相邻的节点和同时标为已读

class Graph{
  // ...
  bfs(v,cb){
    const readList = [] // 已读队列
    const adjList = this.adjList
    let pending = [v||this.vertices[0]] // 待读队列
    while (pending.length) {
      let key = pending.shift()
      readList.push(key)
      cb&&cb(key)
      adjList.get(key).forEach(v=>{
        if(!readList.includes(v)&&!pending.includes(v)){ // 互斥，保证只读一遍
          pending.push(v)
        }
      })
    }
    //** 下面是另一种方法（我个人还是喜欢用while循环来代替递归，递归会浪费函数作用域内存，而且不优雅）
    ;(function read(vertices) {
      vertices.forEach(key=>{
        readList.push(pending.shift())
        cb&&cb(key)
        adjList.get(key).forEach(v=>{
          if(!pending.includes(v)&&!readList.includes(v)){ // 互斥，保证只读一遍
            pending.push(v)
          }
        })
        pending.length&&read(pending)
      })
    })(pending)
    //**
    }
  }
}

遍历看看

/**
 *  graph邻接表
 *  A: B C D
 *  B: A E F
 *  C: A D G
 *  D: A C G H
 *  E: B I
 *  F: B
 *  G: C D
 *  H: D
 *  I: E
 */
 
graph.bfs(null,v=>console.log(v)) // A B C D E F G H I

使用广度搜索计算到各节点到顶点的最短路径

class Graph{
  // ...
  bfs(v,cb){
    const readList = [] 
    const distances = []
    const predecessors = []
    const adjList = this.adjList
    let pending = [v||this.vertices[0]]
    while (pending.length) {
      let key = pending.shift()
      cb&&cb(key)
      readList.push(key)
      distances[key] = distances[key] || 0
      predecessors[key] = predecessors[key]||null
      adjList.get(key).forEach(v=>{
        if(!readList.includes(v)&&!pending.includes(v)){
          pending.push(v)
          distances[v] = distances[key]+1
          predecessors[v] = key
        }
      })
    }
    return {distances,predecessors}
  }
  getAllPath(fromV) {
    let res = Object.create(null)
    fromV = fromV || this.vertices[0]
    const vertices = this.vertices
    const { distances,predecessors } = this.bfs(fromV)
    vertices.forEach(toV=>{
      if(!!distances[toV]){
        let preV = predecessors[toV]
        let curPath = `${toV}`
        while (fromV!==preV) {
          curPath =`${preV} => ${curPath}`
          preV = predecessors[preV]
        }
        curPath = `${fromV} => ${curPath}`
        res[toV] = curPath
      }
    })
    return res
  }
}

/**
 *  graph邻接表
 *  A: B C D
 *  B: A E F
 *  C: A D G
 *  D: A C G H
 *  E: B I
 *  F: B
 *  G: C D
 *  H: D
 *  I: E
 */
  
console.log(graph.bfs())
// distances: [A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2 , I: 3]
// predecessors: [A: null, B: "A", C: "A", D: "A", E: "B", F: " B", G: " C", H: "D", I: "E"]
console.log(graph.getAllPath())
/**
 * B: "A => B"
 * C: "A => C"
 * D: "A => D"
 * E: "A => B => E"
 * F: "A => B => F"
 * G: "A => C => G"
 * H: "A => D => H"
 * I: "A => B => E => I"
 * 
 */

8.1.2 深度优先搜索

深度优先搜索(Depth-First Search，DFS)是先深后宽，实现思想：从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶 点被访问了，接着原路回退并探索下一条路径，维护一个已读队列即可

class Graph{
  // ...
  dfs(cb){
    const readList = []
    const adjList =this.adjList
    const len = this.vertices.length
    function read(vertices){
      vertices.forEach(key=>{
        if(readList.includes(key)) return 
        readList.push(key)
        cb&&cb(key)
        if(readList.length!==len) read(adjList.get(key))
      })
    }
    read(this.vertices)
  }
}
/**
 *  graph邻接表
 *  A: B C D
 *  B: A E F
 *  C: A D G
 *  D: A C G H
 *  E: B I
 *  F: B
 *  G: C D
 *  H: D
 *  I: E
 */
graph.dfs(val=>console.log(val)) // A B E I F C D G H

优化，加入前导节点标记predecessors、遍历节点开始时所在轮次readTimes和遍历完所有子节点所在轮次finishedTimes

class Graph{
  dfs(cb){
    const readList = []
    const adjList =this.adjList
    const len = this.vertices.length

    let readT = 0
    const finishedTimes = Object.create(null)
    const readTimes = Object.create(null)
    const predecessors = Object.create(null)
    function read(vertices,predecessor){
      vertices.forEach(key=>{
        readT++
        if(adjList.get(key).every(v=>readList.includes(v))&&!finishedTimes[key]){
          finishedTimes[key] = readT // 完成遍历某节点的所有邻接点
        }
        if(readList.includes(key)) return 
        readTimes[key] = readT
        readList.push(key)
        cb&&cb(key)
        predecessors[key] = predecessors[key] || predecessor || null
        if(readList.length!==len) read(adjList.get(key),key)
      })
    }
    read(this.vertices)
    return { readTimes, finishedTimes, predecessors }
  }
}
/**
 *  graph邻接表
 *  A: B C D
 *  B: A E F
 *  C: A D G
 *  D: A C G H
 *  E: B I
 *  F: B
 *  G: C D
 *  H: D
 *  I: E
 */
console.log(graph.dfs())
// readTimes: {A: 1, B: 2, C: 10, D: 12, E: 4, F: 8, G: 15, H: 18, I: 6 }   第2轮开始遍历到B节点
// finishedTimes: {A: 13, B: 9, C: 16, D: 20, E: 7, F: 8, G: 15, H: 18, I: 6 } 第9轮 "确认" 遍历完B节点下的所有子节点(这里的确认即这轮不再遍历下去，而是跳过)
// predecessors: {A: null, B: 'A', C: 'A', D: 'C', E: 'B', F: 'B', G: 'D', H: ''D', I: 'E'}

参考

1.《在 JavaScript 中学习数据结构与算法》 (opens new window)