抽象データ型（ADT）とは何であり、なぜそれを実装から分離するのか？

Question

IT Interview Practice · Accepted Answer

**抽象データ型**は、一連の値と、それらに対して許可された**操作**の集合を定義し、**動作**によってのみ記述されます — コードではなく。実装は、その動作を実現する具体的な構造（配列、連結リスト、木）です。

## 同じADT、異なる実装

```text
ADT "Queue":  enqueue, dequeue, peek  (FIFO contract)

Implementation A: array + two indices (ring buffer)
Implementation B: doubly linked list with head/tail pointers
Both honor the SAME contract; cost profiles differ.
```

## なぜ分離するのか

```python
# Callers depend on the CONTRACT, not the internals
class Stack:
    def push(self, x): ...
    def pop(self): ...
    def peek(self): ...
# Swap a list for a linked list internally — callers never change.
```

## 一般的なADTと一般的な実装

| ADT | 一般的な実装 |
|---|---|
| List | 動的配列、連結リスト |
| Stack | 配列、連結リスト |
| Queue | リングバッファ、連結リスト |
| Map | ハッシュテーブル、平衡木 |
| Priority Queue | 二分ヒープ |

## なぜ重要なのか

ADT（インターフェース）に対してプログラミングすることで、コードは柔軟に保たれます。後で実装を最適化できますし、呼び出し元を壊すことはありません。

また、推論を鋭くします — 最初に*どの動作*が必要かを決めて、その動作を提供する最も安価な構造を選択します。

ADT	一般的な実装
List	動的配列、連結リスト
Stack	配列、連結リスト
Queue	リングバッファ、連結リスト
Map	ハッシュテーブル、平衡木
Priority Queue	二分ヒープ

同じADT、異なる実装

なぜ分離するのか

関連する質問

一般的なADTと一般的な実装

なぜ重要なのか