JavaScript 数据结构

JavaScript 数据结构
持续更新

队列

• push(element): 在队尾压入新元素，并返回数组长度
• pop(): 删除队列首元素并返回其值
• front(): 返回队首元素的值，但不删除该元素
• end(): 返回队列尾元素的值，但不删除该元素
• empty(): 如果队列为空返回 true，否则返回 false
• clear(): 清空队列
• size(): 返回队列中元素的个数

class Queue {
  constructor() {
    this.queue = []
    this.length = -1
  }
  push(item) {
    // 在队尾压入新元素, 并返回数组长度
    this.length++
    this.queue.push(item)
    return this.size()
  }
  pop() {
    // 删除队列首元素并返回其值
    return this.queue.shift()
  }
  front() {
    // 返回队首元素的值，但不删除该元素
    if (this.empty()) return undefined
    return this.queue[0]
  }
  end() {
    // 返回队列尾元素的值，但不删除该元素
    if (this.empty()) return undefined
    return this.queue[this.length]
  }
  empty() {
    // 如果队列为空返回 true，否则返回 false
    return this.length === -1
  }
  clear() {
    // 清空队列
    this.queue = []
    this.length = -1
  }
  size() {
    // 返回队列中元素的个数
    return this.length + 1
  }
}

栈

• push(element): 在栈顶压入新元素, 并返回数组长度
• pop(): 删除栈顶元素并返回其值
• front(): 返回栈顶元素的值，但不删除该元素
• end(): 返回栈底元素的值，但不删除该元素
• empty(): 如果栈为空返回 true，否则返回 false
• clear(): 清空栈
• size(): 返回栈中元素的个数

class Stack {
  constructor() {
    this.stack = []
    this.length = -1
  }
  push(item) {
    // 在栈顶压入新元素, 并返回数组长度
    this.length++
    this.queue.push(item)
    return this.size()
  }
  pop() {
    // 删除栈顶元素并返回其值
    return this.queue.pop()
  }
  front() {
    // 返回栈顶元素的值，但不删除该元素
    if (this.empty()) return undefined
    return this.queue[0]
  }
  end() {
    // 返回栈底元素的值，但不删除该元素
    if (this.empty()) return undefined
    return this.queue[this.length]
  }
  empty() {
    // 如果栈为空返回 true，否则返回 false
    return this.length === -1
  }
  clear() {
    // 清空栈
    this.queue = []
    this.length = -1
  }
  size() {
    // 返回栈中元素的个数
    return this.length + 1
  }
}

链表

• append(element)：向链表尾部添加一个新的项
• insert(position, element)：向链表的特定位置插入一个新的项。
• remove(element)：从链表中移除一项。
• indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回-1。
• removeAt(position)：从链表的特定位置移除一项。
• empty()：如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false。
• size()：返回链表包含的元素个数。
• toString()：由于链表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。

class Node {
  constructor(value = null, next = null) {
    this.value = value
    this.next = next
  }
}

class LinkList {
  constructor() {
    this.head = null
    this.length = -1
  }
  append(element) {
    // 向链表尾部添加一个新的项
    let node = new Node(element)
    if (this.head) {
      let current = this.head
      while (current.next) {
        current = current.next
      }
      current.next = node
    } else {
      this.head = node
    }
    this.length++
  }
  insert(position, element) {
    // 向链表的特定位置插入一个新的项。
    if (position < 0 || position > this.length + 1) return false
    let node = new Node(element)
    let parent = this.head
    let current = this.head
    let index = 0
    while (index++ < position) {
      parent = current
      current = current.next
    }
    if (position === 0) {
      node.next = this.head
      this.head = node
    } else {
      node.next = current
      parent.next = node
    }
    this.length++
    return true
  }
  remove(element) {
    // 从链表中移除一项。
    let index = this.indexOf(element)
    if (index === -1) return false
    return this.removeAt(index)
  }
  indexOf(element) {
    // 返回元素在链表中的索引。如果链表中没有该元素则返回-1。
    if (this.empty()) return -1
    let current = this.head
    let index = 0
    while (current) {
      if (current.value === element) return index
      index++
      current = current.next
    }
    return -1
  }
  removeAt(position) {
    // 从链表的特定位置移除一项。
    if (position < 0 || position > this.length) return false
    if (position === 0) {
      this.head = this.head.next
      this.length--
      return true
    }
    let parent = this.head
    let current = this.head
    let index = 0
    while (index++ < position) {
      parent = current
      current = current.next
    }
    parent.next = current.next
    this.length--
    return true
  }
  empty() {
    // 如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false。
    return this.length === -1
  }
  size() {
    // 返回链表包含的元素个数。
    return this.length + 1
  }
  toString() {
    // 由于链表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。
    let arr = []
    let current = this.head
    while (current) {
      arr.push(current.value)
      current = current.next
    }
    return arr.join(',')
  }
}

双向链表

• append(element)：向链表尾部添加一个新的项
• insert(position, element)：向链表的特定位置插入一个新的项。
• remove(element)：从链表中移除一项。
• indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回-1。
• removeAt(position)：从链表的特定位置移除一项。
• empty()：如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false。
• size()：返回链表包含的元素个数。与数组的 length 属性类似。
• toString()：由于链表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。

class DoubleNode {
  constructor(value = null, prev = null, next = null) {
    this.value = value
    this.prev = prev
    this.next = next
  }
}
class DoubleLink {
  constructor() {
    this.head = null // 指向第一个元素
    this.length = -1
    this.end = null // 指向最后一个元素
  }
  append(element) {
    // 向链表尾部添加一个新的项
    let node = new DoubleNode(element)
    if (this.head) {
      this.end.next = node
      node.prev = this.end
      this.end = node
    } else {
      this.head = node
      this.end = node
    }
    this.length++
  }
  insert(position, element) {
    // 向链表的特定位置插入一个新的项。
    if (position < 0 || position > this.length + 1) return false
    let node = new DoubleNode(element)
    let current = this.head
    let index = 0
    while (index++ < position) {
      current = current.next
    }
    if (position === 0) {
      node.next = this.head
      this.head.prev = node
      this.head = node
    } else if (current) {
      node.next = current
      current.prev.next = node
      current.prev = node
    } else {
      this.end.next = node
      node.prev = this.end
      this.end = node
    }
    this.length++
    return true
  }
  remove(element) {
    // 从链表中移除一项。
    let index = this.indexOf(element)
    if (index === -1) return false
    return this.removeAt(index)
  }
  indexOf(element) {
    // 返回元素在链表中的索引。如果链表中没有该元素则返回-1。
    if (this.empty()) return -1
    let current = this.head
    let index = 0
    while (current) {
      if (current.value === element) return index
      index++
      current = current.next
    }
    return -1
  }
  removeAt(position) {
    // 从链表的特定位置移除一项。
    if (position < 0 || position > this.length) return false
    if (position === 0) {
      this.head = this.head.next
      this.length--
      return true
    }
    let parent = this.head
    let current = parent.next
    let index = 0
    while (index < position) {
      index++
      parent = parent.next
      current = parent.next
    }
    parent.next = current.next
    this.length--
    return true
  }
  empty() {
    // 如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false。
    return this.length === -1
  }
  size() {
    // 返回链表包含的元素个数。
    return this.length + 1
  }
  toString() {
    // 由于链表项使用了 DoubleNode 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。
    let arr = []
    let current = this.head
    while (current) {
      arr.push(current.value)
      current = current.next
    }
    return arr.join(',')
  }
}

集合

• insert(element): 插入一个元素
• remove(element): 删除一个元素
• has(element): 判断元素是否在集合中
• size(): 删除一个元素
• clear(): 清空集合
• values(): 返回组成的数组

class Set {
  constructor() {
    this.sets = []
    this.length = -1
  }
  insert(element) {
    // 插入一个元素
    if (!this.has(element)) return
    this.sets.push(element)
    this.length++
  }
  remove(element) {
    // 删除一个元素
    if (!this.has(element)) return
    this.sets = this.filter((e) => e !== element)
    this.length--
  }
  has(element) {
    if (this.length === -1) return false
    // 判断元素是否在集合中
    for (let i = 0; i < this.length; i++) {
      if (this.sets[i] === element) return true
    }
    return false
  }
  size() {
    // 删除一个元素
    return this.length + 1
  }
  clear() {
    // 清空集合
    this.sets = []
    this.length = -1
  }
  values() {
    // 返回组成的数组
    return this.sets
  }
}

字典

• set(key,value)：向字典中添加新元素。
• remove(key)：通过使用键值来从字典中移除键值对应的数据值。
• has(key)：如果某个键值存在于这个字典中，则返回 true，反之则返回 false。
• get(key)：通过键值查找特定的数值并返回。
• clear()：将这个字典中的所有元素全部删除。
• size()：返回字典所包含元素的数量。与数组的 length 属性类似。
• keys()：将字典所包含的所有键名以数组形式返回。
• values()：将字典所包含的所有数值以数组形式返回。

class Dictionay {
  constructor() {
    this.items = {}
    this.length = -1
  }
  set(key, value) {
    // 向字典中添加新元素。
    this.items[key] = value
    this.length++
  }
  remove(key) {
    // 通过使用键值来从字典中移除键值对应的数据值。
    if (this.has(key)) {
      delete this.items[key]
      this.length--
      return true
    }
    return false
  }
  has(key) {
    // 如果某个键值存在于这个字典中，则返回true，反之则返回false。
    return Object.prototype.hasOwnProperty.call(this.items, key)
  }
  get(key) {
    // 通过键值查找特定的数值并返回。
    if (this.has(key)) {
      return this.items[key]
    }
    return undefined
  }
  clear() {
    // 将这个字典中的所有元素全部删除。
    this.items = {}
    this.length = -1
  }
  size() {
    // 返回字典所包含元素的数量。与数组的length属性类似。
    return this.length + 1
  }
  keys() {
    // 将字典所包含的所有键名以数组形式返回。
    return Object.keys(this.items)
  }
  values() {
    // 将字典所包含的所有数值以数组形式返回。
    return Object.values(this.items)
  }
}

哈希表

• put(key, value): 添加元素
• get(key): 获取存放的数据
• resize(length): 哈希表扩容
• remove(key)：删除元素
• empty()：是否为空
• size(): 哈希表的长度

class HashTable {
  constructor(ratio = 0.75) {
    this.length = 5
    this.count = 0 // 内容长度
    this.table = []
    this.ratio = ratio
  }
  put(key, value) {
    if (typeof key !== 'string') key = String(key)
    // 添加元素
    let hash = this.hashFunc(key, this.length)
    let bucket = this.table[hash]
    if (!bucket) {
      bucket = []
      this.table[hash] = bucket
    }

    let override = false // 是否是覆盖操作
    for (let i = 0; i < bucket.length; i++) {
      const element = bucket[i]
      if (element[0] === key) {
        element[1] = value
        override = true
      }
    }
    if (!override) {
      bucket.push([key, value])
      this.count++
      if (this.count > this.length * this.ratio) {
        this.resize(this.getPrime(this.length + 1))
      }
    }
  }
  get(key) {
    if (typeof key !== 'string') key = String(key)
    // 获取存放的数据
    let hash = this.hashFunc(key, this.length)
    let bucket = this.table[hash]
    if (!bucket) bucket = []
    for (let i = 0; i < bucket.length; i++) {
      const element = bucket[i]
      if (element[0] === key) return element[1]
    }
    return null
  }
  remove(key) {
    if (typeof key !== 'string') key = String(key)
    // 删除元素
    let hash = this.hashFunc(key, this.length)
    let bucket = this.table[hash]
    if (!bucket) return null
    for (let i = bucket.length - 1; i >= 0; i--) {
      const element = bucket[i]
      if (element[0] === key) {
        let e = bucket.splice(i, 1)
        this.count--
        // 缩小数组的容量
        if (this.length > 0 && this.count < this.length * (1 - this.ratio)) {
          this.resize(this.getPrime(Math.floor(this.length / 2)))
        }
        return e
      }
    }
    return null
  }
  empty() {
    // 是否为空
    return this.size === 0
  }
  size() {
    // 哈希表的长度
    return this.count
  }
  hashFunc(str, max) {
    // 计算 hash 值
    let hash = 0
    for (let i = 0; i < str.length; i++) {
      hash = hash * 37 + str.charCodeAt(i)
    }
    hash = hash % max
    return hash
  }
  isPrime(num) {
    // 判断是否是 质数
    for (let i = 2; i <= Math.floor(Math.sqrt(num)); i++) {
      if (num % i === 0) return false
    }
    return true
  }
  getPrime(num) {
    // 获取质数
    while (!this.isPrime(num)) {
      num++
    }
    return num
  }
  resize(length) {
    // 哈希表扩容
    let oldTable = this.table
    this.length = length
    this.count = 0
    this.table = []
    oldTable.forEach((bucket) => {
      if (bucket) {
        for (let i = 0; i < bucket.length; i++) {
          this.put(bucket[i][0], bucket[i][1])
        }
      }
    })
  }
}

树

二叉树

• insert(value)：向树中插入一个新的键。
• search(value)：在树中查找一个键，如果结点存在，则返回 true；如果不存在，则返回 false。
• inOrderTraverse：通过中序遍历方式遍历所有结点。
• preOrderTraverse：通过先序遍历方式遍历所有结点。
• postOrderTraverse：通过后序遍历方式遍历所有结点。
• min：返回树中最小的值/键。
• max：返回树中最大的值/键。
• remove(value)：从树中移除某个键。

class TreeNode {
  constructor(value = null, left = null, right = null) {
    this.value = value
    this.left = left
    this.right = right
  }
}

class BinaryTree {
  constructor() {
    this.head = null
    this.left = null
    this.right = null
  }
  insert(value) {
    // 向树中插入一个新的键。
    const node = new TreeNode(value)
    if (!this.head) {
      this.head = node
      return
    }
    let current = this.head
    let parent = this.head
    let isRight = true
    while (current) {
      parent = current
      if (value > current.value) {
        current = current.right
        isRight = true
      } else {
        current = current.left
        isRight = false
      }
    }
    if (isRight) {
      parent.right = node
    } else {
      parent.left = node
    }
  }
  search(value) {
    // 在树中查找一个键，如果结点存在，则返回 true；如果不存在，则返回 false。
    if (!this.head) return false
    let current = this.head
    while (current) {
      if (current.value === value) return true
      else if (value > current.value) current = current.right
      else current = current.left
    }
    return false
  }
  inOrderTraverse(fn) {
    // 通过中序遍历方式遍历所有结点。
    let result = []
    if (typeof fn !== 'function')
      fn = function(result) {
        return result.join()
      }
    function traverse(node) {
      if (!node) return
      traverse(node.left)
      result.push(node.value)
      traverse(node.right)
    }
    traverse(this.head)
    return fn(result) || ''
  }
  preOrderTraverse(fn) {
    // 通过先序遍历方式遍历所有结点。
    let result = []
    if (typeof fn !== 'function')
      fn = function(result) {
        return result.join()
      }
    function traverse(node) {
      if (!node) return
      result.push(node.value)
      traverse(node.left)
      traverse(node.right)
    }
    traverse(this.head)
    return fn(result) || ''
  }
  postOrderTraverse(fn) {
    // 通过后序遍历方式遍历所有结点。
    let result = []
    if (typeof fn !== 'function')
      fn = function(result) {
        return result.join()
      }
    function traverse(node) {
      if (!node) return
      traverse(node.left)
      traverse(node.right)
      result.push(node.value)
    }
    traverse(this.head)
    return fn(result) || ''
  }
  min() {
    // 返回树中最小的值/键。
    let current = this.head
    if (current) {
      while (current.left) {
        current = current.left
      }
      return current.value
    }
    return null
  }
  max() {
    // 返回树中最大的值/键。
    let current = this.head
    if (current) {
      while (current.right) {
        current = current.right
      }
      return current.value
    }
    return null
  }
  remove(value) {
    // 从树中移除某个键。
    let current = this.head
    let parent = this.head
    let isRight = false
    while (current) {
      if (current.value === value) break
      parent = current
      if (value > current.value) {
        isRight = true
        current = current.right
      } else {
        isRight = false
        current = current.left
      }
    }
    // 没有找到要删除的元素
    if (!current) return false

    if (!current.left && !current.right) {
      // 叶子节点
      if (current === this.head) this.head = null
      // 根节点
      else if (isRight) parent.right = null
      else parent.left = null
    } else if (current.left && !current.right) {
      // 只有左节点
      if (current === this.head) this.head = this.head.left
      // 根节点
      else if (isRight) parent.right = current.left
      else parent.left = current.left
    } else if (current.right && !current.left) {
      // 只有右节点
      if (current === this.head) this.head = this.head.right
      // 根节点
      else if (isRight) parent.right = current.right
      else parent.left = current.right
    } else {
      // 有两个节点
      // 找右子树最小值
      let child = current.right
      let par = current.right
      while (child.left) {
        par = child
        child = child.left
      }
      if (par === child) {
        // current.right 没有左子树(区别于下面这种情况)
        if (isRight) {
          parent.right = child
          child.left = current.left
        } else {
          parent.left = child
          child.left = current.left
        }
        if (current === this.head) this.head = child // 根节点
      } else if (!child.left && child.right) {
        // 找到的节点只有右子树
        par.left = child.right
        child.right = current.right
        child.left = current.left
        if (isRight) parent.right = child
        else parent.left = child

        if (current === this.head) this.head = child
      } else {
        // 找到的节点是叶子节点
        par.left = null
        child.right = current.right
        child.left = current.left
        if (isRight) parent.right = child
        else parent.left = child

        if (current === this.head) this.head = child
      }
    }
    return true
  }
}

图