개발자 기술 면접을 위한 필수 자료구조 15가지 핵심 정리와 시각화

기술 면접과 백엔드 실무 성능을 관통하는 15대 필수 자료구조 완벽 정리! 메모리 캐시 지역성, 배열·연결리스트, 스택·큐·덱, 해시테이블, 트리(BST·AVL·RB·B+Tree), 힙, 트라이, 그래프, 유니온파인드, 블룸필터의 원리를 직관적인 다이어그램과 코드로 해설합니다.
IT·과학
저자

Ikmyungterran

공개

2026년 7월 9일

Modified

2026년 10월 18일

0. 자료구조는 ’데이터를 담는 그릇’이다

주방을 요리하는 공간이라고 할 때: * 알고리즘이 맛있는 음식을 만드는 ‘조리 레시피(절차)’라면, * 자료구조는 신선한 식재료를 보관하는 ‘냉장고와 밀폐용기(그릇)’입니다.

식재료가 뒤죽박죽 엉망으로 널브러져 있다면 아무리 뛰어난 셰프라도 재료를 찾는 데 시간을 다 허비합니다. 데이터를 컴퓨터 메모리(RAM)에 어떻게 정돈해 두느냐에 따라 프로그램의 처리 속도가 수천 배 달라집니다.

graph TD
    RAM["컴퓨터 주기억장치 (RAM): 번호가 붙은 거대한 물리 주소 공간"] --> Continuous["연속 메모리 할당: 배열(Array) 계열"]
    RAM --> Discontinuous["불연속 포인터 연결: 노드(Node) 기반 계열"]
    Continuous --> CacheWin["CPU 캐시 공간 지역성(Spatial Locality) 극대화"]
    Discontinuous --> MemoryFlex["동적 크기 할당 및 빈번한 삽입·삭제의 유연성"]
    style RAM fill:#F1F5F9,stroke:#475569,stroke-width:2px;
    style Continuous fill:#DCFCE7,stroke:#16A34A,stroke-width:2px;
    style Discontinuous fill:#FEF3C7,stroke:#D97706,stroke-width:2px;
    style CacheWin fill:#BAE6FD,stroke:#0284C7,stroke-width:1px;
    style MemoryFlex fill:#F3E8FF,stroke:#9333EA,stroke-width:1px;

1. 배열 (Array) & 동적 배열 (Dynamic Array / Vector)

배열은 동일한 타입의 데이터를 메모리에 빈틈없이 연속적으로 나란히 배치하는 가장 기초적인 선형 자료구조입니다.

  • 동작 원리: 배열의 시작 메모리 주소와 인덱스만 알면 시작주소 + (인덱스 * 요소크기) 수식으로 물리 주소를 즉시 계산합니다.
  • 시간 복잡도:
    • 임의 인덱스 조회 (Lookup): \(O(1)\)
    • 맨 끝 삽입/삭제: 분할 상환 \(O(1)\)
    • 중간 삽입/삭제: \(O(N)\) (뒤의 모든 데이터를 한 칸씩 밀거나 당겨야 함)
  • 동적 배열의 Doubling 전략: 정적 배열과 달리 용량(Capacity)이 가득 차면 2배 크기의 새로운 연속 메모리를 할당받아 기존 데이터를 통째로 복사합니다.
# 파이썬 List(동적 배열)의 인덱스 접근과 중간 삽입 비교
nums = [10, 20, 30, 40, 50]
val = nums[2]          # O(1) 즉각 조회: 30
nums.insert(2, 99)     # O(N) 비용 발생: 30, 40, 50을 오른쪽으로 한 칸씩 이동
힌트🚀 CPU 캐시 라인과 공간 지역성

현대 CPU는 RAM에서 데이터를 1바이트씩 가져오지 않고, 64바이트 덩어리(Cache Line)를 통째로 L1/L2 캐시로 퍼옵니다. 배열은 데이터가 메모리에 나란히 붙어 있으므로 다음 원소가 이미 캐시에 들어 있어 CPU 연산이 압도적으로 빠릅니다.

2. 단일 / 이중 연결 리스트 (Linked List)

연결 리스트는 연속된 메모리 공간을 쓰지 않고, 데이터와 다음 노드의 주소(Pointer)를 담은 개별 노드(Node)들을 줄줄이 엮어 놓은 구조입니다.

  • 동작 원리: 단일 연결 리스트는 Next 포인터만 가지며, 이중 연결 리스트(Doubly Linked List)는 Prev와 Next 양방향 포인터를 가집니다.
  • 시간 복잡도:
    • 특정 노드 탐색: \(O(N)\) (Head부터 순차적으로 타고 가야 함)
    • 이미 위치를 아는 노드의 삽입/삭제: \(O(1)\) (포인터 2개만 갈아 끼우면 끝)
  • 실무 활용: 음악 플레이어의 이전 곡/다음 곡 재생, LRU 캐시 구현체, 운영체제 메모리 관리 프리 리스트.
class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

# O(1) 노드 연결 삽입 예시
def insert_after(node, new_node):
    new_node.next = node.next
    new_node.prev = node
    if node.next:
        node.next.prev = new_node
    node.next = new_node

3. 스택 (Stack - LIFO)

스택은 ‘가장 마지막에 넣은 데이터가 가장 먼저 나오는(Last-In, First-Out)’ 후입선출 자료구조입니다. 바닥이 막힌 프링글스 감자칩 통에 비유할 수 있습니다.

graph LR
    subgraph StackOperation["스택(Stack)의 LIFO 동작 메커니즘"]
        In["PUSH(데이터 입력)"] --> Top["[ 노드 3 ] (Top 포인터)"]
        Top --> Mid["[ 노드 2 ]"]
        Mid --> Bottom["[ 노드 1 ] (Bottom 바닥)"]
        Top --> Out["POP(최근 데이터 추출)"]
    end
    style StackOperation fill:#FEF3C7,stroke:#D97706,stroke-width:2px;

  • 시간 복잡도: push(), pop(), peek() 모두 \(O(1)\)
  • 실무 활용:
    • 브라우저의 ‘뒤로 가기(Back)’ 이력 히스토리
    • 텍스트 편집기의 실행 취소(Ctrl + Z / Undo)
    • 컴파일러/인터프리터의 괄호 유효성 검사 및 수식 파싱
    • 프로그래밍 언어의 함수 호출 스택(Call Stack)

4. 큐 (Queue - FIFO)

큐는 ‘먼저 들어온 데이터가 먼저 나가는(First-In, First-Out)’ 선입선출 자료구조입니다. 은행 창구나 매표소의 대기 줄과 같습니다.

  • 동작 원리: 뒤(Rear/Tail)에서 Enqueue로 데이터를 넣고, 앞(Front/Head)에서 Dequeue로 데이터를 꺼냅니다.
  • 시간 복잡도: enqueue(), dequeue() 모두 \(O(1)\)
  • 원형 큐(Circular Queue): 일반 배열 기반 큐는 Dequeue 시 앞쪽 공간이 낭비되므로, 배열의 끝과 시작을 모듈로(index % size) 연산으로 이어붙여 메모리를 재사용합니다.
  • 실무 활용: 프린터 출력 대기열, 백엔드 비동기 작업 큐(Celery, RabbitMQ), 웹 서버의 HTTP 연결 대기열, BFS 그래프 탐색.

5. 덱 (Deque - Double-Ended Queue)

덱은 양쪽 끝(Front와 Rear) 모두에서 삽입과 삭제가 \(O(1)\)로 가능한 만능 자료구조입니다.

  • 동작 원리: 스택과 큐의 특성을 모두 지니고 있어, 상황에 따라 스택으로도 큐로도 동작할 수 있습니다.
  • 시간 복잡도: append(), appendleft(), pop(), popleft() 모두 \(O(1)\)
  • 실무 활용: 슬라이딩 윈도우 알고리즘의 최댓값/최솟값 추적, 웹 브라우저의 앞/뒤 방문 기록 관리, 실시간 주식 호가 주문 버퍼.
from collections import deque

d = deque([1, 2, 3])
d.appendleft(0)   # 앞단 삽입: O(1) -> [0, 1, 2, 3]
d.pop()           # 뒷단 추출: O(1) -> 3 반환

6. 해시 테이블 (Hash Table & Hash Map)

해시 테이블은 임의의 길이의 키(Key)를 해시 함수(Hash Function)를 거쳐 고정 크기의 정수 인덱스로 변환한 뒤, 배열(Bucket)에 값(Value)을 저장하는 자료구조입니다.

sequenceDiagram
    autonumber
    participant Key as 입력 키: "user_102"
    participant HashFn as 해시 함수 murmur3()
    participant Bucket as 해시 버킷 배열 (RAM)

    Key->>HashFn: "user_102" 문자열 전달
    HashFn-->>Bucket: 해시값 % 버킷크기 -> 슬롯 5번 계산!
    Bucket-->>Key: 5번 버킷 데이터 '{"name": "Alice"}' 반환 (O(1))

  • 시간 복잡도: 평균 조회/삽입/삭제 \(O(1)\), 해시 충돌 최악의 경우 \(O(N)\)
  • 해시 충돌(Collision) 해결 2대 기법:
    1. 개별 체이닝 (Separate Chaining): 충돌이 난 버킷 뒤에 연결 리스트나 Red-Black 트리를 달아 데이터를 줄줄이 엮습니다. (Java HashMap 표준)
    2. 개방 주소법 (Open Addressing): 충돌이 나면 다른 빈 버킷 슬롯을 찾아 들어갑니다. (선형 탐사, 제곱 탐사, 이중 해싱)

7. 이진 탐색 트리 (BST - Binary Search Tree)

이진 탐색 트리는 각 노드가 최대 2개의 자식을 가지며, “왼쪽 서브트리의 모든 노드는 부모보다 작고, 오른쪽 서브트리의 모든 노드는 부모보다 크다”는 불변식을 유지하는 계층 구조입니다.

graph TD
    Root["[ 50 ] 루트"] --> Left["[ 30 ] (작은 값)"]
    Root --> Right["[ 70 ] (큰 값)"]
    Left --> L1["[ 20 ]"]
    Left --> L2["[ 40 ]"]
    Right --> R1["[ 60 ]"]
    Right --> R2["[ 80 ]"]
    style Root fill:#E0F2FE,stroke:#0284C7,stroke-width:2px;
    style Left fill:#DCFCE7,stroke:#16A34A,stroke-width:1px;
    style Right fill:#FEF3C7,stroke:#D97706,stroke-width:1px;

  • 시간 복잡도:
    • 균형 상태: 탐색/삽입/삭제 모두 \(O(\log N)\)
    • 편향 트리(Degenerate Tree): 정렬된 순서대로 [1, 2, 3, 4, 5]가 들어오면 한쪽으로 늘어서 연결 리스트처럼 타락하여 \(O(N)\)으로 성능이 붕괴됩니다.

8. AVL 트리 (AVL Tree)

AVL 트리는 편향 트리의 성능 저하를 막기 위해 발명된 최초의 자가 균형 이진 탐색 트리(Self-Balancing BST)입니다.

  • 동작 원리: 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이(Balance Factor)가 \(-1, 0, 1\) 중 하나를 유지해야 합니다.
  • 트리 회전 (Rotation): 높이 차이가 2 이상 벌어지면 LL, RR, LR, RL의 4가지 패턴에 따라 노드를 즉시 회전(Left/Right Rotation)시켜 강제로 균형을 복구합니다.
  • 시간 복잡도: 최악의 경우에도 항상 엄격한 높이 균형을 유지하여 \(O(\log N)\)을 보장합니다.

9. 레드-블랙 트리 (Red-Black Tree)

레드-블랙 트리는 AVL 트리보다 회전 비용을 줄이면서도 실용적으로 높이 균형을 유지하는 가장 대표적인 균형 이진 탐색 트리입니다.

  • 5대 불문율:
    1. 모든 노드는 빨간색(Red)이거나 검은색(Black)이다.
    2. 루트 노드는 항상 검은색이다.
    3. 모든 리프(NIL) 노드는 검은색이다.
    4. 빨간색 노드의 자식은 반드시 검은색이어야 한다. (빨간 노드가 연속 2번 올 수 없음, No Double Red)
    5. 임의의 노드에서 리프 노드에 이르는 모든 경로의 검은색 노드 개수는 동일하다.
  • 실무 활용: C++ STL의 std::map과 std::set, Java의 TreeMap, 리눅스 커널의 CPU 프로세스 스케줄러(CFS).

10. B-Tree & B+Tree (데이터베이스 인덱스 엔진)

메모리가 아닌 하드디스크/SSD의 블록 I/O를 최소화하기 위해 고안된 다진 탐색 트리(Multi-way Search Tree)입니다. MySQL(InnoDB), PostgreSQL, SQLite 등 거의 모든 관계형 데이터베이스의 핵심 인덱스 엔진입니다.

graph TD
    subgraph NonLeaf["내부 브랜치 노드: 키와 자식 페이지 주소만 보관"]
        Root["[ 30 | 70 ]"]
    end
    subgraph LeafLayer["리프 노드: 실제 레코드 포인터 보관 + 양방향 연결 리스트 링크"]
        L1["[ 10, 20 ]"] --- L2["[ 35, 50, 60 ]"] --- L3["[ 75, 80, 90 ]"]
    end
    Root --> L1
    Root --> L2
    Root --> L3
    style NonLeaf fill:#F1F5F9,stroke:#475569,stroke-width:1px;
    style LeafLayer fill:#DCFCE7,stroke:#16A34A,stroke-width:2px;

  • B+Tree의 결정적 강점:
    1. 실제 데이터 레코드는 가장 밑바닥의 리프 노드(Leaf Node)에만 저장됩니다.
    2. 리프 노드들끼리 양방향 연결 리스트(Linked List)로 촘촘히 엮여 있습니다.
    3. 따라서 WHERE age BETWEEN 20 AND 50과 같은 범위 스캔(Range Scan)을 수행할 때 트리를 거슬러 올라갈 필요 없이 리프 노드만 옆으로 순차 탐색하여 수십만 건을 순식간에 긁어옵니다.

11. 이진 힙 (Binary Heap) & 우선순위 큐 (Priority Queue)

힙은 완전 이진 트리(Complete Binary Tree)를 기반으로 하여 최댓값 또는 최솟값을 \(O(1)\)만에 즉시 꺼내기 위해 최적화된 자료구조입니다.

  • 최대 힙 (Max Heap): 부모 노드의 키가 자식 노드보다 항상 크거나 같습니다. 루트 노드에 전체 최댓값이 위치합니다.
  • 최소 힙 (Min Heap): 루트 노드에 전체 최솟값이 위치합니다.
  • 배열 구현의 묘미: 포인터 없이 1차원 배열로 완벽히 표현됩니다.
    • 부모 노드 인덱스: i // 2
    • 왼쪽 자식 인덱스: 2 * i
    • 오른쪽 자식 인덱스: 2 * i + 1
  • 시간 복잡도: 최댓값/최솟값 조회 \(O(1)\), 원소 삽입 및 추출 \(O(\log N)\)
  • 실무 활용: 다익스트라 최단 경로 알고리즘, 운영체제 태스크 스케줄링, 허프만 압축 코딩.

12. 트라이 (Trie / Prefix Tree)

트라이는 문자열 집합을 트리 형태로 저장하여 문자열 검색과 접두사(Prefix) 일치 여부를 초고속으로 판별하는 탐색 트리입니다.

graph TD
    Root["(Root)"] --> C["'c'"]
    Root --> A["'a'"]
    C --> CA["'a'"]
    CA --> CAT["'t' [단어완성: cat]"]
    CA --> CAR["'r' [단어완성: car]"]
    A --> AP["'p'"]
    AP --> APP["'p' [단어완성: app]"]
    style CAT fill:#BAE6FD,stroke:#0284C7,stroke-width:2px;
    style CAR fill:#BAE6FD,stroke:#0284C7,stroke-width:2px;
    style APP fill:#BAE6FD,stroke:#0284C7,stroke-width:2px;

  • 동작 원리: 문자열의 각 글자가 노드가 되며, 공통 접두사를 공유하므로 메모리를 절약하고 탐색 속도를 극대화합니다.
  • 시간 복잡도: 문자열 길이가 \(M\)일 때 탐색 시간은 문자열 개수 \(N\)과 무관하게 \(O(M)\)입니다.
  • 실무 활용: 검색창의 검색어 자동완성(Autocomplete), 맞춤법 검사기, IP 라우팅 최장 접두사 일치(LPM).

13. 그래프 (Graph - 인접 행렬 vs 인접 리스트)

그래프는 정점(Vertex)과 이들을 잇는 간선(Edge)으로 데이터 간의 복잡한 연결 관계를 나타내는 비선형 자료구조입니다.

구분 인접 행렬 (Adjacency Matrix) 인접 리스트 (Adjacency List)
표현 방식 2차원 불리언 배열 adj[u][v] 각 정점마다 연결된 이웃 노드를 담은 연결 리스트/벡터
공간 복잡도 \(O(V^2)\) (간선이 적어도 메모리 낭비) \(O(V + E)\) (실제 존재하는 간선만큼만 차지)
간선 존재 여부 (\(u \rightarrow v\)) \(O(1)\) (행렬 즉시 확인) \(O(\text{degree}(u))\) (이웃 리스트 순회)
모든 인접 노드 순회 \(O(V)\) (해당 행 전체 스캔) \(O(\text{degree}(u))\) (이웃만 즉시 순회)
추천 상황 간선이 빽빽한 밀집 그래프(Dense Graph) 대부분의 실무 그래프 (희소 그래프 Sparse Graph)

14. 유니온-파인드 (Disjoint Set / Union-Find)

상호 배타적인 집합(Disjoint Set)들을 관리하며, “두 원소가 같은 그룹에 속해 있는가?”를 실시간으로 판별하는 트리 기반 자료구조입니다.

  • 핵심 연산:
    • Find(x): 원소 \(x\)가 속한 집합의 대표자(루트 노드)를 찾습니다.
    • Union(x, y): \(x\)가 속한 집합과 \(y\)가 속한 집합을 하나로 합칩니다.
  • 2대 성능 최적화 기법:
    1. 경로 압축 (Path Compression): Find 연산을 수행할 때 방문한 모든 노드를 루트 노드 바로 밑에 직접 연결해 트리를 납작하게 만듭니다.
    2. Rank 기반 결합 (Union by Rank): 높이가 낮은 트리를 높이가 높은 트리 밑에 붙여 트리의 높이 증가를 억제합니다.
  • 시간 복잡도: 아커만 함수의 역함수인 \(\alpha(N)\)에 수렴하여 실질적으로 \(O(1)\)에 가깝습니다.
  • 실무 활용: 크루스칼(Kruskal) 최소 신장 트리(MST) 알고리즘의 사이클 감지, 네트워크 연결성 검사, 이미지 세분화(Segmentation).

15. 블룸 필터 (Bloom Filter)

블룸 필터는 “원소가 집합에 포함되어 있는지”를 극소량의 메모리로 판별하는 확률적 자료구조(Probabilistic Data Structure)입니다.

  • 동작 원리:
    1. 거대한 \(M\)비트 크기의 0으로 초기화된 비트 배열을 준비합니다.
    2. 원소가 들어오면 \(K\)개의 독립적인 해시 함수를 통과시켜 나온 \(K\)개의 비트 슬롯을 1로 세팅합니다.
    3. 조회를 할 때 \(K\)개 슬롯 중 단 하나라도 0이면 그 원소는 100% 집합에 존재하지 않습니다.
    4. \(K\)개 슬롯이 모두 1이면 “아마도 존재할 것”입니다. (거짓 양성 False Positive 가능성 존재, 단 거짓 음성은 절대 없음!)
  • 실무 활용:
    • 웹 크롤러의 방문 URL 중복 검사 (수십억 개 URL을 수 MB로 압축 검사)
    • Google Bigtable, Apache Cassandra의 디스크 I/O 방어 (SSTable에 데이터가 없는 경우 디스크를 읽지 않고 즉시 거절)
    • CDN 캐시 스탬피드 방어 및 악성 URL 피싱 필터

15대 자료구조 시간 복잡도 총괄 매트릭스

자료구조 탐색 (Lookup) 삽입 (Insert) 삭제 (Delete) 주요 장점 및 핵심 권장 실무 사례
1. 배열 \(O(1)\) \(O(N)\) \(O(N)\) 연속 메모리, 뛰어난 CPU 캐시 적중률, 정적 인덱싱
2. 연결 리스트 \(O(N)\) 위치 알 때 \(O(1)\) 위치 알 때 \(O(1)\) 동적 크기, 중간 삽입/삭제 시 메모리 이동 비용 0
3. 스택 \(O(N)\) \(O(1)\) \(O(1)\) LIFO, 괄호 검사, 뒤로가기, 함수 호출 제어
4. 큐 \(O(N)\) \(O(1)\) \(O(1)\) FIFO, 작업 버퍼, 인쇄 대기열, BFS 그래프 탐색
5. 덱 \(O(N)\) \(O(1)\) \(O(1)\) 양단 \(O(1)\) 삽입/추출, 슬라이딩 윈도우 최댓값
6. 해시 테이블 평균 \(O(1)\) 평균 \(O(1)\) 평균 \(O(1)\) 고유 Key 기반 초고속 검색, 캐시 및 딕셔너리
7. BST 평균 \(O(\log N)\) 평균 \(O(\log N)\) 평균 \(O(\log N)\) 계층 정렬, 편향 시 \(O(N)\)으로 타락 위험
8. AVL 트리 \(O(\log N)\) \(O(\log N)\) \(O(\log N)\) 엄격한 높이 균형 유지, 검색 빈도가 극도로 높은 환경
9. Red-Black Tree \(O(\log N)\) \(O(\log N)\) \(O(\log N)\) 삽입/삭제 회전 비용 절감, C++ std::map, Java TreeMap
10. B+Tree \(O(\log N)\) \(O(\log N)\) \(O(\log N)\) 리프 노드 양방향 체이닝, RDBMS 디스크 인덱스 및 범위 스캔
11. 이진 힙 최댓값: \(O(1)\) \(O(\log N)\) \(O(\log N)\) 우선순위 큐, 실시간 스케줄러, 다익스트라 알고리즘
12. 트라이 \(O(M)\) \(O(M)\) \(O(M)\) 접두사(Prefix) 일치, 검색어 자동완성, 사전 매칭
13. 그래프 \(O(V+E)\) \(O(1)\) \(O(E)\) 관계망 분석, 네트워크 라우팅, 소셜 네트워크 추천
14. 유니온-파인드 \(\approx O(1)\) \(\approx O(1)\) - 상호 배타 집합 판별, 최소 신장 트리(크루스칼) 사이클 검사
15. 블룸 필터 \(O(K)\) \(O(K)\) 지원 안 함 초소형 메모리, 디스크 I/O 사전 차단, 거짓 음성 0%

📚 참고 문헌 및 공식 출처

구분 자료명 주요 내용 링크
자료구조 바이블 Fundamentals of Data Structures in C (Horowitz 저) 배열, 트리, 그래프의 수학적 표현과 메모리 구조 이론 Silicon Press
DB 인덱스 심화 Database Internals (Alex Petrov 저) B-Tree, B+Tree, LSM-Tree의 디스크 스토리지 아키텍처 O’Reilly
Java 표준 구현체 OpenJDK HashMap & ConcurrentHashMap Implementation 버킷 충돌 해결, 트리화 임계치(Treeify Threshold 8) 소스 분석 OpenJDK Source
고급 구조 연구 Space/Time Trade-offs in Hash Coding with Allowable Errors Burton H. Bloom (1970), 블룸 필터의 원전 논문 ACM Digital Library

함께 읽으면 좋은 글