추상 데이터 타입(ADT)이란 무엇이며, 왜 구현과 분리하나요?

Question

IT Interview Practice · Accepted Answer

**추상 데이터 타입(abstract data type)**은 값들의 집합과 그 위에서 허용되는 **연산**을 정의하며, 코드가 아니라 순수하게 **동작**으로 기술됩니다. 구현은 그 동작을 실현하는 구체적인 구조(array, linked list, tree)입니다.

## 같은 ADT, 다른 구현

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

구현 A: array + 두 개의 인덱스 (ring buffer)
구현 B: head/tail 포인터를 가진 doubly linked list
둘 다 같은 계약을 지키지만, 비용 프로파일이 다름.
```

## 왜 분리하는가

```python
# 호출 측은 내부 구현이 아니라 계약에 의존함
class Stack:
    def push(self, x): ...
    def pop(self): ...
    def peek(self): ...
# 내부적으로 list를 linked list로 교체해도 — 호출 측은 절대 바뀌지 않음.
```

## 흔한 ADT와 전형적인 구현

| ADT | 흔한 구현 |
|---|---|
| List | dynamic array, linked list |
| Stack | array, linked list |
| Queue | ring buffer, linked list |
| Map | hash table, balanced tree |
| Priority Queue | binary heap |

## 왜 중요한가

ADT(인터페이스)를 기준으로 프로그래밍하면 코드가 유연하게 유지됩니다. 나중에 호출 측을 깨뜨리지 않고 구현을 최적화할 수 있습니다.

또한 추론을 날카롭게 만듭니다. 먼저 *어떤 동작*이 필요한지 결정한 뒤, 그것을 제공하는 가장 저렴한 구조를 고르게 됩니다.

ADT	흔한 구현
List	dynamic array, linked list
Stack	array, linked list
Queue	ring buffer, linked list
Map	hash table, balanced tree
Priority Queue	binary heap

같은 ADT, 다른 구현

왜 분리하는가

관련 질문

흔한 ADT와 전형적인 구현

왜 중요한가