25분 만에 끝내는 핵심 자료구조 15가지 대백과: 배열부터 트리·그래프·해시테이블까지 완벽 시각화

프로그래밍의 뼈대를 이루는 15가지 핵심 자료구조 완벽 정리! RAM 메모리와 CPU 캐시 지역성의 원리, 배열 vs 연결 리스트, 스택/큐, 해시 테이블 충돌 해결, 이진 탐색 트리와 DB 인덱스를 지배하는 B+Tree의 구조를 한눈에 파악할 수 있도록 시각화 해설합니다.
IT·과학
저자

Ikmyungterran

공개

2026년 9월 8일

Modified

2026년 9월 8일

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

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

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

graph TD
    RAM["컴퓨터 주기억장치 (RAM): 번호가 붙은 거대한 사물함"] --> Continuous["연속 메모리 할당: 배열 Array"]
    RAM --> Discontinuous["불연속 포인터 연결: 연결 리스트 Linked List"]
    Continuous --> CacheWin["CPU 캐시 지역성 대폭 향상!"]
    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. 선형 자료구조의 영원한 라이벌: 배열 vs 연결 리스트

비교 항목 배열 (Array) 연결 리스트 (Linked List)
메모리 배치 빈틈없이 연속된 물리 메모리 공간에 나란히 배치 메모리 여기저기 흩어져 있고 주소(Pointer)로 서로를 가리킴
인덱스 임의 접근 (Lookup) \(O(1)\) 초고속 (시작 주소 + 인덱스 * 크기) \(O(N)\) 느림 (헤드부터 노드를 하나씩 타고 넘어가야 함)
중간 삽입 / 삭제 \(O(N)\) 느림 (뒤의 모든 데이터를 한 칸씩 밀거나 당겨야 함) \(O(1)\) 즉각 완료 (앞뒤 포인터 연결선만 뚝 떼어 붙이면 끝)
CPU 캐시 적중률 압도적으로 높음 (공간 지역성 Spatial Locality) 낮음 (메모리가 흩어져 있어 매번 캐시 미스 발생)
힌트🚀 왜 현대 개발에서는 연결 리스트보다 배열을 훨씬 많이 쓸까?

이론상 연결 리스트가 삽입/삭제 \(O(1)\)로 좋아 보이지만, 현대 CPU는 메모리를 읽을 때 요청된 바이트만 가져오는 것이 아니라 주변 64바이트 덩어리(Cache Line)를 통째로 L1/L2 캐시로 퍼옵니다. 배열은 연속되어 있어 다음 데이터가 이미 CPU 캐시에 들어있지만, 연결 리스트는 메모리 곳곳을 포인터로 점프해야 하므로 CPU가 멍때리는 캐시 미스(Cache Miss)가 발생합니다.

2. 출입구가 통제된 데이터 통로: 스택(Stack)과 큐(Queue)

graph LR
    subgraph StackBox["스택 (Stack: LIFO)"]
        S_In["PUSH"] --> S1["[ 3 ] 최상단 (Top)"]
        S1 --> S2["[ 2 ]"]
        S2 --> S3["[ 1 ] 바닥"]
        S1 --> S_Out["POP"]
    end
    subgraph QueueBox["큐 (Queue: FIFO)"]
        Q_In["ENQUEUE (Rear)"] --> Q3["[ 3 ]"]
        Q3 --> Q2["[ 2 ]"]
        Q2 --> Q1["[ 1 ]"]
        Q1 --> Q_Out["DEQUEUE (Front)"]
    end
    style StackBox fill:#FEF3C7,stroke:#D97706,stroke-width:2px;
    style QueueBox fill:#E0F2FE,stroke:#0284C7,stroke-width:2px;

  • 스택 (Stack - LIFO 후입선출): 프링글스 감자칩 통. 가장 마지막에 넣은 것이 가장 먼저 나옵니다.
    • 실무 활용: 브라우저 ‘뒤로 가기’, 텍스트 에디터의 ‘실행 취소(Ctrl+Z)’, 프로그래밍 언어의 함수 호출 스택(Call Stack).
  • 큐 (Queue - FIFO 선입선출): 은행 창구 줄서기. 먼저 온 사람이 먼저 서비스를 받습니다.
    • 실무 활용: 프린터 인쇄 대기열, 백엔드 비동기 작업 큐(RabbitMQ, Celery), 웹 서버의 접속 대기열.
  • 덱 (Deque - Double-Ended Queue): 양쪽 끝(앞/뒤) 모두에서 넣고 뺄 수 있는 만능 큐.

3. \(O(1)\)의 마법: 해시 테이블 (Hash Table)

전화번호부에서 100만 명 중 ’홍길동’의 번호를 0.0001초 만에 찾는 비결은 무엇일까요?

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

    Key->>HashFn: "apple" 문자열 전달
    HashFn-->>Bucket: 수학 연산을 통해 정수 인덱스 4번 슬롯 계산!
    Bucket-->>Key: 4번 버킷의 값 "$3.50" 즉시 반환 (O(1))

해시 충돌(Hash Collision)을 해결하는 2대 비책:

  1. 체이닝 (Chaining): 충돌이 난 버킷 뒤에 연결 리스트나 Red-Black 트리를 매달아 데이터를 줄줄이 연결합니다. (Java HashMap 표준)
  2. 개방 주소법 (Open Addressing): 충돌이 나면 옆의 빈 슬롯을 찾아 들어갑니다. (선형 탐사 Linear Probing, 이중 해싱)

4. 계층형 데이터의 정점: 트리(Tree)와 B+Tree

단순한 선형 구조로는 수억 건의 계층 데이터를 다룰 수 없습니다.

                  [ 루트 노드 ]
                  /                      [ 서브트리 ]     [ 서브트리 ]
             /      \         /                [단말]    [단말]   [단말]    [단말] (리프 노드)
  1. 이진 탐색 트리 (BST, Binary Search Tree): “왼쪽 자식은 나보다 작고, 오른쪽 자식은 나보다 크다.” 평균 \(O(\log N)\)으로 탐색하지만, 정렬된 데이터가 순서대로 들어오면 한쪽으로 길게 늘어서는 편향 트리(\(O(N)\) 타락)가 됩니다.
  2. 균형 이진 트리 (AVL Tree & Red-Black Tree): 노드가 한쪽으로 기울어지면 스스로 회전(Rotation)하여 높이 균형을 강제로 맞춥니다. 자바의 TreeMap과 C++의 std::map이 Red-Black Tree로 구현되어 있습니다.
  3. B+Tree (데이터베이스 인덱스의 제왕):
    • 디스크 I/O를 최소화하기 위해 자식 노드를 수백 개씩 갖는 다진 트리(Multi-way Tree)입니다.
    • 모든 실제 데이터는 가장 바닥의 리프 노드(Leaf Node)에만 저장되며, 리프 노드들끼리 양방향 연결 리스트(Linked List)로 촘촘히 연결되어 있습니다.
    • 덕분에 WHERE age BETWEEN 20 AND 30과 같은 범위 스캔(Range Scan)을 할 때 트리를 다시 올라갈 필요 없이 리프 노드만 옆으로 횡단하며 초고속으로 데이터를 긁어옵니다.

5. 최댓값·최솟값 즉시 뽑기: 힙(Heap)과 우선순위 큐

새로운 환자가 응급실에 실려 왔을 때, 도착 순서가 아니라 환자의 위급한 상태(우선순위)에 따라 가장 위급한 환자를 \(O(1)\)에 호출해야 합니다.

  • 최대 힙 (Max Heap): 부모 노드의 값이 항상 자식 노드보다 큽니다. 루트 노드에는 항상 전체 데이터의 최댓값이 위치합니다.
  • 최소 힙 (Min Heap): 루트 노드에 항상 최솟값이 위치합니다.
  • 새 데이터 삽입: \(O(\log N)\)
  • 최우선 순위 데이터 추출: \(O(\log N)\)

6. 핵심 자료구조 8대 요약표

자료구조 탐색(Lookup) 삽입(Insert) 삭제(Delete) 핵심 강점 및 추천 실무 상황
배열 (Array) \(O(1)\) \(O(N)\) \(O(N)\) 데이터 개수가 정해져 있고 조회가 압도적으로 많은 경우
연결 리스트 \(O(N)\) \(O(1)\) \(O(1)\) 중간 삽입/삭제가 빈번하고 전체 크기를 가늠하기 힘든 경우
스택 (Stack) \(O(N)\) \(O(1)\) \(O(1)\) 최근 작업 되돌리기, 괄호 짝 맞추기, 깊이 우선 탐색(DFS)
큐 (Queue) \(O(N)\) \(O(1)\) \(O(1)\) 요청 버퍼링, 이벤트 큐, 너비 우선 탐색(BFS)
해시 테이블 \(O(1)\) \(O(1)\) \(O(1)\) 고유 키(Key)로 데이터를 즉각 조회해야 하는 모든 캐시 및 맵
Red-Black Tree \(O(\log N)\) \(O(\log N)\) \(O(\log N)\) 정렬 상태를 유지하면서 삽입/삭제가 지속적으로 발생하는 경우
B+Tree \(O(\log N)\) \(O(\log N)\) \(O(\log N)\) 대용량 디스크 기반 인덱스 및 범위 검색(Range Scan)
힙 (Heap) 최댓값: \(O(1)\) \(O(\log N)\) \(O(\log N)\) 우선순위 큐, 실시간 스케줄러, 다익스트라 최단 경로 알고리즘

📚 참고 문헌 및 공식 출처

구분 자료명 주요 내용 링크
자료구조 바이블 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

함께 읽으면 좋은 글