计算机基础数据结构：数组、链表、栈、队列与树入门

数据结构的核心，是定义一种数据组织方式，并维护这种组织方式的性质。选择合适的数据结构，通常能让插入、删除、查找、遍历等操作更清晰、更高效。

线性结构概览

线性结构中的元素通常按顺序组织，常见代表有数组、链表、栈、队列和双端队列。

栈强调“最后进入的元素最先出来”，队列强调“最早进入的元素最先出来”，双端队列则允许从两端插入和删除。

栈：后进先出结构

栈是一种遵循后进先出原则的有序集合，也叫 LIFO，Last In First Out。新增元素和删除元素都发生在同一端，这一端叫栈顶，另一端叫栈底。

典型场景包括函数调用栈、浏览器历史记录、撤销操作、括号匹配、深度优先搜索等。

栈的常用操作

push(element)：向栈顶添加元素。
pop()：移除并返回栈顶元素。
peek()：返回栈顶元素，但不修改栈。
isEmpty()：判断栈是否为空。
clear()：清空栈。
size()：返回栈中元素数量。

栈的数组实现

javascript

1class Stack {2  constructor () {3    this.items = []4  }5 6  push (element) {7    this.items.push(element)8  }9 10  pop () {11    return this.items.pop()12  }13 14  peek () {15    return this.items[this.items.length - 1]16  }17 18  isEmpty () {19    return this.items.length === 020  }21 22  clear () {23    this.items = []24  }25 26  size () {27    return this.items.length28  }29}class Stack {
  constructor () {
    this.items = []
  }

  push (element) {
    this.items.push(element)
  }

  pop () {
    return this.items.pop()
  }

  peek () {
    return this.items[this.items.length - 1]
  }

  isEmpty () {
    return this.items.length === 0
  }

  clear () {
    this.items = []
  }

  size () {
    return this.items.length
  }
}

数组实现写法简单，但如果只需要暴露栈操作，最好不要让外部直接访问内部数组。

栈的对象实现

javascript

1class ObjectStack {2  constructor () {3    this.count = 04    this.items = {}5  }6 7  push (element) {8    this.items[this.count] = element9    this.count++10  }11 12  pop () {13    if (this.isEmpty()) return undefined14 15    this.count--16    const result = this.items[this.count]17    delete this.items[this.count]18    return result19  }20 21  peek () {22    if (this.isEmpty()) return undefined23    return this.items[this.count - 1]24  }25 26  isEmpty () {27    return this.count === 028  }29 30  clear () {31    this.items = {}32    this.count = 033  }34 35  size () {36    return this.count37  }38}class ObjectStack {
  constructor () {
    this.count = 0
    this.items = {}
  }

  push (element) {
    this.items[this.count] = element
    this.count++
  }

  pop () {
    if (this.isEmpty()) return undefined

    this.count--
    const result = this.items[this.count]
    delete this.items[this.count]
    return result
  }

  peek () {
    if (this.isEmpty()) return undefined
    return this.items[this.count - 1]
  }

  isEmpty () {
    return this.count === 0
  }

  clear () {
    this.items = {}
    this.count = 0
  }

  size () {
    return this.count
  }
}

队列：先进先出结构

队列是一种遵循先进先出原则的有序集合，也叫 FIFO，First In First Out。元素从队尾进入，从队头离开。

典型场景包括任务排队、打印队列、消息队列、事件循环、广度优先搜索等。

队列的常用操作

enqueue(element)：向队尾添加元素。
dequeue()：移除并返回队头元素。
peek()：返回队头元素，但不修改队列。
isEmpty()：判断队列是否为空。
clear()：清空队列。
size()：返回队列中元素数量。

队列的对象实现

javascript

1class Queue {2  constructor () {3    this.count = 04    this.lowestCount = 05    this.items = {}6  }7 8  enqueue (element) {9    this.items[this.count] = element10    this.count++11  }12 13  dequeue () {14    if (this.isEmpty()) return undefined15 16    const result = this.items[this.lowestCount]17    delete this.items[this.lowestCount]18    this.lowestCount++19    return result20  }21 22  peek () {23    if (this.isEmpty()) return undefined24    return this.items[this.lowestCount]25  }26 27  isEmpty () {28    return this.size() === 029  }30 31  clear () {32    this.items = {}33    this.count = 034    this.lowestCount = 035  }36 37  size () {38    return this.count - this.lowestCount39  }40}class Queue {
  constructor () {
    this.count = 0
    this.lowestCount = 0
    this.items = {}
  }

  enqueue (element) {
    this.items[this.count] = element
    this.count++
  }

  dequeue () {
    if (this.isEmpty()) return undefined

    const result = this.items[this.lowestCount]
    delete this.items[this.lowestCount]
    this.lowestCount++
    return result
  }

  peek () {
    if (this.isEmpty()) return undefined
    return this.items[this.lowestCount]
  }

  isEmpty () {
    return this.size() === 0
  }

  clear () {
    this.items = {}
    this.count = 0
    this.lowestCount = 0
  }

  size () {
    return this.count - this.lowestCount
  }
}

队列和栈的主要区别在删除端：栈从栈顶删除，队列从队头删除。

双端队列：两端都可操作的队列

双端队列，Deque，允许从队头和队尾添加或移除元素。它既可以当普通队列使用，也可以当栈使用。

常见场景包括撤销与重做、回文检查、滑动窗口最大值、任务调度等。

双端队列的常用操作

addFront(element)：从队头添加元素。
addBack(element)：从队尾添加元素。
removeFront()：从队头移除元素。
removeBack()：从队尾移除元素。
peekFront()：查看队头元素。
peekBack()：查看队尾元素。

双端队列的对象实现

javascript

1class Deque {2  constructor () {3    this.count = 04    this.lowestCount = 05    this.items = {}6  }7 8  addFront (element) {9    if (this.isEmpty()) {10      this.addBack(element)11    } else if (this.lowestCount > 0) {12      this.lowestCount--13      this.items[this.lowestCount] = element14    } else {15      for (let i = this.count; i > 0; i--) {16        this.items[i] = this.items[i - 1]17      }18      this.count++19      this.items[0] = element20    }21  }22 23  addBack (element) {24    this.items[this.count] = element25    this.count++26  }27 28  removeFront () {29    if (this.isEmpty()) return undefined30 31    const result = this.items[this.lowestCount]32    delete this.items[this.lowestCount]33    this.lowestCount++34    return result35  }36 37  removeBack () {38    if (this.isEmpty()) return undefined39 40    this.count--41    const result = this.items[this.count]42    delete this.items[this.count]43    return result44  }45 46  peekFront () {47    if (this.isEmpty()) return undefined48    return this.items[this.lowestCount]49  }50 51  peekBack () {52    if (this.isEmpty()) return undefined53    return this.items[this.count - 1]54  }55 56  isEmpty () {57    return this.size() === 058  }59 60  size () {61    return this.count - this.lowestCount62  }63 64  clear () {65    this.items = {}66    this.count = 067    this.lowestCount = 068  }69}class Deque {
  constructor () {
    this.count = 0
    this.lowestCount = 0
    this.items = {}
  }

  addFront (element) {
    if (this.isEmpty()) {
      this.addBack(element)
    } else if (this.lowestCount > 0) {
      this.lowestCount--
      this.items[this.lowestCount] = element
    } else {
      for (let i = this.count; i > 0; i--) {
        this.items[i] = this.items[i - 1]
      }
      this.count++
      this.items[0] = element
    }
  }

  addBack (element) {
    this.items[this.count] = element
    this.count++
  }

  removeFront () {
    if (this.isEmpty()) return undefined

    const result = this.items[this.lowestCount]
    delete this.items[this.lowestCount]
    this.lowestCount++
    return result
  }

  removeBack () {
    if (this.isEmpty()) return undefined

    this.count--
    const result = this.items[this.count]
    delete this.items[this.count]
    return result
  }

  peekFront () {
    if (this.isEmpty()) return undefined
    return this.items[this.lowestCount]
  }

  peekBack () {
    if (this.isEmpty()) return undefined
    return this.items[this.count - 1]
  }

  isEmpty () {
    return this.size() === 0
  }

  size () {
    return this.count - this.lowestCount
  }

  clear () {
    this.items = {}
    this.count = 0
    this.lowestCount = 0
  }
}

集合：无序且唯一的数据结构

集合由一组无序且不重复的元素组成。它对应数学中的有限集合概念，适合处理去重、交集、并集、差集等问题。

JavaScript 原生提供了 Set，实际开发中优先使用原生实现。

集合的常用操作

add(value)：添加元素。
delete(value)：删除元素。
has(value)：判断元素是否存在。
clear()：清空集合。
size：返回集合大小。
values()：返回集合中的值。

集合的基础实现

javascript

1class CustomSet {2  constructor () {3    this.items = {}4  }5 6  has (value) {7    return Object.prototype.hasOwnProperty.call(this.items, value)8  }9 10  add (value) {11    if (this.has(value)) return false12    this.items[value] = value13    return true14  }15 16  delete (value) {17    if (!this.has(value)) return false18    delete this.items[value]19    return true20  }21 22  clear () {23    this.items = {}24  }25 26  size () {27    return Object.keys(this.items).length28  }29 30  values () {31    return Object.values(this.items)32  }33}class CustomSet {
  constructor () {
    this.items = {}
  }

  has (value) {
    return Object.prototype.hasOwnProperty.call(this.items, value)
  }

  add (value) {
    if (this.has(value)) return false
    this.items[value] = value
    return true
  }

  delete (value) {
    if (!this.has(value)) return false
    delete this.items[value]
    return true
  }

  clear () {
    this.items = {}
  }

  size () {
    return Object.keys(this.items).length
  }

  values () {
    return Object.values(this.items)
  }
}

集合的常见运算

javascript

1function union (setA, setB) {2  return new Set([...setA, ...setB])3}4 5function intersection (setA, setB) {6  return new Set([...setA].filter(value => setB.has(value)))7}8 9function difference (setA, setB) {10  return new Set([...setA].filter(value => !setB.has(value)))11}function union (setA, setB) {
  return new Set([...setA, ...setB])
}

function intersection (setA, setB) {
  return new Set([...setA].filter(value => setB.has(value)))
}

function difference (setA, setB) {
  return new Set([...setA].filter(value => !setB.has(value)))
}

字典：键值对映射结构

字典用于存储键值对，也叫映射、符号表或关联数组。集合更关注“值是否存在”，字典更关注“某个键对应什么值”。

JavaScript 中常用 Map 或普通对象实现字典。需要任意类型作为键时，优先使用 Map。

字典的常用操作

set(key, value)：添加或更新键值对。
remove(key)：通过键删除键值对。
hasKey(key)：判断键是否存在。
get(key)：根据键获取值。
clear()：清空字典。
size()：返回键值对数量。
keys()：返回所有键。
values()：返回所有值。
entries()：返回所有键值对。
forEach(callback)：遍历字典。

字典的基础实现

javascript

1class Dictionary {2  constructor () {3    this.table = {}4  }5 6  set (key, value) {7    if (key == null) return false8    this.table[key] = value9    return true10  }11 12  get (key) {13    return this.hasKey(key) ? this.table[key] : undefined14  }15 16  hasKey (key) {17    return Object.prototype.hasOwnProperty.call(this.table, key)18  }19 20  remove (key) {21    if (!this.hasKey(key)) return false22    delete this.table[key]23    return true24  }25 26  keys () {27    return Object.keys(this.table)28  }29 30  values () {31    return Object.values(this.table)32  }33 34  entries () {35    return Object.entries(this.table)36  }37 38  size () {39    return this.keys().length40  }41 42  clear () {43    this.table = {}44  }45}class Dictionary {
  constructor () {
    this.table = {}
  }

  set (key, value) {
    if (key == null) return false
    this.table[key] = value
    return true
  }

  get (key) {
    return this.hasKey(key) ? this.table[key] : undefined
  }

  hasKey (key) {
    return Object.prototype.hasOwnProperty.call(this.table, key)
  }

  remove (key) {
    if (!this.hasKey(key)) return false
    delete this.table[key]
    return true
  }

  keys () {
    return Object.keys(this.table)
  }

  values () {
    return Object.values(this.table)
  }

  entries () {
    return Object.entries(this.table)
  }

  size () {
    return this.keys().length
  }

  clear () {
    this.table = {}
  }
}

树结构概览

树是一种分层数据结构，由节点和边组成。最上层节点叫根节点，没有子节点的节点叫叶子节点，拥有子节点的节点叫内部节点。

常见术语：

根节点：树的起点。
父节点：直接连接某个节点的上一层节点。
子节点：直接连接某个节点的下一层节点。
兄弟节点：拥有同一个父节点的节点。
叶子节点：没有子节点的节点。
深度：从根节点到当前节点经过的边数。
高度：从当前节点到最远叶子节点经过的边数。

二叉树：最多两个子节点的树

二叉树中的每个节点最多只有两个子节点，通常称为左子节点和右子节点。

二叉树本身不要求节点有序。只有在二叉搜索树中，才要求左子树小于根节点、右子树大于根节点。

二叉搜索树 BST：可排序的二叉树

二叉搜索树是二叉树的一种，它要求每个节点满足：

左子树中的所有值小于当前节点。
右子树中的所有值大于当前节点。
左右子树本身也都是二叉搜索树。

这个性质让查找、插入、删除可以沿着一条路径进行，平均复杂度为 O(log n)。但如果数据接近有序，树可能退化成链表，复杂度会变成 O(n)。

BST 的常用操作

insert(key)：插入新键。
search(key)：查找键。
inOrderTraverse()：中序遍历，结果通常是升序。
preOrderTraverse()：先序遍历，适合复制树结构。
postOrderTraverse()：后序遍历，适合释放或删除树。
min()：查找最小值。
max()：查找最大值。
remove(key)：删除键。

BST 的 JavaScript 实现

javascript

1class TreeNode {2  constructor (key) {3    this.key = key4    this.left = null5    this.right = null6  }7}8 9class BinarySearchTree {10  constructor () {11    this.root = null12  }13 14  insert (key) {15    const newNode = new TreeNode(key)16 17    if (this.root === null) {18      this.root = newNode19      return20    }21 22    let current = this.root23    while (current) {24      if (key < current.key) {25        if (current.left === null) {26          current.left = newNode27          return28        }29        current = current.left30      } else {31        if (current.right === null) {32          current.right = newNode33          return34        }35        current = current.right36      }37    }38  }39 40  search (key) {41    let current = this.root42 43    while (current) {44      if (key === current.key) return current45      current = key < current.key ? current.left : current.right46    }47 48    return null49  }50 51  inOrderTraverse () {52    const result = []53 54    const visit = node => {55      if (node === null) return56      visit(node.left)57      result.push(node.key)58      visit(node.right)59    }60 61    visit(this.root)62    return result63  }64 65  min (node = this.root) {66    if (node === null) return null67    while (node.left !== null) node = node.left68    return node69  }70 71  max (node = this.root) {72    if (node === null) return null73    while (node.right !== null) node = node.right74    return node75  }76}class TreeNode {
  constructor (key) {
    this.key = key
    this.left = null
    this.right = null
  }
}

class BinarySearchTree {
  constructor () {
    this.root = null
  }

  insert (key) {
    const newNode = new TreeNode(key)

    if (this.root === null) {
      this.root = newNode
      return
    }

    let current = this.root
    while (current) {
      if (key < current.key) {
        if (current.left === null) {
          current.left = newNode
          return
        }
        current = current.left
      } else {
        if (current.right === null) {
          current.right = newNode
          return
        }
        current = current.right
      }
    }
  }

  search (key) {
    let current = this.root

    while (current) {
      if (key === current.key) return current
      current = key < current.key ? current.left : current.right
    }

    return null
  }

  inOrderTraverse () {
    const result = []

    const visit = node => {
      if (node === null) return
      visit(node.left)
      result.push(node.key)
      visit(node.right)
    }

    visit(this.root)
    return result
  }

  min (node = this.root) {
    if (node === null) return null
    while (node.left !== null) node = node.left
    return node
  }

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

BST 删除节点的三种情况

删除叶子节点：直接删除。
删除只有一个子节点的节点：让子节点顶替当前节点。
删除有两个子节点的节点：通常使用右子树最小节点，或左子树最大节点，替换当前节点。

AVL 树：严格平衡的二叉搜索树

AVL 树是一种自平衡二叉搜索树。它要求任意节点的左右子树高度差不超过 1。

当插入或删除导致不平衡时，AVL 树会通过旋转恢复平衡。

AVL 树的旋转类型

LL：新节点插入在左子树的左侧，需要右旋。
RR：新节点插入在右子树的右侧，需要左旋。
LR：新节点插入在左子树的右侧，先左旋再右旋。
RL：新节点插入在右子树的左侧，先右旋再左旋。

AVL 树查询性能稳定，适合读多写少的场景；因为维护平衡更严格，插入和删除时旋转成本可能比红黑树更高。

红黑树：工程中常用的自平衡树

红黑树也是一种自平衡二叉搜索树，但它不像 AVL 树那样追求严格平衡，而是通过颜色规则维持“近似平衡”。

红黑树的核心规则

每个节点要么是红色，要么是黑色。
根节点是黑色。
所有空叶子节点视为黑色。
红色节点的子节点必须是黑色，不能出现连续红色节点。
从任意节点到其所有后代空叶子节点的路径上，黑色节点数量相同。

新插入的节点通常先设为红色，再通过变色和旋转修复红黑树性质。

红黑树适合的场景

红黑树在插入、删除、查找之间取得了较好的平衡，工程中使用很多。例如 Java 的 TreeMap、TreeSet，以及部分语言或库中的有序映射结构。

如果操作以查询为主，AVL 树可能更有优势；如果插入和删除频繁，红黑树通常更适合。

二叉堆：完全二叉树上的优先级结构

二叉堆是一种满足堆性质的完全二叉树，通常用数组表示。它常用于优先队列、堆排序、Top K 问题等。

二叉堆的分类

最大堆：父节点的值大于或等于子节点的值，堆顶是最大值。
最小堆：父节点的值小于或等于子节点的值，堆顶是最小值。

二叉堆的数组下标关系

假设当前节点下标为 i：

父节点下标：Math.floor((i - 1) / 2)
左子节点下标：2 * i + 1
右子节点下标：2 * i + 2

最大堆的 JavaScript 实现

javascript

1function leftChildIndex (index) {2  return index * 2 + 13}4 5function rightChildIndex (index) {6  return index * 2 + 27}8 9function swap (array, i, j) {10  const temp = array[i]11  array[i] = array[j]12  array[j] = temp13}14 15class MaxHeap {16  constructor (array = []) {17    this.data = [...array]18    this.heapSize = this.data.length19    this.buildHeap()20  }21 22  buildHeap () {23    for (let i = Math.floor(this.heapSize / 2) - 1; i >= 0; i--) {24      this.heapifyDown(i)25    }26  }27 28  heapifyDown (index) {29    let largest = index30    const left = leftChildIndex(index)31    const right = rightChildIndex(index)32 33    if (left < this.heapSize && this.data[left] > this.data[largest]) {34      largest = left35    }36 37    if (right < this.heapSize && this.data[right] > this.data[largest]) {38      largest = right39    }40 41    if (largest !== index) {42      swap(this.data, index, largest)43      this.heapifyDown(largest)44    }45  }46 47  peek () {48    return this.data[0]49  }50 51  extractMax () {52    if (this.heapSize === 0) return undefined53 54    const max = this.data[0]55    this.data[0] = this.data[this.heapSize - 1]56    this.data.pop()57    this.heapSize--58    this.heapifyDown(0)59    return max60  }61}function leftChildIndex (index) {
  return index * 2 + 1
}

function rightChildIndex (index) {
  return index * 2 + 2
}

function swap (array, i, j) {
  const temp = array[i]
  array[i] = array[j]
  array[j] = temp
}

class MaxHeap {
  constructor (array = []) {
    this.data = [...array]
    this.heapSize = this.data.length
    this.buildHeap()
  }

  buildHeap () {
    for (let i = Math.floor(this.heapSize / 2) - 1; i >= 0; i--) {
      this.heapifyDown(i)
    }
  }

  heapifyDown (index) {
    let largest = index
    const left = leftChildIndex(index)
    const right = rightChildIndex(index)

    if (left < this.heapSize && this.data[left] > this.data[largest]) {
      largest = left
    }

    if (right < this.heapSize && this.data[right] > this.data[largest]) {
      largest = right
    }

    if (largest !== index) {
      swap(this.data, index, largest)
      this.heapifyDown(largest)
    }
  }

  peek () {
    return this.data[0]
  }

  extractMax () {
    if (this.heapSize === 0) return undefined

    const max = this.data[0]
    this.data[0] = this.data[this.heapSize - 1]
    this.data.pop()
    this.heapSize--
    this.heapifyDown(0)
    return max
  }
}

图：顶点与边组成的关系结构

图由顶点集合和边集合组成，用来描述对象之间的关系。相比树，图可以表达更复杂的连接关系。

常见场景包括社交网络、地图路径、依赖关系、推荐系统、网络拓扑等。

图的常见分类

无向图：边没有方向，例如好友关系。
有向图：边有方向，例如关注关系。
带权图：边带有权重，例如道路距离。
无权图：边只表示连接关系，不表示成本。

图的表示方式

邻接矩阵适合顶点数量较少、边较密集的图；邻接表适合边较稀疏的图，也是实际开发中更常见的表示方式。

javascript

1class Graph {2  constructor (isDirected = false) {3    this.isDirected = isDirected4    this.vertices = []5    this.adjList = new Map()6  }7 8  addVertex (vertex) {9    if (!this.vertices.includes(vertex)) {10      this.vertices.push(vertex)11      this.adjList.set(vertex, [])12    }13  }14 15  addEdge (from, to) {16    if (!this.adjList.has(from)) this.addVertex(from)17    if (!this.adjList.has(to)) this.addVertex(to)18 19    this.adjList.get(from).push(to)20 21    if (!this.isDirected) {22      this.adjList.get(to).push(from)23    }24  }25}class Graph {
  constructor (isDirected = false) {
    this.isDirected = isDirected
    this.vertices = []
    this.adjList = new Map()
  }

  addVertex (vertex) {
    if (!this.vertices.includes(vertex)) {
      this.vertices.push(vertex)
      this.adjList.set(vertex, [])
    }
  }

  addEdge (from, to) {
    if (!this.adjList.has(from)) this.addVertex(from)
    if (!this.adjList.has(to)) this.addVertex(to)

    this.adjList.get(from).push(to)

    if (!this.isDirected) {
      this.adjList.get(to).push(from)
    }
  }
}

广度优先搜索 BFS

BFS 使用队列，从起点开始一层一层向外访问。它适合求无权图最短路径、层级遍历、社交关系中的几度好友等问题。

javascript

1function breadthFirstSearch (graph, startVertex, callback) {2  const visited = new Set()3  const queue = [startVertex]4  visited.add(startVertex)5 6  while (queue.length > 0) {7    const vertex = queue.shift()8    callback(vertex)9 10    for (const neighbor of graph.adjList.get(vertex)) {11      if (!visited.has(neighbor)) {12        visited.add(neighbor)13        queue.push(neighbor)14      }15    }16  }17}function breadthFirstSearch (graph, startVertex, callback) {
  const visited = new Set()
  const queue = [startVertex]
  visited.add(startVertex)

  while (queue.length > 0) {
    const vertex = queue.shift()
    callback(vertex)

    for (const neighbor of graph.adjList.get(vertex)) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor)
        queue.push(neighbor)
      }
    }
  }
}

深度优先搜索 DFS

DFS 使用递归或栈，从一个分支尽可能深入，走不通再回溯。它适合路径搜索、连通分量、拓扑排序、检测环等问题。

javascript

1function depthFirstSearch (graph, startVertex, callback) {2  const visited = new Set()3 4  function visit (vertex) {5    visited.add(vertex)6    callback(vertex)7 8    for (const neighbor of graph.adjList.get(vertex)) {9      if (!visited.has(neighbor)) {10        visit(neighbor)11      }12    }13  }14 15  visit(startVertex)16}function depthFirstSearch (graph, startVertex, callback) {
  const visited = new Set()

  function visit (vertex) {
    visited.add(vertex)
    callback(vertex)

    for (const neighbor of graph.adjList.get(vertex)) {
      if (!visited.has(neighbor)) {
        visit(neighbor)
      }
    }
  }

  visit(startVertex)
}

复杂度速查表

数据结构	查找	插入	删除	适合场景
栈	`O(n)`	`O(1)`	`O(1)`	撤销、括号匹配、函数调用
队列	`O(n)`	`O(1)`	`O(1)`	排队任务、BFS、消息处理
双端队列	`O(n)`	`O(1)`	`O(1)`	滑动窗口、撤销重做
集合	平均 `O(1)`	平均 `O(1)`	平均 `O(1)`	去重、集合运算
字典	平均 `O(1)`	平均 `O(1)`	平均 `O(1)`	映射关系、缓存
二叉搜索树	平均 `O(log n)`	平均 `O(log n)`	平均 `O(log n)`	有序数据、范围查询
AVL 树	`O(log n)`	`O(log n)`	`O(log n)`	查询较多且要求稳定
红黑树	`O(log n)`	`O(log n)`	`O(log n)`	插入删除较频繁的有序结构
二叉堆	`O(n)`	`O(log n)`	`O(log n)`	优先队列、Top K、堆排序
图	取决于算法	取决于表示	取决于表示	路径、关系、依赖建模

线性结构概览

栈：后进先出结构

栈的常用操作

栈的数组实现

栈的对象实现

队列：先进先出结构

队列的常用操作

队列的对象实现

双端队列：两端都可操作的队列

双端队列的常用操作

双端队列的对象实现

集合：无序且唯一的数据结构

集合的常用操作

集合的基础实现

集合的常见运算

字典：键值对映射结构

字典的常用操作

字典的基础实现

树结构概览

二叉树：最多两个子节点的树

二叉搜索树 BST：可排序的二叉树

BST 的常用操作

BST 的 JavaScript 实现

BST 删除节点的三种情况

AVL 树：严格平衡的二叉搜索树

AVL 树的旋转类型

红黑树：工程中常用的自平衡树

红黑树的核心规则

红黑树适合的场景

二叉堆：完全二叉树上的优先级结构

二叉堆的分类

二叉堆的数组下标关系

最大堆的 JavaScript 实现

图：顶点与边组成的关系结构

图的常见分类

图的表示方式

广度优先搜索 BFS

深度优先搜索 DFS

复杂度速查表

相关文章

评论

相关文章

评论