데이터 구조란 무엇이며, 추상 데이터 타입(ADT)이란 무엇인가요?

Question

Accepted Answer

**데이터 구조(data structure)**는 데이터를 효율적으로 접근하고 수정할 수 있도록 메모리에 정리하고 저장하는 방식입니다. **추상 데이터 타입(abstract data type, ADT)**은 *논리적 모델*, 즉 연산과 그 동작을 의미하며, 실제로 어떻게 구현되는지와는 무관합니다.

## ADT 대 구현

ADT는 *어떤* 연산이 존재하는지를 기술하고, 데이터 구조는 그것을 *어떻게* 저장하고 얼마나 빠르게 동작하게 할지를 결정합니다.

```text
ADT: Stack            →  push, pop, peek (LIFO 동작)
구현:                 →  array 기반   또는   linked list 기반

ADT: List             →  get(i), insert, remove
구현:                 →  dynamic array  또는   linked list
```

## 코드에서 이 구분이 중요한 이유

```python
# 둘 다 "Stack" ADT를 만족하지만, 비용 프로파일이 다릅니다
stack = []          # list 기반 stack
stack.append(10)    # push  -> amortized O(1)
top = stack[-1]     # peek  -> O(1)
stack.pop()         # pop   -> O(1)
```

## 구조 선택하기

| 고려 사항 | 던져야 할 질문 |
|---|---|
| 접근 패턴 | 임의 접근인가, 순차 접근인가? |
| 변경 | 중간에서 자주 insert/delete 하는가? |
| 순서 | 정렬, FIFO, LIFO, 아니면 없음? |
| 조회 | index로 찾는가, key로 찾는가? |

올바른 선택은 작업 부하에서 **자주 쓰이는 연산이 저렴한** 구조입니다.

## 왜 중요한가

잘못된 구조를 선택하면 O(1) 연산이 O(n)이 되어, 규모가 커질수록 코드가 수천 배 느려질 수 있습니다.

ADT 관점에서 사고하면 먼저 *동작*을 기준으로 추론한 뒤, 나중에 호출 측을 다시 작성하지 않고도 구현을 교체할 수 있습니다.

고려 사항	던져야 할 질문
접근 패턴	임의 접근인가, 순차 접근인가?
변경	중간에서 자주 insert/delete 하는가?
순서	정렬, FIFO, LIFO, 아니면 없음?
조회	index로 찾는가, key로 찾는가?