// 课程 · 12 课 · 为拇指而生
[data structures]
从一排带编号的储物柜到自平衡树。每节课都以一个可互动的演示开始 — push、pop、walk、hash、rotate — 讲解文字位于演示下方，而非前面。
复习
课程
- #01
数组
连续内存——一个 CPU 周期内完成按下标访问
- read
- O(1)
- write
- O(n)
- layout
- contiguous
- #02
链表
节点散落在内存各处，靠指针缝合在一起
- read
- O(n)
- write
- O(1)*
- layout
- scattered
- #03
栈
后进先出（LIFO）——最新进来的，最先出去
- read
- O(1)
- write
- O(1)
- layout
- LIFO
- #04
队列
先进先出（FIFO）——每一次都是公平的顺序
- read
- O(1)
- write
- O(1)
- layout
- FIFO
- #05
二叉树
一个节点，两个孩子——一切递归数据结构之源
- read
- O(n)
- write
- O(1)
- layout
- hierarchy
- #06
二叉搜索树
顺序进去，对数时间出来
- read
- O(log n)
- write
- O(log n)
- layout
- ordered
- #07
堆与优先队列
数组支撑、对数时间取最小值——优先队列的引擎
- read
- O(1)
- write
- O(1)
- layout
- FIFO
- #08
哈希表
djb2 哈希 → 桶下标 → 平均 O(1)
- read
- O(1)*
- write
- O(1)*
- layout
- bucketed
- #09
图
顶点与边——一种通用的抽象
- read
- O(V+E)
- write
- varies
- layout
- edges
- #10
平衡树
旋转让高度始终 ≈ log n，无论插入顺序如何
- read
- O(log n)
- write
- O(log n)
- layout
- self-rotating
- #11
动态规划
以空间换时间——解一次，永远记住
- read
- O(1)*
- write
- tabulate
- layout
- O(n·m)