기초 자료구조: 배열에서 트라이까지

자료구조는 데이터를 메모리에 어떻게 배치하고 연결하느냐의 문제다. 배열처럼 연속된 공간을 쓰면 접근은 빠르지만 크기를 바꾸기 어렵고, 포인터로 흩어진 공간을 이으면 크기는 자유롭지만 접근이 느려진다. 예제는 C와 Kotlin으로 든다.

추상 자료형 (ADT)

스택을 쓸 때는 push와 pop만 알면 된다. 안이 배열인지 연결 리스트인지는 몰라도 된다. 이렇게 자료와 연산의 동작만 약속하고 구현은 감춘 정의를 추상 자료형(ADT, Abstract Data Type)이라고 한다. 리스트·스택·큐·트리를 배울 때 늘 「ADT 정의 → 구현」 순서를 밟는 이유다.

자료형 = 값의 집합 + 연산의 집합

정수형도 값 {…, -1, 0, 1, …}과 연산 {+, -, ×, /, mod}이 함께 묶여야 쓸 수 있는 자료형이 된다. ADT는 이 생각을 사용자가 정의하는 자료로 넓힌 것이다. 예를 들어 리스트 ADT는 「순서 있는 항목들」이라는 값과 다음 연산으로만 정의된다.

표 어디에도 배열이나 포인터가 나오지 않는다는 점이 핵심이다. ADT는 추상화 가운데 데이터 추상화(값이 메모리에 놓이는 방식을 숨김)와 절차 추상화(sort(a)처럼 계산 단계를 숨김)를 합친 것이다. 반복문이 점프 명령으로 바뀌는 과정을 숨기는 제어 추상화는 여기에 들지 않는다.

ADT와 자료구조

우선순위 큐는 정렬된 배열로도 힙으로도, 맵은 해시 테이블로도 균형 이진 탐색 트리로도 만든다. 같은 ADT라도 구현에 따라 연산의 복잡도가 달라지므로 자주 쓰는 연산을 보고 구현을 고른다. 아래 절들은 대부분 이 「어떻게」에 해당한다.

인터페이스와 구현의 분리

ADT를 코드로 옮기면 사용자가 보는 인터페이스(연산 이름·인자·반환값·동작)와 약속을 지키는 구현(내부 표현과 알고리즘)으로 나뉜다. 사용자 코드가 인터페이스에만 기대면 구현을 배열에서 연결 리스트로 바꿔도 사용자 코드는 그대로다. 성능 문제가 생겼을 때 구현만 갈아 끼울 수 있다는 것이 ADT의 실질적인 이득이다.

C에는 클래스가 없으니 파일로 나눈다. 헤더(.h)에 타입과 함수 원형을, 소스(.c)에 본문을 둔다.

/* list.h: 인터페이스 */
typedef struct List List;          /* 멤버를 공개하지 않은 불완전 타입 */
List *list_create(void);
int   list_length(const List *l);
void  list_insert(List *l, int pos, int item);
 
/* list.c: 구현. 사용자는 이 파일을 보지 않는다 */
struct List { int count; int items[100]; };
int list_length(const List *l) { return l->count; }

헤더에 구조체 멤버를 드러내지 않으면 사용자는 l->count를 직접 건드릴 수 없고 함수로만 다룬다. 대신 크기를 모르니 사용자가 List를 직접 선언할 수 없어 생성·해제 함수를 따로 줘야 한다. 구조체 정의를 헤더에 그대로 두는 방식도 흔한데, 이때 은닉은 「멤버를 직접 만지지 않는다」는 약속에 기댄다. 헤더 분리와 링크는 C의 스코프와 링키지에 있다.

C++·Java는 클래스가 자료와 연산을 한 단위로 묶고 public·private 접근 제어자로 경계를 언어 차원에서 강제한다. Java의 List 인터페이스와 ArrayList·LinkedList의 관계가 ADT와 구현의 관계 그대로다(아래 「언어 라이브러리 속 자료구조」).

배열 (Array)

• 고정된 크기의 메모리 덩어리다. 원소들이 이웃한 공간(contiguous memory) 에 할당된다.
• 배열의 시작 주소(base address)는 첫 번째 원소가 있는 주소다. 인덱스는 시작 주소에서 몇 칸 떨어졌는지를 뜻하는 오프셋이라 i번 원소의 주소는 시작 주소 + i × 원소 크기로 바로 계산된다. 그래서 임의 접근(random access) 이 O(1)이고, 첫 원소의 오프셋이 0이므로 대부분의 언어가 인덱스를 0부터 센다(인덱스 5는 여섯 번째 원소다).
• 정렬되어 있다면 이진 탐색으로 O(log n)에 찾을 수 있다.
• C에서 int arr[10];처럼 선언한 배열은 한 번 만들면 크기를 바꿀 수 없다. 크기를 키우려면 malloc·realloc으로 힙에 공간을 잡아야 한다.

크기를 늘리면 무슨 일이 생기나

연속된 공간 바로 뒤가 다른 데이터로 차 있을 수 있으므로, 원소 하나를 추가하려 해도

1. 더 큰 메모리 공간을 새로 할당하고
2. 기존 원소를 모두 복사한 뒤 새 원소를 넣어야 한다.

원소 n개를 읽고 쓰는 작업이 필요하므로 O(n) 이다.

int *list = malloc(3 * sizeof(int));
// ... list[0] ~ list[2] 사용
 
int *tmp = realloc(list, 4 * sizeof(int)); // 더 큰 공간을 잡고 기존 값을 옮겨 줌
if (tmp == NULL)
{
    free(list);
    return 1;
}
list = tmp;
list[3] = 4;
free(list);

realloc이 복사를 대신해 줄 뿐, 뒤 공간이 비어 있지 않으면 새 공간을 잡고 원소를 모두 옮기는 비용은 그대로다.

배열 문제의 기본 요령

배열은 거의 모든 알고리즘 문제의 입력 형태다. 문자열도 문자 배열이라 같은 요령이 통한다.

중복 값이 있는지, 중복이 답을 바꾸는지는 먼저 확인할 조건이다.

다차원 배열과 구조체

배열을 바탕으로 두 가지 복합 구조를 만든다.

행렬 다루기

2차원 배열(행렬) 문제는 대개 칸을 정점으로 보는 그래프 탐색(BFS·DFS)이거나 동적 계획법이다. 그 밖에 자주 쓰는 조작은 다음과 같다.

빈 행렬은 행이 0개인 경우와 행은 있지만 첫 행의 길이가 0인 경우를 모두 걸러야 matrix[0]에서 오류가 나지 않는다.

배열과 구조체 배열은 크기가 고정이고 중간에 끼워 넣기 어렵다. 구조체 안에 다른 구조체를 가리키는 포인터를 넣으면 이 제약을 벗어난다. 포인터가 하나면 연결 리스트, 둘 이상이면 트리, 아무 노드나 가리키면 그래프가 된다.

연결 리스트 (Linked List)

원소를 연속된 곳에 두지 않고 아무 빈 공간에 할당한 뒤, 다음 원소의 주소를 가리키게 연결한다. 각 노드는 값과 다음 노드를 가리키는 포인터를 가진다. C에서는 구조체와 포인터로 노드를 만든다.

typedef struct node
{
    int number;
    struct node *next;
} node;

Kotlin에서는 객체 참조가 C의 포인터 역할을 한다.

class Node(val value: String, var next: Node? = null)
 
// prev 다음에 새 노드 끼워 넣기: 포인터 두 개만 바꾸면 된다
fun addAfter(prev: Node, value: String) {
    prev.next = Node(value, prev.next)
}

마지막 노드의 next는 NULL(Kotlin은 null)로 끝을 표시한다. 마지막 노드가 다시 첫 노드를 가리키면 원형 연결 리스트(circular linked list) 다. 노드가 다음(next)과 이전(prev) 노드를 모두 가리키면 이중 연결 리스트(doubly linked list) 로, 노드 하나만 쥐고도 그 노드를 지울 수 있고 양방향으로 순회한다. 노드들은 만들어진 시점에 따라 메모리 여기저기에 흩어져 있고, 순서는 오직 포인터가 정한다. 그래서 순서 바꾸기·자르기·나누기·뒤집기도 포인터만 고치면 된다.

배열과 연결 리스트, 언제 무엇을

임의 접근이 많고 끝에서만 넣고 빼면 배열, 위치를 이미 쥔 상태에서 중간 삽입·삭제가 잦으면 연결 리스트를 쓴다. 실제로는 캐시 효율 때문에 이론상 연결 리스트가 유리한 경우에도 배열이 더 빠른 일이 많아서 기본 선택은 동적 배열이다. 크기 상한이 정해진 양쪽 끝 삽입·삭제는 배열 기반 원형 버퍼로 해결할 수 있다.

연결 리스트 문제를 푸는 기법

Java(LinkedList)와 C++(std::list)는 표준 라이브러리에 연결 리스트가 있지만, Python과 JavaScript에는 없어 노드 클래스를 직접 만든다. 문제는 대개 추가 공간 없이 제자리에서 포인터를 고치라고 요구한다. 새 리스트를 만들어 결과를 담으면 쉽지만 공간이 O(n) 든다.

def reverse(head):
    prev = None
    cur = head
    while cur:
        cur.next, prev, cur = prev, cur, cur.next   # 링크를 뒤로 돌리고 한 칸 전진
    return prev

자주 조합되는 부품은 노드 수 세기, 제자리 뒤집기, 가운데 노드 찾기, 정렬된 두 리스트 병합 네 가지다. 빈 리스트, 노드 1개·2개, 사이클이 있을 수 있는지를 먼저 확인한다.

스킵 리스트 (Skip List)

정렬된 연결 리스트는 위치를 찾느라 탐색이 O(n)이다. 스킵 리스트는 그 위에 일부 노드만 이은 「급행」 리스트를 여러 층 쌓아 멀리 건너뛰며 찾는다. 균형 트리처럼 정렬 순서를 유지하면서 탐색·삽입·삭제가 기대 O(log n) 이다.

레벨 3: head ─────────────────────────────▶ 50 ──────────────▶ NIL
레벨 2: head ──────────▶ 20 ──────────────▶ 50 ──────────────▶ NIL
레벨 1: head ──▶ 10 ──▶ 20 ──────▶ 35 ──▶ 50 ──────▶ 70 ──▶ NIL
레벨 0: head ──▶ 10 ──▶ 20 ──▶ 30 ──▶ 35 ──▶ 50 ──▶ 60 ──▶ 70 ──▶ NIL   (모든 원소)

위 그림에서 35를 찾으면 레벨 3에서 head의 다음이 50이라 크므로 내려가고, 레벨 2에서 20으로 간 뒤 다음이 50이라 내려가고, 레벨 1에서 20의 다음이 35라 찾는다. 10과 30은 보지도 않는다.

• 노드가 레벨 i 이상에 있을 확률은 pⁱ이라, 레벨 i에는 기대 n·pⁱ개가 남는다. 층 수는 기대 log_(1/p) n이고, 각 층에서 오른쪽으로 가는 걸음은 기대 1/p번이라 탐색이 기대 O(log n)이다. 높이를 운에 맡기므로 최악은 O(n) 이지만 그럴 확률은 n이 커질수록 무시할 만큼 작다.
• 포인터 수는 기대 n/(1-p)개다. p = 1/2면 노드당 평균 2개, p = 1/4면 약 1.33개다.
• 균형 트리와 달리 회전 같은 재배치가 없다. 삽입·삭제가 주변 링크 몇 개만 바꾸므로 구현이 짧고, 잠금 없이(CAS) 동시에 고치기 쉽다. Java ConcurrentSkipListMap이 이 성질을 쓴다.
• 레벨 0이 정렬된 연결 리스트라 범위 조회는 시작점을 찾은 뒤 옆으로 훑으면 된다.

Redis 정렬 집합(sorted set)은 p = 1/4, 최대 32레벨인 스킵 리스트에 각 노드의 순위(rank)를 위한 구간 길이를 더해 ZRANGE·ZRANK를 O(log n)에 처리한다. 원소 → 점수 조회는 함께 두는 해시 테이블이 맡는다. LevelDB·RocksDB의 멤테이블도 스킵 리스트다(DB 내부 구조).

트리와 이진 탐색 트리

연결 리스트를 응용해 계층 구조를 만든 것이 트리다. 이진 탐색 트리(BST) 는 왼쪽에 더 작은 값, 오른쪽에 더 큰 값을 두어 탐색이 평균 O(log n)이지만, 정렬된 순서로 넣으면 한쪽으로 치우친 편향 트리가 되어 O(n)으로 떨어진다. 그래서 AVL·레드-블랙 트리처럼 높이를 제한하는 균형 트리를 쓴다. 용어, 순회, 회전은 트리와 이진 탐색 트리에 정리했다.

해시 테이블 (Hash Table)

배열과 연결 리스트를 조합한 구조다.

1. 키를 해시 함수에 넣으면 정수(해시값)가 나온다.
2. 이 값을 정해진 크기의 배열(버킷, bucket)의 인덱스로 써서 바로 그 칸을 찾는다.

그래서 평균 탐색 시간이 O(1) 이다. 키-값 쌍을 키로 조회하는 딕셔너리(Python dict, Java·Kotlin Map)가 대개 해시 테이블로 구현된다.

해시 충돌 (Collision)

서로 다른 키가 같은 해시값을 가지면 충돌이 생긴다. 같은 칸에 들어온 값들을 연결 리스트로 이어 붙여(체이닝) 해결한다.

• 특정 칸에만 데이터가 몰리면 그 리스트를 순회해야 하므로 최악의 경우 O(n) 이 된다.
• 충돌을 줄이려면 값을 고르게 분산하는 좋은 해시 함수를 쓰거나 버킷 수를 늘린다.

개방 주소법과의 비교, 적재율과 리사이즈, Java HashMap·Python dict의 실제 구현은 해시 테이블에 정리했다.

트라이 (Trie)

문자열 검색에 특화된 트리다. 알파벳이라면 각 노드가 a~z 26칸짜리 배열을 갖고, 각 칸이 다음 글자의 노드를 가리킨다.

• "Harry"를 찾으려면 H → a → r → r → y 다섯 단계면 된다.
• 탐색 시간은 저장된 단어 수가 아니라 찾는 단어의 길이 k에 비례한다(O(k)). 단어 길이에는 현실적인 상한이 있으므로 사실상 O(1) 로 볼 수 있다.
• 대신 노드마다 26칸 배열을 두므로 메모리를 많이 쓴다. 시간과 공간의 트레이드오프다.
• 삽입은 글자마다 자식이 없으면 만들며 내려가고, 단어가 끝나는 노드에 끝 표시를 단다. 그래야 ab와 abc처럼 접두사 관계인 단어를 구분한다.
• 접두사까지 내려간 뒤 그 아래 서브트리를 훑으면 그 접두사로 시작하는 단어를 모두 얻는다. 검색창 자동 완성이 이 원리다.
• 삽입·탐색·삭제가 모두 단어 길이 m에 비례하는 O(m)이다. 삭제는 끝 표시를 지운 뒤, 자식도 끝 표시도 없어진 노드를 아래에서 위로 거슬러 지운다.
• 단어 목록을 한 번 트라이로 만들어 두면, 단어 하나를 찾을 때 목록 n개를 모두 비교하는 대신 O(m)이면 된다. 같은 사전으로 질의를 반복하는 문제에서 쓴다.
• 빈 문자열을 넣으면 루트에 끝 표시가 붙는다. 빈 트라이에서의 탐색과 함께 경계 사례로 확인한다.

스택과 큐

둘 다 연결 리스트 위에 얹을 수 있다. 큐는 머리 노드를 가리키는 포인터를 다음 노드로 옮겨 꺼내고(dequeue), 꼬리에 노드를 이어 넣는다(enqueue). 꼬리 포인터를 따로 두지 않으면 넣을 때마다 끝까지 따라가야 해 O(n)이 된다. 스택은 머리 한쪽에서만 넣고(push) 꺼낸다(pop). LIFO의 스택과 FIFO의 큐는 스택, 큐와 덱에 따로 정리했다.

얕은 복사와 깊은 복사

C에서 char *t = s;가 문자열이 아니라 주소만 복사하는 것과 같은 문제가 객체에서도 생긴다.

Kotlin data class의 copy()나 super.clone()처럼 언어가 주는 복사는 대개 얕은 복사다. 리스트 같은 참조 타입 필드는 직접 새로 복사해야 깊은 복사가 된다.

언어 라이브러리 속 자료구조: Java 컬렉션

실무에서는 자료구조를 직접 짜기보다 언어가 주는 구현을 고른다. Java 컬렉션 프레임워크(JCF)는 인터페이스로 연산을 정하고(ADT) 구현 클래스로 내부 자료구조를 정하는 구조라 이 관계가 잘 보인다.

flowchart TB
  it["Iterable<br/>for-each로 순회할 수 있다"] --> col["Collection<br/>추가·삭제·포함 여부 같은 기본 연산"]
  col --> list["List<br/>순서 있음, 중복 허용"]
  list --> al["ArrayList<br/>동적 배열"]
  list --> ll["LinkedList<br/>이중 연결 리스트 (Deque도 구현)"]
  col --> set["Set<br/>중복 없음"]
  set --> hs["HashSet<br/>해시 테이블"]
  set --> lhs["LinkedHashSet<br/>해시 테이블 + 삽입 순서"]
  set --> ts["TreeSet<br/>레드-블랙 트리, 정렬 유지 (SortedSet)"]
  col --> q["Queue<br/>한쪽에서 넣고 꺼냄"]
  q --> pq["PriorityQueue<br/>힙"]
  q --> dq["Deque"]
  dq --> ad["ArrayDeque<br/>원형 배열, 스택·큐 모두 대용"]

Map (Collection과 별개 계층):

flowchart TB
  map["Map<br/>키-값"] --> hm["HashMap<br/>해시 테이블"]
  map --> lhm["LinkedHashMap<br/>해시 테이블 + 순서 (LRU 캐시 구현에 쓰인다)"]
  map --> tm["TreeMap<br/>레드-블랙 트리, 키 정렬"]

• 고르는 기준은 이 노트의 복잡도 표와 같다. 인덱스 접근이 많으면 ArrayList, 정렬된 순회가 필요하면 TreeMap·TreeSet, 순서가 상관없으면 HashMap·HashSet이다.
• Stack·Vector·Hashtable은 초기 버전의 동기화된 클래스라 지금은 ArrayDeque, ArrayList, HashMap(동시성이 필요하면 ConcurrentHashMap)을 쓴다.
• Java 21부터는 처음·끝 원소 접근을 통일한 SequencedCollection·SequencedMap 인터페이스가 계층에 들어갔다.
• 변수 타입은 인터페이스(List<String> list = new ArrayList<>())로 선언해 구현을 바꾸기 쉽게 한다.

자료구조가 실제 소프트웨어의 어디에 쓰이는지는 현실 시스템을 움직이는 알고리즘과 자료구조에 있다.

핵심 정리

복잡도 표기 자체는 빅오 표기법과 시간 복잡도에 정리했다.

더 읽을거리

• VisuAlgo: 정렬, 연결 리스트, 힙, BST, 그래프 탐색, 최단 경로, 네트워크 플로까지 자료구조·알고리즘의 동작을 애니메이션으로 단계별로 보여 준다.
• Dictionary of Algorithms and Data Structures: 미국 NIST가 운영하는 알고리즘·자료구조·대표 문제 용어 사전. 용어의 정확한 정의를 찾을 때 쓴다.