两问先给结论：
- 有哪些：按操作契约分四大家族——线性、树、图、散列；
栈、队列、优先队列、有序映射等是家族上的接口别名，不是第五家族。 - 底层会不会因语言而变：会。 跨语言稳定的是 抽象数据类型（Abstract Data Type，ADT） 的操作与复杂度；变的是节点布局、增长策略、哈希算法、是否装箱、是否有 垃圾回收（Garbage Collection，GC）。
以 Python 把四大家族落到标准库：从 数组与动态数组 读到 图，柜台表见 Python标准库速查。
段末注释：ADT 只规定「能做什么、多慢」，不规定「内存怎么摆」。同一 ADT 可以有多种实现；同一种实现落到不同语言运行时，字节布局仍会不同。
1. 先拆三层，再看清单
把「数据结构」叠成三层，后面所有「同名不同物」都能对上号。
| 层 | 问的问题 | 跨语言是否一致 | 例子 |
|---|---|---|---|
| ADT | 支持哪些操作？均摊 / 最坏复杂度？ | 一致（教科书口径） | 栈 = 后进先出；查找期望 (O(1)) |
| 具体实现 | 用连续数组还是指针串？链地址还是开放寻址？ | 可选、可换 | 栈用数组或链表都能做 |
| 语言运行时 | 元素是值还是对象引用？有没有对象头、GC、对齐？ | 必有差异 | Python list 存的是指针，C++ vector<int> 存的是整数本身 |
读复杂度时默认指 ADT + 某种主流实现。例如「哈希表查找 (O(1))」说的是期望均摊，前提是哈希均匀、装载因子受控；最坏仍可以退化到 (O(n))（或树化后 (O(\log n))）。
2. 数据结构有哪些
教科书口径（CLRS 一类）按 逻辑形状 分，不按语言关键字分。下面是工作中会碰到的闭集，不是「所有曾被发明过的结构」。
2.1 线性：位置有先后
| ADT / 结构 | 核心操作 | 主流实现 | 复杂度直觉 |
|---|---|---|---|
| 静态数组 | 按下标读写 | 连续内存 | 读写 (O(1))；中间插入 (O(n)) |
| 动态数组 | 尾部追加、随机访问 | 连续块 + 扩容 | 追加均摊 (O(1))；扩容拷贝 (O(n)) |
| 链表 | 端点插入删除 | 单 / 双向 / 循环节点 | 已知节点处插删 (O(1))；按下标找 (O(n)) |
| 栈 | 入栈 / 出栈 | 动态数组或链表 | (O(1)) |
| 队列 / 双端队列 | 两端进出 | 环数组、块状链表 | (O(1)) |
| 字符串 | 切片、拼接、查找 | 字节 / 码元数组（常不可变） | 取决于是否共享底层、是否写时复制 |
栈、队列不是「另一种形状」，而是给线性容器加了 只从哪端进出 的纪律。
2.2 树：分层、常用来维持有序或堆序
| 结构 | 用来干什么 | 节点关系 |
|---|---|---|
| 二叉树 / 二叉搜索树 | 有序查找的教学原型 | 左 < 根 < 右 |
| 堆（二叉堆） | 优先队列 | 父优于子；数组即可存 |
| 平衡树（AVL、红黑树、Treap） | 有序映射 / 有序集合 | 旋转或随机优先级维持高度 (O(\log n)) |
| B / B+ 树 | 磁盘、数据库索引 | 多路、矮胖，减少 I/O |
| 字典树（Trie） | 前缀查找 | 边是字符 / 字节 |
| 线段树 / 树状数组 | 区间查询与更新 | 把数组递归对半 |
| 并查集 | 连通分量、 Kruskal | 父指针森林 + 路径压缩 |
2.3 图：点与边
图是「关系」的容器。实现几乎只有两条路：
| 实现 | 存什么 | 适合 |
|---|---|---|
| 邻接矩阵 | (n \times n) 是否有边 / 权重 | 稠密图、快速判边 |
| 邻接表 | 每个点一份出边列表 | 稀疏图（更常见） |
有向 / 无向、带权 / 不带权是 边的语义，不是第三种存法。遍历入口是广度优先、深度优先；最短路、最小生成树是算法，挂在图上，本身不是新结构。
2.4 散列：用哈希函数把键拍到槽位
| 结构 | 与「普通数组」的差 |
|---|---|
| 哈希表 / 哈希映射 | 键 → 槽；冲突用链或探测 |
| 哈希集合 | 只有键、没有值 |
| 布隆过滤器 | 位图 + 多哈希；能确定「不在」，不能确定「在」 |
有序映射（按键排序遍历）不是哈希表：主流是平衡树或跳表。语言里都叫 map 时，先问「有序还是散列」。
2.5 组合体（不是新家族）
工程里常见的是 两种结构焊在一起：
| 名字 | 焊法 | 换来的操作 |
|---|---|---|
| LRU 缓存 | 哈希表 + 双向链表 | 按键 (O(1)) 找到，并 (O(1)) 挪到队头 |
| 优先队列 | 通常是堆 | 每次取出当前最优 |
| 跳表 | 多层链表 + 随机层高 | 期望 (O(\log n)) 查找，实现比红黑树简单 |
| 稀疏矩阵 | 三元组表或邻接表 | 只存非零 |
3. 底层实现会因语言而变——变在哪
ADT 层不变，运行时层必变。 差异集中在五件事。
3.1 元素是「值」还是「指针」
| 语言 | 典型容器里实际躺着的东西 | 后果 |
|---|---|---|
| C / C++ / Rust | T 本身（值语义，可内联） |
连续、缓存友好；vector<int> 就是一排整数 |
| Java | 对象引用（泛型会装箱） | ArrayList<Integer> 是一排指针，整数在堆上另有对象头 |
| Python | 一律 PyObject* |
list 是指针数组，不是 C 的 int[] |
| Go | 基本类型内联；接口 / 指针才间接 | []int 连续；[]any 每元素一个接口值 |
所以「数组 (O(1)) 随机访问」在 Python 里仍成立，但常数比 C++ vector<int> 大一截：每次访问多一次指针跳转。
3.2 同名容器，实现常常不是同一种
| 你随口说的词 | Python | C++ | Java | Go | Rust |
|---|---|---|---|---|---|
| list | list = 动态指针数组 |
std::list = 双向链表 |
LinkedList = 双向链表；日常用 ArrayList |
无此关键字，用 slice |
LinkedList 存在但很少用；日常 Vec |
| map / dict | dict = 有序哈希表（3.7+ 语言保证插入序） |
std::map = 红黑树；散列是 unordered_map |
HashMap 无序；TreeMap 红黑；LinkedHashMap 保序 |
map = 哈希表，遍历顺序不保证 |
HashMap = 瑞士表；有序用 BTreeMap |
| 动态数组 | list |
vector（常见 2× 扩容） |
ArrayList（1.5× 扩容） |
slice（指针 + 长度 + 容量） |
Vec（常见 2×） |
| 双端队列 | collections.deque（块状双向） |
deque（分块） |
ArrayDeque |
无内置，第三方或环形切片 | VecDeque |
最容易踩的坑：把 Python 的 list 想成 C++ 的 list，或把 C++ 的 map 想成 Python 的 dict。前者一个是数组、一个是链表；后者一个是树（有序、(O(\log n))）、一个是哈希（无序或插入序、期望 (O(1))）。
3.3 哈希表：同是「散列」，探测方式不同
| 实现 | 冲突怎么处理 | 出现在 |
|---|---|---|
| 链地址 + 桶过长转红黑树 | 链表，长度 ≥ 8 树化 | Java HashMap（Java 8+） |
| 紧凑插入序表 | 索引层 + 按插入排列的条目 | CPython dict（3.6 实现，3.7 成语言规范） |
| 分离链接（节点散列） | 每槽一条链 | 多数 std::unordered_map |
| 瑞士表（开放寻址 + SIMD 探针） | 组内并行比 tophash | Rust HashMap（hashbrown）；Go 1.24+ map |
复杂度都写成期望 (O(1))，但 缓存行为、删除墓碑、迭代顺序、最坏退化 不一样。跨语言移植「依赖遍历顺序」的代码，这是第一处爆点。
3.4 字符串与切片：可变、共享、编码
| 语言 | 字符串 | 容易忽略的点 |
|---|---|---|
| C | char* + '\0' |
不是容器，是约定 |
| C++ | std::string，短串常 SSO（小字符串优化，存在对象内部） |
短串无堆分配 |
| Java | 不可变；紧凑字符串后 Latin-1 用 byte[] |
下标是 16 位码元时代的遗留直觉，不再总成立 |
| Python | 不可变 Unicode；短串可能驻留 | += 在循环里会反复分配 |
| Go / Rust | 不可变字节视图 / String（UTF-8） |
下标是字节，不是「第几个字」 |
切片（Go slice、Rust &[T]、Python list[i:j]）有的共享底层、有的拷贝。改一个切片会不会改另一个，必须查该语言的语义，不能从名字猜。
3.5 并发与内存管理
- GC 语言（Python / Java / Go）：节点可以随便互相指，循环引用由运行时收；代价是对象头、停顿或写屏障。
- 无 GC（C++ / Rust）：所有权或智能指针决定「链表节点谁释放」；Rust 标准库不鼓励
LinkedList，多数场景Vec更快。 - 并发容器 是另一套实现：Java
ConcurrentHashMap、Gosync.Map、Rust 要自己加锁或用 crate。普通dict/HashMap不能当并发安全版本用。
4. 选型：先锁 ADT，再锁实现，最后才看语言
1 | 1. 操作是什么？随机访问 / 端点插删 / 按键查找 / 有序遍历 / 前缀 / 图关系 |
经验规则（先用这条，再谈例外）：
| 你真正要的 | 先选 |
|---|---|
| 按下标、追加、扫描 | 动态数组（list / vector / slice / Vec） |
| 只要后进先出 / 先进先出 | 栈 / 队列（底层仍是数组，除非题目逼你手写链表） |
| 按键查找，不要顺序 | 哈希表 |
| 按键查找，还要排序遍历 | 树或跳表（std::map / TreeMap / BTreeMap） |
| 每次取最大 / 最小 | 堆 |
| 点与边 | 邻接表（稠密到矩阵再考虑） |
| 前缀 | Trie |
| 磁盘有序索引 | B+ 树 |
链表在现代机器上 默认不是更快的选择：指针追逐打爆缓存。Java / C++ 标准库里的 LinkedList 仍然存在，是因为 ADT 需要，不是因为日常插入一定更快。
5. 自检
- 说出四大家族，并各举一个 ADT 与一种实现。
- 解释为什么 Python
list和 C++std::list不能当成同一种东西。 - 为什么「哈希表 (O(1))」在 Java 和 CPython 里写法相同，迭代顺序却不能假设相同？
- 把「我要一个 map」翻译成：有序还是散列、键是值还是对象、是否并发。
答不全就回到 §1 的三层表，不要直接背语言关键字。
6. 社区口径与风险
分类与复杂度以 CLRS、各语言标准库文档为口径，不另造分类法。开源对照可看 CPython listobject.c / dictobject.c、Go runtime/map.go、Rust hashbrown、OpenJDK HashMap.java。
风险：标准库实现会换代（Go 1.24 瑞士表、Java 8 树化、Python 3.7 字典保序）。本文记的是 2026 年主流实现的形状，写生产代码以你锁定的语言版本文档为准；不要把「当前 CPython 保序」推广成「所有哈希表都保序」。