자료구조 — 데이터를 담는 그릇들
목차
자료구조 — 데이터를 담는 그릇들
프로그래밍 입문에서 변수와 함수 다음으로 자주 만나는 주제가 자료구조. 같은 데이터를 어떤 그릇에 담느냐에 따라 코드의 단순함과 속도가 크게 달라집니다. 이 글은 자주 쓰이는 자료구조 9 가지의 정의 · 동작 · 시간 복잡도와 언어별 표준 구현, 입문에서 헷갈리기 쉬운 자리.
1. 자료구조에 대한 이야기
데이터를 메모리에 어떻게 담고 어떻게 접근할지의 약속. 대부분의 현대 언어는 핵심 자료구조를 표준 라이브러리로 제공하므로 직접 구현하는 일은 드물지만, 무엇이 안에서 일어나는지를 아는 만큼 적절한 도구를 고를 수 있습니다.
기초 자료구조에 대한 정전 텍스트로 자주 권장되는 자료는 Cormen · Leiserson · Rivest · Stein 의 Introduction to Algorithms (1990 초판, 약칭 CLRS) 와 Robert Sedgewick 의 Algorithms (1983 초판).
2. 배열
연속된 메모리 칸의 묶음. 인덱스로 임의 접근이 빠름.
| 연산 | 시간 |
|---|---|
| 인덱스로 접근 | O(1) |
| 끝에 추가 (amortized) | O(1) |
| 중간 삽입 / 삭제 | O(n) — 뒤쪽이 모두 한 칸 밀림 |
| 탐색 (정렬 안 됨) | O(n) |
언어별 — JS Array · Python list · Java ArrayList · C++ std::vector.
3. 연결 리스트
각 노드가 다음 노드의 참조를 가지는 형태. 단일 · 이중 · 원형이 있음.
| 연산 | 시간 |
|---|---|
| 인덱스 접근 | O(n) |
| 끝 / 앞에 삽입 (포인터 보유 시) | O(1) |
| 중간 삽입 / 삭제 (노드 보유 시) | O(1) |
| 탐색 | O(n) |
배열에 비해 임의 접근이 느리고 캐시 친화성도 떨어져, 모던 환경에서는 동적 배열에 밀리는 경우가 많음. 큐 · LRU 같은 자리에서는 여전히 유용.
언어별 — Java LinkedList · C++ std::list. JS · Python 의 표준에는 없으며 직접 구현 또는 collections.deque 가 비슷한 역할.
4. 해시 테이블
키를 해시 함수에 넣어 인덱스를 만드는 자료구조. 평균 O(1) 의 조회 · 삽입.
| 연산 | 평균 | 최악 |
|---|---|---|
| 조회 | O(1) | O(n) — 모든 키가 같은 버킷에 몰릴 때 |
| 삽입 | O(1) | O(n) |
| 삭제 | O(1) | O(n) |
해시 충돌 처리는 체이닝 (연결 리스트) 또는 오픈 어드레싱 (다음 빈 칸 탐색) 이 일반적. 모던 언어 표준 구현 대부분은 충돌 시에도 좋은 분포를 유지하도록 설계.
언어별 — JS Map · 객체 ({}) · Python dict · set · Java HashMap · HashSet · C++ std::unordered_map.
5. 스택
LIFO (Last In, First Out). 함수 호출 · 되돌리기 (Undo) · 깊이 우선 탐색.
push(1) → [1]
push(2) → [1, 2]
push(3) → [1, 2, 3]
pop() → [1, 2], 반환 3
배열로 쉽게 구현 가능. JS array.push / array.pop · Python list.append / list.pop.
6. 큐
FIFO (First In, First Out). 작업 큐 · 너비 우선 탐색.
enqueue(1) → [1]
enqueue(2) → [1, 2]
dequeue() → [2], 반환 1
배열의 앞에서 빼는 작업은 O(n) 이라 큰 큐에는 비효율. Python collections.deque · Java ArrayDeque 가 양쪽 O(1) 을 지원.
7. 트리
각 노드가 0 개 이상 자식을 가지는 비순환 그래프. 자주 쓰이는 갈래:
- 이진 트리 (Binary Tree) — 자식이 최대 2 개.
- 이진 탐색 트리 (BST) — 좌측은 작은 값, 우측은 큰 값. 평균 조회 O(log n), 최악 O(n) (편향 트리).
- 자가 균형 트리 — AVL · 레드-블랙 트리. 항상 O(log n) 보장.
- B-트리 / B+트리 — DB 인덱스의 사실상 표준.
- 힙 (Heap) — 부모가 자식보다 항상 크거나 작음. 우선순위 큐의 토대. 삽입 · 최댓값 추출 모두 O(log n).
- 트라이 (Trie) — 문자열의 공통 접두사를 공유. 자동완성 · 사전.
8. 그래프
노드와 간선의 일반적 형태. 방향 / 무방향, 가중치 유무로 구분.
표현 방식:
- 인접 행렬 — N × N. 밀집 그래프에 유리. 공간 O(N²).
- 인접 리스트 — 각 노드의 이웃 리스트. 희소 그래프에 유리. 공간 O(V+E).
대표 알고리즘 — BFS · DFS · Dijkstra · Bellman-Ford · 위상 정렬 · MST (Kruskal · Prim).
9. 시간 복잡도 한눈에
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열 | O(1) | O(n) | O(n) | O(n) |
| 연결 리스트 | O(n) | O(n) | O(1)* | O(1)* |
| 해시 테이블 | — | O(1) avg | O(1) avg | O(1) avg |
| 이진 탐색 트리 | O(log n) avg | O(log n) avg | O(log n) avg | O(log n) avg |
| 균형 트리 (AVL · RB) | O(log n) | O(log n) | O(log n) | O(log n) |
| 힙 | — | O(n) | O(log n) | O(log n) |
(* 노드 참조를 이미 가지고 있을 때)
10. 다른 길
특수 자료구조:
- 블룸 필터 — 확률적 멤버십 테스트. false positive 허용, false negative 없음.
- 스킵 리스트 — 균형 트리 대신 사용. Redis 의 sorted set.
- 세그먼트 트리 · 펜윅 트리 (BIT) — 구간 합 · 최솟값 등.
- Disjoint Set (Union-Find) — 그룹 합치기. Kruskal 의 부품.
- LRU 캐시 — 해시 + 이중 연결 리스트의 조합.
11. 자주 쓰는 모양
// JS
const arr = [1, 2, 3];
arr.push(4);
const map = new Map();
map.set("k", 1);
map.get("k");
map.has("k");
const set = new Set([1, 2, 2, 3]); // {1, 2, 3}
const stack = [];
stack.push(1); stack.push(2);
stack.pop();
# Python
arr = [1, 2, 3]
arr.append(4)
d = {"k": 1}
"k" in d
s = {1, 2, 2, 3}
from collections import deque
q = deque([1, 2, 3])
q.append(4); q.popleft()
import heapq
h = []; heapq.heappush(h, 3); heapq.heappush(h, 1)
heapq.heappop(h) # 1 (최소 힙)
// Java
ArrayList<Integer> arr = new ArrayList<>();
arr.add(1);
HashMap<String, Integer> map = new HashMap<>();
map.put("k", 1);
HashSet<Integer> set = new HashSet<>();
ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.poll();
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 최소 힙
TreeMap<String, Integer> sorted = new TreeMap<>(); // 정렬된 키
12. 자주 걸리는 자리
JS 객체 vs Map — {} 는 키가 문자열 · 심볼만, 프로토타입 오염 가능, 순서 약속이 약함. 데이터용 키-값에는 Map 권장.
Python list 의 앞에서 pop — list.pop(0) 은 O(n). 큐가 필요하면 deque.
Java Vector · Hashtable — 동기화된 레거시. 대신 ArrayList · HashMap. 동시성이 필요하면 ConcurrentHashMap.
해시 충돌 가정 — 사용자 입력에서 키가 만들어진다면 의도적 충돌 공격 (HashDoS) 가능. 모던 언어 대부분이 랜덤 해시 시드로 막아 두지만 가정은 알아 두는 편.
트리 · 해시의 구분 못 함 — "해시 테이블이 빠른데 왜 트리?" — 정렬된 순회 · 범위 쿼리 · 일관된 최악 시간이 필요하면 트리.
메모리 — 빠른 자료구조는 메모리 부담이 큼. 모바일 · 임베디드는 균형이 다름.
하고픈 말
자료구조는 데이터를 담는 그릇. 직접 구현은 드물지만 무엇이 안에서 일어나는지를 아는 만큼 적절한 도구를 고를 수 있습니다. 배열 · 해시 테이블 · 트리 (힙 · BST · B-tree) · 그래프의 네 가지가 일상의 90 %. 메모리 vs 속도의 트레이드오프는 환경 (서버 / 모바일 / 임베디드) 에 따라.
Next
- big-o
- design-patterns
Introduction to Algorithms (CLRS) · Algorithms (Robert Sedgewick) · VisuAlgo · Data Structure Visualizations (University of San Francisco) · LeetCode · HackerRank · 백준 · NeetCode 150 · MDN JS Map · Set · Python collections 모듈 · Java Collections Framework 을 참고합니다.