핵심 개념

자료구조는 데이터를 메모리에 배치하는 방식과, 그 배치에서 싸게 할 수 있는 연산을 함께 묶은 것입니다. 자료구조를 고르는 일은 언제나 맞바꿈입니다. 위치로 찾는 일이 즉시 끝나는 배치는 가운데 삽입이 느릴 수 있고, 삽입이 싼 배치는 찾기가 느릴 수 있습니다. 이 안내서는 거의 모든 프로그램에서 만나는 다섯 가지 구조, 즉 배열과 동적 배열, 연결 리스트, 스택, 큐와 덱, 해시 테이블을 다룹니다.

추상 자료형과 구현

구조가 약속하는 것과 그 약속을 지키는 방법을 나눠 생각하면 이해가 쉬워집니다.

• 추상 자료형(ADT) 은 연산과 그 의미를 정합니다. 스택은 push, pop, peek 를 제공하고, 마지막에 넣은 것이 먼저 나온다고 약속합니다.
• 구현 은 구체적인 메모리 배치입니다. 같은 스택을 동적 배열 위에 만들 수도 있고 연결 리스트 위에 만들 수도 있습니다.

면접 질문이나 라이브러리 문서는 이 둘을 섞어 말하는 경우가 많습니다. "어떤 클래스를 쓸까?"보다 "어떤 연산이 얼마나 자주 필요한가?"를 먼저 묻는 습관을 들이면 좋습니다.

연속 메모리와 연결 메모리

여기서 다루는 구조는 모두 두 가지 생각 중 하나에서 출발합니다.

요즘 CPU는 메모리를 캐시 라인 단위로 읽기 때문에, 빅오가 같더라도 연속 배열을 훑는 쪽이 연결 리스트를 훑는 쪽보다 몇 배 빠른 경우가 흔합니다.

다섯 가지 구조

• 배열 / 동적 배열: 연속된 메모리 블록입니다. 동적 배열(Python list, C++ std::vector, Java ArrayList, JavaScript 배열)은 여유 용량을 두었다가 가득 차면 더 큰 블록을 잡아 복사하므로, 끝에 추가하는 비용이 분할 상환 O(1)입니다.
• 연결 리스트: 값과 다음 노드에 대한 참조를 가진 노드의 사슬입니다(단일 연결). 양쪽 이웃을 모두 가리키면 이중 연결 리스트입니다.
• 스택: 나중에 들어간 것이 먼저 나옵니다(LIFO). 쌓아 둔 접시나 실행 중인 프로그램의 호출 스택을 떠올리면 됩니다.
• 큐 / 덱: 큐는 먼저 들어간 것이 먼저 나옵니다(FIFO). 매표소 줄과 같습니다. 덱(양방향 큐)은 양쪽 끝에서 넣고 뺄 수 있습니다.
• 해시 테이블: 키를 값에 대응시킵니다. 해시 함수가 키를 버킷 번호로 바꾸므로 찾기가 평균 O(1)입니다.

표준 라이브러리에 이미 있습니다

실무 코드에서 이 구조를 직접 짜는 일은 드물지만, 어떤 내장 타입이 어떤 생각에 해당하는지는 알아야 합니다.

리스트를 스택으로 쓸 때는 끝에서만 넣고 뺍니다.

stack = []
stack.append("a")      # push
stack.append("b")
print(stack[-1])       # peek -> b
print(stack.pop())     # pop  -> b
print(stack)           # ['a']

큐가 필요하면 list.pop(0) 대신 deque 를 씁니다. pop(0) 은 남은 원소를 전부 한 칸씩 당기기 때문입니다.

from collections import deque

queue = deque()
queue.append("job-1")      # 오른쪽 끝에 넣기(enqueue)
queue.append("job-2")
print(queue.popleft())     # 왼쪽 끝에서 꺼내기(dequeue) -> job-1
queue.appendleft("urgent") # 덱은 앞쪽에도 넣을 수 있습니다
print(list(queue))         # ['urgent', 'job-2']

딕셔너리와 집합은 해시 테이블입니다. 키는 해시할 수 있어야 하며, 실제로는 변경 불가능한 값이어야 한다는 뜻입니다.

stock = {"apple": 3, "pear": 0}
stock["kiwi"] = 7                 # 삽입
stock["apple"] += 1               # 갱신
print(stock.get("plum", 0))       # 없는 키는 기본값 -> 0
seen = {"apple", "kiwi"}
print("pear" in seen)             # 평균 O(1) 포함 검사 -> False
# stock[["a", "b"]] = 1 은 TypeError: 리스트는 해시할 수 없습니다

무엇을 고를까

다음 질문을 차례로 던져 봅니다.

1. 위치(인덱스)로 접근해야 하는가? 동적 배열을 씁니다.
2. 한쪽 끝에서만 넣고 빼는가? 스택을 씁니다(동적 배열이면 충분합니다).
3. 한쪽에서 넣고 반대쪽에서 빼는가? 큐나 덱을 씁니다. 0번 위치에서 빼는 일반 배열은 피합니다.
4. 키로 찾거나 포함 여부를 검사하는가? 해시 맵이나 해시 집합을 씁니다.
5. 노드를 쥔 채 가운데에서 자주 끼우고 빼는가? 연결 리스트를 고려하되, 먼저 측정합니다. 배열이 이기는 경우가 많습니다.

용어

정리

자료구조는 접근 방식 사이의 맞바꿈입니다. 연속 배열은 빠른 인덱싱과 좋은 캐시 효율을, 연결 노드는 국소적인 끼워 넣기를, 스택과 큐는 끝에서만 다루는 단순함을, 해시 테이블은 키로 찾는 평균 O(1)을 줍니다. 필요한 연산에서 출발해, 그 연산을 싸게 만들어 주는 내장 타입을 고르면 됩니다.