データ構造とは何か、また抽象データ型(ADT)とは何か？

Question

Accepted Answer

**データ構造**は、データをメモリに組織して保存し、効率的にアクセスして変更できるようにする方法です。**抽象データ型(ADT)**は、*論理モデル*——操作とその動作——であり、実装方法に依存しません。

## ADT vs 実装

ADTは*どのような*操作が存在するかを記述します。データ構造は、*どのように*保存され、どのくらい高速に実行されるかを決定します。

```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、なし？ |
| ルックアップ | インデックスまたはキーで？ |

正しい選択は、ワークロードに対して**一般的な操作が安価**なものです。

## なぜ重要なのか

間違った構造を選ぶと、O(1)操作がO(n)に変わり、スケール時にコードを数千倍遅くする可能性があります。

ADTの観点で考えることで、まず*動作*について推論でき、後で呼び出し元を書き直さずに実装を切り替えることができます。

考慮事項	検討する質問
アクセスパターン	ランダムアクセスまたはシーケンシャルアクセス？
変更	中間への頻繁な挿入/削除？
順序	ソート済み、FIFO、LIFO、なし？
ルックアップ	インデックスまたはキーで？