数据结构板块导览

数据结构这一块的价值不在于「会手写红黑树」，而在于拿到需求时能立刻选出合适的容器，并知道它的复杂度代价。所以本板块每页都按同一个顺序展开：接口设计（TypeScript 类型）→ 实现（带注释）→ 各操作复杂度 → 与 JS 内建结构的对比 → 前端真实用途 → 易错点。

先看一张选型表

拿到问题时，按你要做的操作查表，比背结构名字有用得多：

你的主要操作	优先考虑	典型复杂度	前端例子
按下标随机访问、尾部增删	数组 / TypedArray	O(1) / O(1) 摊还	列表渲染数据、顶点缓冲、像素数组
头部频繁增删	环形缓冲队列 / 双端队列	O(1)	消息队列、动画队列、0-1 BFS
按值快速查找、去重	Map / Set（哈希表）	O(1) 平均	缓存、ID 索引、标签去重
需要有序遍历、范围查询	平衡树 / 跳表 / 排序数组	O(log n) 查、O(n) 遍历	时间轴、区间合并、排行榜
每次取最值	堆 / 优先队列	O(log n) 入出、O(1) 取顶	任务调度、Top-K、定时器
前缀匹配、自动补全	Trie	O(前缀长度)	搜索建议、命令面板、路由匹配
连通性判断、动态合并	并查集	近似 O(1)	分组、依赖环检测、图像连通区域
区间统计（和/最值）	线段树 / Fenwick 树	O(log n) 更新与查询	虚拟滚动、图表聚合、区间过滤
缓存淘汰	LRU（哈希表 + 双向链表）	O(1)	接口缓存、图片缓存、计算结果缓存
判断「可能存在」且允许误判	布隆过滤器	O(k)	缓存穿透防护、大规模去重

数组 vs 链表：实测差距在头部/中部/尾部插入删除与随机访问的耗时对比

examples/data-structures/array-vs-linked-list.js

/**
 * 【数据结构 · TypeScript】数组 vs 链表：一次操作的实测耗时
 * ------------------------------------------------------------------
 * 同一批操作（头部插入 / 中部插入 / 尾部插入 / 头部删除 / 尾部删除 / 随机访问）
 * 分别跑在内建 `Array` 与手写单向链表上，按规模画成对数刻度的柱状图。
 *
 * 度量方法（比“跑一次看毫秒数”可靠得多）：
 *   · 每个样本先按规模建好结构（建结构的时间**不计入**）；
 *   · 在一个 now() 区间里连续执行 chunk 次操作，chunk 按上一次的实测单次耗时自适应放大，
 *     这样既摊销了 performance.now() 本身的开销，也不会让慢操作跑太久；
 *   · 结构被撑大或掏空到不安全时，**在计时之外**重建，保证规模始终接近 n；
 *   · 每轮把操作结果累加进 checksum，避免 JIT 把空转调用优化掉。
 */
import { create2D, rafLoop, cleanupAll } from '../shared/runtime.js'
import { createPanel } from '../shared/ui.js'

/* ============================ 1. 两种结构 ============================ */

/** 链表节点：TS 里的“指针”就是一个可为 null 的对象引用 */
class ListNode {
  value: number
  next: ListNode | null

  constructor(value: number) {
    this.value = value
    this.next = null
  }
}

/** 单向链表：带 tail 指针，尾部插入才是 O(1) */
class SinglyLinkedList {
  head: ListNode | null = null
  tail: ListNode | null = null
  size = 0

  push(value: number): void {
    const node = new ListNode(value)
    if (this.tail) {
      this.tail.next = node
      this.tail = node
    } else {
      this.head = node
      this.tail = node
    }
    this.size++
  }

  unshift(value: number): void {
    const node = new ListNode(value)
    node.next = this.head
    this.head = node
    if (!this.tail) this.tail = node
    this.size++
  }

  /** 第 index 个元素：必须从头逐个跳过去，O(n) */
  get(index: number): number {
    let cur = this.head
    for (let i = 0; i < index && cur; i++) cur = cur.next
    return cur ? cur.value : -1
  }

  insertAt(index: number, value: number): void {
    if (index <= 0) {
      this.unshift(value)
      return
    }
    if (index >= this.size) {
      this.push(value)
      return
    }
    let prev = this.head
    for (let i = 0; i < index - 1 && prev; i++) prev = prev.next
    if (!prev) return
    const node = new ListNode(value)
    node.next = prev.next
    prev.next = node
    this.size++
  }

  removeHead(): number {
    const node = this.head
    if (!node) return -1
    this.head = node.next
    if (!this.head) this.tail = null
    this.size--
    return node.value
  }

  /** 尾部删除需要找倒数第二个节点，所以是 O(n) */
  removeTail(): number {
    const node = this.tail
    if (!node) return -1
    if (this.head === node) {
      this.head = null
      this.tail = null
      this.size = 0
      return node.value
    }
    let prev = this.head
    while (prev && prev.next !== node) prev = prev.next
    if (prev) {
      prev.next = null
      this.tail = prev
    }
    this.size--
    return node.value
  }
}

/* ============================ 2. 待对比的操作 ============================ */

/** insert / remove 会改变规模，access 不会 */
type OpKind = 'insert' | 'remove' | 'access'

interface BenchCase {
  label: string
  /** 展示用的复杂度标签，不参与计算 */
  arrayOrder: string
  listOrder: string
  kind: OpKind
  arrayRun(array: number[], i: number): number
  listRun(list: SinglyLinkedList, i: number): number
}

const CASES = {
  headInsert: {
    label: '头部插入',
    arrayOrder: 'O(n)',
    listOrder: 'O(1)',
    kind: 'insert',
    arrayRun: (array, i) => {
      array.unshift(i)
      return array.length
    },
    listRun: (list, i) => {
      list.unshift(i)
      return list.size
    }
  },
  midInsert: {
    label: '中部插入',
    arrayOrder: 'O(n)',
    listOrder: 'O(n)',
    kind: 'insert',
    arrayRun: (array, i) => {
      array.splice(array.length >> 1, 0, i)
      return array.length
    },
    listRun: (list, i) => {
      list.insertAt(list.size >> 1, i)
      return list.size
    }
  },
  tailInsert: {
    label: '尾部插入',
    arrayOrder: 'O(1)',
    listOrder: 'O(1)',
    kind: 'insert',
    arrayRun: (array, i) => {
      array.push(i)
      return array.length
    },
    listRun: (list, i) => {
      list.push(i)
      return list.size
    }
  },
  headRemove: {
    label: '头部删除',
    arrayOrder: 'O(n)',
    listOrder: 'O(1)',
    kind: 'remove',
    arrayRun: (array) => {
      const value = array.shift()
      return value === undefined ? -1 : value
    },
    listRun: (list) => list.removeHead()
  },
  tailRemove: {
    label: '尾部删除',
    arrayOrder: 'O(1)',
    listOrder: 'O(n)',
    kind: 'remove',
    arrayRun: (array) => {
      const value = array.pop()
      return value === undefined ? -1 : value
    },
    listRun: (list) => list.removeTail()
  },
  randomAccess: {
    label: '随机访问',
    arrayOrder: 'O(1)',
    listOrder: 'O(n)',
    kind: 'access',
    arrayRun: (array, i) => array[(i * 7919) % array.length] ?? -1,
    listRun: (list, i) => list.get((i * 7919) % list.size)
  }
} satisfies Record<string, BenchCase>

type CaseName = keyof typeof CASES
const CASE_NAMES = Object.keys(CASES) as CaseName[]

const SIZES: readonly number[] = [500, 5000, 50000]

/* ============================ 3. 度量 ============================ */

interface Timing {
  /** 单次操作耗时（毫秒） */
  perOp: number
  /** 实际执行的操作次数 */
  ops: number
  /** 计时之外重建结构的次数 */
  refills: number
}

interface Adapter<S> {
  create(size: number): S
  count(state: S): number
}

const ARRAY_ADAPTER: Adapter<number[]> = {
  create: (size) => {
    const array = new Array<number>(size)
    for (let i = 0; i < size; i++) array[i] = i
    return array
  },
  count: (array) => array.length
}

const LIST_ADAPTER: Adapter<SinglyLinkedList> = {
  create: (size) => {
    const list = new SinglyLinkedList()
    for (let i = 0; i < size; i++) list.push(i)
    return list
  },
  count: (list) => list.size
}

/** 一个 chunk 最多连续执行多少次操作（access 的批量上限） */
const ACCESS_CHUNK = 4096
/** 单次度量的时间预算（毫秒） */
const DEFAULT_BUDGET = 4

/**
 * 度量「在规模约 size 的结构上执行一次操作」的平均耗时。
 * 泛型 S 让同一个函数既能测 `number[]`，也能测链表。
 */
function bench<S>(
  adapter: Adapter<S>,
  run: (state: S, i: number) => number,
  kind: OpKind,
  size: number,
  budgetMs: number
): Timing {
  const half = Math.max(1, Math.floor(size / 2))
  const cap = Math.max(half + 1, Math.floor(size * 1.5))
  let state = adapter.create(size)
  let preCheck = 0
  let ops = 0
  let refills = 0
  let elapsed = 0
  let chunk = 1

  while (elapsed < budgetMs && ops < 2_000_000 && refills < 400) {
    const room =
      kind === 'access'
        ? ACCESS_CHUNK
        : kind === 'remove'
          ? adapter.count(state) - half
          : cap - adapter.count(state)

    if (room <= 0) {
      state = adapter.create(size) // 计时之外重建，规模回到 n
      refills++
      continue
    }

    const n = Math.min(chunk, room)
    const t0 = performance.now()
    for (let k = 0; k < n; k++) preCheck += run(state, ops + k)
    const dt = performance.now() - t0

    elapsed += dt
    ops += n
    const perOp = dt / n
    const target = perOp > 0 ? Math.ceil(Math.max(0.1, budgetMs - elapsed) / perOp) : 1 << 20
    // 每次最多放大到 4 倍：单次样本可能远低于平均值（随机访问恰好命中头部就是这样）
    chunk = Math.max(1, Math.min(1 << 20, Math.floor(chunk * 4), target))
  }

  void preCheck
  return { perOp: ops > 0 ? elapsed / ops : 0, ops, refills }
}

interface Sample {
  size: number
  array: Timing
  list: Timing
}

function runCase(name: CaseName, budgetMs: number): Sample[] {
  const kase = CASES[name]
  return SIZES.map((size) => ({
    size,
    array: bench(ARRAY_ADAPTER, kase.arrayRun, kase.kind, size, budgetMs),
    list: bench(LIST_ADAPTER, kase.listRun, kase.kind, size, budgetMs)
  }))
}

/* ============================ 4. 绘制 ============================ */

const COLORS = {
  bg: '#0b1220',
  array: '#7aa2ff',
  list: '#7ee7ce',
  grid: 'rgba(122, 162, 255, 0.14)',
  text: 'rgba(230, 237, 247, 0.72)',
  dim: 'rgba(230, 237, 247, 0.42)'
} as const

/** 对数刻度：1ns ~ 100ms */
const AXIS_MIN_NS = 1
const AXIS_MAX_NS = 1e8
const TICKS: ReadonlyArray<{ ns: number; label: string }> = [
  { ns: 1e0, label: '1ns' },
  { ns: 1e2, label: '100ns' },
  { ns: 1e4, label: '10µs' },
  { ns: 1e6, label: '1ms' },
  { ns: 1e8, label: '100ms' }
]

function fmtTime(ms: number): string {
  const ns = ms * 1e6
  if (ns < 1e3) return `${ns < 10 ? ns.toFixed(1) : ns.toFixed(0)} ns`
  if (ns < 1e6) return `${(ns / 1e3).toFixed(ns < 1e4 ? 2 : 1)} µs`
  if (ns < 1e9) return `${(ns / 1e6).toFixed(2)} ms`
  return `${(ns / 1e9).toFixed(2)} s`
}

function sizeLabel(size: number): string {
  return size >= 1000 ? `n=${size / 1000}k` : `n=${size}`
}

export default function (container: HTMLElement): () => void {
  const view = create2D(container, { width: 660, height: 340, background: COLORS.bg })
  const { ctx } = view

  let current: CaseName = 'headInsert'
  let budget = DEFAULT_BUDGET
  let samples: Sample[] = []
  let dirty = true
  /** 累计操作次数，既能证明度量真的跑了，也让结果不被优化掉 */
  let checksum = 0

  const nsOf = (timing: Timing): number => Math.max(AXIS_MIN_NS, timing.perOp * 1e6)
  const norm = (timing: Timing): number =>
    Math.min(1, Math.max(0, (Math.log10(nsOf(timing)) - Math.log10(AXIS_MIN_NS)) / (Math.log10(AXIS_MAX_NS) - Math.log10(AXIS_MIN_NS))))

  function draw(): void {
    const { width: w, height: h } = view
    const padLeft = 62
    const padRight = 18
    const padTop = 52
    const padBottom = 52
    const plotW = w - padLeft - padRight
    const plotH = h - padTop - padBottom
    const bottom = padTop + plotH

    ctx.fillStyle = COLORS.bg
    ctx.fillRect(0, 0, w, h)

    // ---- 纵轴：对数刻度 ----
    ctx.font = '11px ui-monospace, monospace'
    for (const tick of TICKS) {
      const t = (Math.log10(tick.ns) - Math.log10(AXIS_MIN_NS)) / (Math.log10(AXIS_MAX_NS) - Math.log10(AXIS_MIN_NS))
      const y = bottom - t * plotH
      ctx.strokeStyle = COLORS.grid
      ctx.lineWidth = 1
      ctx.beginPath()
      ctx.moveTo(padLeft, y)
      ctx.lineTo(padLeft + plotW, y)
      ctx.stroke()
      ctx.fillStyle = COLORS.dim
      ctx.textAlign = 'right'
      ctx.fillText(tick.label, padLeft - 8, y + 4)
    }

    // ---- 分组柱状图 ----
    const groupW = plotW / SIZES.length
    const barW = Math.min(34, groupW * 0.24)
    const gap = 8

    for (let g = 0; g < samples.length; g++) {
      const sample = samples[g]
      const center = padLeft + groupW * (g + 0.5)
      const faster = sample.array.perOp <= sample.list.perOp ? 'Array' : '链表'
      const bars = [
        { label: 'Array', value: sample.array, color: COLORS.array, x: center - barW - gap / 2, fast: faster === 'Array' },
        { label: '链表', value: sample.list, color: COLORS.list, x: center + gap / 2, fast: faster === '链表' }
      ]

      for (const bar of bars) {
        const barH = Math.max(2, norm(bar.value) * plotH)
        const y = bottom - barH
        ctx.fillStyle = bar.color
        ctx.globalAlpha = bar.fast ? 1 : 0.55
        ctx.fillRect(bar.x, y, barW, barH)
        ctx.globalAlpha = 1

        if (bar.fast) {
          ctx.strokeStyle = 'rgba(255, 255, 255, 0.75)'
          ctx.lineWidth = 1.4
          ctx.strokeRect(bar.x + 0.5, y + 0.5, barW - 1, barH - 1)
        }

        ctx.fillStyle = COLORS.text
        ctx.textAlign = 'center'
        ctx.font = '10px ui-monospace, monospace'
        ctx.fillText(fmtTime(bar.value.perOp), bar.x + barW / 2, y - 6)
      }

      ctx.fillStyle = COLORS.dim
      ctx.textAlign = 'center'
      ctx.font = '11px ui-monospace, monospace'
      ctx.fillText(sizeLabel(sample.size), center, bottom + 18)
      ctx.fillStyle = faster === 'Array' ? COLORS.array : COLORS.list
      ctx.fillText(faster === 'Array' ? 'Array 更快' : '链表更快', center, bottom + 34)
    }

    // ---- 图例与标题 ----
    const kase = CASES[current]
    ctx.textAlign = 'left'
    ctx.font = '13px ui-monospace, monospace'
    ctx.fillStyle = 'rgba(230, 237, 247, 0.9)'
    ctx.fillText(`${kase.label}（单次操作耗时，对数刻度）`, padLeft - 46, 20)

    ctx.font = '11px ui-monospace, monospace'
    ctx.fillStyle = COLORS.array
    ctx.fillRect(padLeft - 46, 30, 10, 10)
    ctx.fillStyle = COLORS.text
    ctx.fillText(`内建 Array ${kase.arrayOrder}`, padLeft - 30, 39)

    ctx.fillStyle = COLORS.list
    ctx.fillRect(padLeft + 96, 30, 10, 10)
    ctx.fillStyle = COLORS.text
    ctx.fillText(`单向链表 ${kase.listOrder}`, padLeft + 112, 39)

    ctx.fillStyle = COLORS.dim
    ctx.font = '10px ui-monospace, monospace'
    ctx.textAlign = 'right'
    ctx.fillText(`预算 ${budget}ms/项 · 累计校验和 ${checksum}`, padLeft + plotW, 39)
  }

  const loop = rafLoop(() => {
    if (!dirty) return
    dirty = false
    draw()
  })

  const panel = createPanel(container, { title: '对比参数', position: 'below' })
  const readout = panel.readout('测量中…')

  /** 重新测量并刷新所有与结果有关的显示 */
  function refresh(): void {
    samples = runCase(current, budget)
    checksum = 0
    for (const sample of samples) checksum += sample.array.ops + sample.list.ops
    dirty = true
    const last = samples[samples.length - 1]
    readout.set(`${sizeLabel(last.size)}：Array ${fmtTime(last.array.perOp)} / 链表 ${fmtTime(last.list.perOp)}`)
  }

  panel.select<CaseName>({
    label: '操作类型',
    value: current,
    options: CASE_NAMES.map((name) => ({ label: CASES[name].label, value: name })),
    onChange: (value) => {
      current = value
      refresh()
    }
  })
  panel.slider({
    label: '每项测量预算',
    min: 1,
    max: 12,
    step: 1,
    value: budget,
    format: (v) => `${v} ms`,
    onInput: (v) => {
      budget = v
      refresh()
    }
  })
  panel.button({ label: '重新测量', onClick: refresh })
  panel.note(
    '每根柱子是「在规模 n 的结构上执行一次操作」的平均耗时：高亮描边代表这一组更快。' +
      '计时期间在 now() 之间连续跑多个操作以摊销计时开销，结构被撑大或掏空时在计时之外重建。'
  )
  refresh()

  return cleanupAll(loop, view, panel)
}

为什么 JS 里 Array 常常比链表快

链表的理论复杂度更漂亮，但每个节点都是一次堆分配 + 一次指针跳转，缓存友好性差；而 JS 的 Array 是连续存储的动态数组，顺序访问几乎总能命中 CPU 缓存。「理论复杂度」与「实际耗时」不一致时，先怀疑数据局部性与分配开销——这也是本板块每个示例都带实测对比的原因。

板块地图

页面	讲什么	关键结论
数组与 TypedArray	JS 数组的真实实现、shift 为何慢、TypedArray 内存布局	尾部操作便宜，头部操作昂贵；二进制数据用 TypedArray
链表	单向/双向/循环、哨兵节点、反转与判环	适合频繁插入删除与「移动节点」的场景（LRU、撤销栈）
栈、队列与双端队列	数组/链表/环形缓冲三种实现	队列要用环形缓冲，别用数组 shift
哈希表与 Map/Set	冲突处理、负载因子、Map vs 对象	平均 O(1)，但要防碰撞攻击与可变键
树与二叉搜索树	遍历、BST 增删查、平衡树概念	有序性带来 O(log n)，退化会变成 O(n)
堆与优先队列	sift 操作、O(n) 建堆、Top-K	只要最值不要全序时，堆比排序便宜
Trie 与字符串结构	前缀树、压缩 Trie、与其他方案对比	前缀查询用 Trie，纯精确查找用哈希表
并查集与图表示	路径压缩、按秩合并、图的三表示	动态连通性问题的最优解
线段树、跳表与持久化结构	区间结构、近似判断、不可变结构	按「查询形态」选结构，而不是按名字

JS/TS 内建结构速览

内置结构已经覆盖了大部分需求，先确认内置的够不够用，再考虑自己实现：

内建	底层	适合	注意
Array	动态数组（可能退化为字典模式）	顺序数据、栈（push/pop）	shift/unshift/splice 是 O(n)；顺序访问最快
Map	哈希表	任意类型的键、保序字典	键是引用比较（对象键要求同一引用）；size 是 O(1)
Set	哈希表	去重、成员判断	迭代顺序是插入顺序，别依赖它做排序
WeakMap / WeakSet	弱引用哈希	给对象附加元数据、避免内存泄漏	不可遍历、无 size；键必须是对象
TypedArray	连续二进制缓冲	图形/音视频/二进制协议	长度固定；越界写入被忽略（不报错）
ArrayBuffer / DataView	字节缓冲	解析协议、手动控制字节序	注意 littleEndian 参数，网络协议多为大端
JSON	文本序列化	配置、接口数据	不支持 Map/Set/undefined/循环引用

Map 的插入序不是排序

Map 保证插入顺序，不保证有序。需要按 key 排序遍历时，要显式 [...map.keys()].sort()（每次 O(n log n)），或者改用有序结构（跳表/平衡树/排序数组 + 二分）。

各结构操作复杂度对照

结构	访问	查找	插入	删除	备注
数组	O(1)	O(n)	O(n) / 尾部 O(1)	O(n) / 尾部 O(1)	缓存友好
链表	O(n)	O(n)	O(1)（已知位置）	O(1)（已知节点）	分配开销大
哈希表	—	O(1) 平均	O(1) 平均	O(1) 平均	最坏 O(n)
二叉搜索树（平衡）	O(log n)	O(log n)	O(log n)	O(log n)	退化时 O(n)
堆	O(1) 取顶	O(n)	O(log n)	O(log n) 删顶	只保证堆序
Trie	—	O(前缀长度)	O(键长)	O(键长)	空间换时间
并查集	—	近似 O(1)	近似 O(1)	不支持删除	只做合并与查询
跳表	O(log n)	O(log n)	O(log n)	O(log n)	实现比平衡树简单

怎么用这个板块

1. 先查选型表：确定候选结构，再进对应页面。
2. 读接口而非实现细节：每页开头都有 TypeScript 接口，先看接口能否满足你的调用方式。
3. 看实测数字：带可视化的示例会给出真实耗时对比，用来校准「理论复杂度」与「实际性能」的差距。
4. 回到复杂度表自查：自己实现时，如果某个操作比表里慢一个量级，通常意味着写错了（例如队列用了 shift）。

常见坑（跨结构通用）

现象	原因	处理
队列越用越慢	用数组 shift() 出队，每次搬移整个数组	改环形缓冲或链表队列
哈希表查找变慢	键的哈希分布差（如自增 ID 低位规律）或负载因子过高	换哈希函数、及时扩容、避免用可变对象做键
递归遍历树导致爆栈	深度等于节点数（退化成链）	改迭代 + 显式栈，或用平衡结构
WeakMap 里的数据「不见了」	键对象被 GC 回收（这正是它的设计目的）	需要长期持有时改用 Map 并显式清理
修改结构后迭代结果异常	迭代过程中增删元素	先快照（[...map]）再迭代，或收集待删项
内存只增不减	缓存没有淘汰策略、监听器未解绑	用 LRU/布隆过滤器控制规模，配套取消订阅机制

相关板块

• 算法 —— 结构之上的算法：排序、查找、图算法、动态规划
• 前端程序设计模式 —— 用模式组织数据结构与缓存层
• 图形学数学 —— 图形数据（顶点、矩阵、四叉树划分）的数学基础
• TypeScript 示例约定 —— 本板块示例的写法约定