자료구조 투어 — 배열부터 그래프까지 10종
열 가지 구조를 '어떤 접근을 싸게 만들고 무엇을 대가로 치르는가'라는 한 질문으로 순례하며, 구조별 핵심 연산과 비용을 무대에 세운다.
1 / 12자료구조 열 개를 한 줄 질문으로 순례합니다 — "이 구조는 어떤 접근을 싸게 만들고, 무엇을 대가로 치르는가?"
배열연결 리스트스택큐디큐해시맵행렬이진 탐색 트리힙그래프
단계 목록 · 키보드 ←/→ 이동, Space 재생
자료구조 선택은 '가장 자주 하는 연산'이 정한다 — 각 구조는 특정 접근을 O(1)이나 O(log n)으로 만드는 대신 다른 접근을 포기한 거래의 결과다.
왜 헷갈리는가
"뭐든 배열이나 해시맵이면 되지 않나"가 절반의 진실이라 위험하다 — 실제로 대부분은 된다. 하지만 '정렬을 유지하며 넣고 빼기'(BST), '최솟값만 반복해 꺼내기'(힙), '양끝 모두'(디큐)가 필요한 순간 배열은 O(n)의 늪이 된다. 반대 함정: 연결 리스트가 이론상 삽입 O(1)이지만 캐시 지역성 탓에 실측에서는 배열에 지는 일이 흔하다.
열 구조의 거래표
각 구조가 산 것과 판 것.
- 배열: 번호 접근 O(1)을 사고 중간 삽입 O(n)을 팔았다. 연속 메모리 = 캐시 친화 — 현대 CPU에서 과소평가 금물.
- 연결 리스트: 위치를 아는 삽입 O(1)을 사고 접근 O(n)+캐시 불리를 팔았다. LRU 캐시(해시맵과 결합)가 대표 서식지.
- 스택/큐/디큐: 구조가 아니라 '규율'이다 — 최근 것(실행 취소·콜스택), 공정한 순서(작업 큐·BFS), 양끝(슬라이딩 윈도우 최댓값).
- 해시맵: 키 조회 평균 O(1)을 사고 순서를 팔았다. 실무 자료구조의 왕 — 하지만 순회 순서에 의존하는 코드는 시한폭탄.
- BST(균형): 정렬 유지 + O(log n) 삽입·검색·범위 질의 — DB 인덱스(B-트리)와 언어의 TreeMap이 이 거래다.
- 힙: '최솟값이 누구인가'만 O(1) — 전체 정렬을 유지하지 않는 것이 요령. 우선순위 큐·Top-K·다익스트라·스케줄러.
- 행렬/그래프: 격자 세상과 관계 세상의 원자재 — 표현(인접 리스트 vs 행렬)부터가 공간-시간 거래다.
면접·실무에서 고르는 법
"이 데이터에 가장 자주 하는 질문이 무엇인가"를 먼저 적어라. '키로 찾기'가 대부분이면 해시맵, '순서대로 처리'면 큐, '최근 것 우선'이면 스택, '정렬 상태로 범위를 묻기'면 트리, '최댓값·최솟값만'이면 힙이다. 두 질문이 겹치면 구조를 합성한다 — LRU 캐시(해시맵+이중 연결 리스트), 우선순위 작업 큐(힙+해시맵)가 그 예다.
기억할 것
- 구조 선택 = 가장 잦은 연산의 최적화. 만능 구조는 없다.
- 배열의 캐시 지역성은 Big-O 표에 없는 실전 무기다.
- 힙은 '전부 정렬'이 아니라 '꼭대기만 보장' — 그래서 싸다.
- 복합 요구는 구조의 합성으로 푼다 — LRU = 해시맵 + 연결 리스트.