什么是数据结构，什么是抽象数据类型（ADT）？

Question

Accepted Answer

**data structure** 是一种在内存中组织和存储数据的方式，以便能够高效地访问和修改数据。**abstract data type (ADT)** 是*逻辑模型* — 操作及其行为 — 独立于其实现方式。

## ADT vs implementation

ADT 描述了*哪些*操作存在；data structure 决定了*如何*存储它们以及运行速度有多快。

```text
ADT: Stack            →  push, pop, peek (LIFO behavior)
Implementations:      →  array-backed   OR   linked-list-backed

ADT: List             →  get(i), insert, remove
Implementations:      →  dynamic array  OR   linked list
```

## 在代码中为什么这种区别很重要

```python
# Both satisfy the "Stack" ADT, but have different cost profiles
stack = []          # list-backed stack
stack.append(10)    # push  -> amortized O(1)
top = stack[-1]     # peek  -> O(1)
stack.pop()         # pop   -> O(1)
```

## 选择一个结构

| 考虑因素 | 需要提出的问题 |
|---|---|
| 访问模式 | 随机访问还是顺序访问？ |
| 修改 | 频繁在中间插入/删除？ |
| 排序 | 有序、FIFO、LIFO 还是无序？ |
| 查询 | 按索引还是按 key？ |

正确的选择是那个**常见操作成本最低**的结构，用于你的工作负载。

## 为什么这很重要

选择错误的结构会将 O(1) 操作变成 O(n)，这可能在大规模情况下使代码慢数千倍。

以 ADT 的方式思考让你先推理*行为*，然后稍后可以交换实现而无需重写调用者。

考虑因素	需要提出的问题
访问模式	随机访问还是顺序访问？
修改	频繁在中间插入/删除？
排序	有序、FIFO、LIFO 还是无序？
查询	按索引还是按 key？