배열, 연결 리스트, 스택, 큐

리스트의 append는 O(1)인데 맨 앞에 넣기는 왜 O(n)일까요? 데이터를 메모리에 늘어놓는 두 방식인 배열과 연결 리스트를 직접 만들어 옮긴 칸과 따라간 횟수를 세고, 원소 하나에 드는 메모리를 리스트, array, 연결 리스트로 비교해요. 그 위에 규칙을 더한 스택으로 괄호 짝 맞추기와 되돌리기를 만들고, 큐를 리스트 대신 deque로 만들어야 하는 이유를 시간으로 확인해요. 최근 몇 개만 기억하는 maxlen, 호출 스택, 작업 대기열, 상황에 맞는 구조 고르는 법까지 다뤄요.

중급강의 2 / 6약 16분

지난 강의의 표에서 리스트의 append와 pop()은 O(1)인데, insert(0, x)와 pop(0)은 O(n)이었어요. 같은 리스트인데 왜 앞과 뒤가 다를까요? 답은 데이터를 메모리에 늘어놓는 방식에 있어요. 이번 강의에서는 가장 기본이 되는 두 방식인 배열과 연결 리스트를 직접 만들어 보고, 그 위에 규칙을 하나씩 더한 스택과 큐를 써 봐요.

배열: 빈틈없이 이어진 칸

컴퓨터 기초 트랙에서 본 것처럼 메모리는 번호(주소)가 붙은 아주 긴 칸의 줄이에요. 배열은 같은 크기의 칸을 빈틈없이 이어서 잡아요. 그래서 i번째 칸의 주소는 "시작 주소 + i × 칸 크기"로 한 번에 계산돼요. 100만 번째 칸이라도 계산 한 번이라 O(1)이에요.

대신 크기를 미리 정해야 하고, 중간에 끼워 넣으려면 뒤쪽 칸을 모두 한 칸씩 밀어야 해요. 파이썬의 리스트는 칸이 모자라면 더 큰 배열을 새로 잡아 옮기는 동적 배열이에요. 지난 강의의 분할 상환이 바로 이 이야기였어요. 간단한 동적 배열을 직접 만들어서 칸을 몇 번 옮기는지 세어 볼게요. 이해하기 쉽게 칸이 모자랄 때마다 두 배로 늘려요.

class DynamicArray:
    def __init__(self):
        self.capacity, self.size, self.moves = 1, 0, 0
        self.slots = [None]                             # 이어진 빈칸 묶음이라고 생각해요

    def _grow(self):                                    # 빈칸이 모자라면 두 배 크기로 옮겨요
        self.capacity *= 2
        new = [None] * self.capacity
        for i in range(self.size):
            new[i] = self.slots[i]
            self.moves += 1
        self.slots = new

    def append(self, value):
        if self.size == self.capacity:
            self._grow()
        self.slots[self.size] = value
        self.size += 1

    def insert_front(self, value):
        if self.size == self.capacity:
            self._grow()
        for i in range(self.size, 0, -1):               # 한 칸씩 뒤로 밀어 맨 앞을 비워요
            self.slots[i] = self.slots[i - 1]
            self.moves += 1
        self.slots[0] = value
        self.size += 1

    def get(self, i):                                   # 시작 위치에서 i칸, 계산 한 번이면 돼요
        return self.slots[i]

for n in (1_000, 2_000, 4_000):
    back, front = DynamicArray(), DynamicArray()
    for v in range(n):
        back.append(v)
        front.insert_front(v)
    print(f"n={n:>5,}  뒤에 넣기: 옮긴 칸 {back.moves:>5,}  앞에 넣기: 옮긴 칸 {front.moves:>9,}")
n=1,000  뒤에 넣기: 옮긴 칸 1,023  앞에 넣기: 옮긴 칸   500,523
n=2,000  뒤에 넣기: 옮긴 칸 2,047  앞에 넣기: 옮긴 칸 2,001,047
n=4,000  뒤에 넣기: 옮긴 칸 4,095  앞에 넣기: 옮긴 칸 8,002,095

뒤에 넣기는 n개를 넣는 동안 옮긴 칸이 n 남짓이라 하나당 O(1)이에요. 앞에 넣기는 넣을 때마다 이미 있는 원소를 모두 한 칸씩 밀어야 해서, n이 두 배가 되면 4배로 늘어요. 하나당 O(n), 전체로는 O(n²)이에요. pop(0)이 O(n)인 것도 같은 이유예요. 맨 앞을 꺼내면 생긴 빈칸을 메우려고 나머지를 한 칸씩 당겨야 하거든요.

연결 리스트: 다음을 가리키는 노드

연결 리스트는 칸을 이어 붙이지 않아요. 값마다 노드를 따로 만들고, 노드가 "다음 노드는 저기 있다"는 주소를 함께 들고 있어요. 보물찾기 쪽지처럼 첫 쪽지만 알면 나머지는 따라가며 찾아요.

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value, self.next = value, next

class LinkedList:
    def __init__(self):
        self.head, self.size = None, 0

    def push_front(self, value):                        # 새 노드가 지금의 맨 앞을 가리키면 끝
        self.head = Node(value, self.head)
        self.size += 1

    def get(self, i):                                   # i번째까지 하나씩 따라가야 해요
        node, steps = self.head, 0
        for _ in range(i):
            node, steps = node.next, steps + 1
        return node.value, steps

    def __iter__(self):
        node = self.head
        while node:
            yield node.value
            node = node.next

songs = LinkedList()
for title in ["봄비", "여름밤", "가을 편지", "겨울 숲"]:
    songs.push_front(title)
print("앞에서부터:", " → ".join(songs))
print("2번째 곡과 따라간 횟수:", songs.get(2))

big = LinkedList()
for v in range(100_000):
    big.push_front(v)
print("10만 개 중 9만 번째 값과 따라간 횟수:", big.get(90_000))
앞에서부터: 겨울 숲 → 가을 편지 → 여름밤 → 봄비
2번째 곡과 따라간 횟수: ('여름밤', 2)
10만 개 중 9만 번째 값과 따라간 횟수: (9999, 90000)
  • 맨 앞에 넣기는 O(1)이에요. 새 노드가 지금의 맨 앞을 가리키게 하고, 맨 앞 표시만 새 노드로 바꾸면 끝이에요. 아무것도 밀지 않아요. 그래서 넣은 순서와 거꾸로 늘어섰어요.
  • i번째 찾기는 O(i)예요. 주소를 계산할 방법이 없어서 처음부터 하나씩 따라가야 해요. 9만 번째 값을 찾는 데 9만 번 따라갔어요.
  • 노드가 앞뒤를 모두 가리키는 이중 연결 리스트는 맨 뒤에서 넣고 빼기도 O(1)이고, 지울 노드를 이미 손에 쥐고 있다면 중간에서 빼기도 O(1)이에요. 그 노드를 찾는 데는 여전히 O(n)이 들지만요.

연결 리스트는 메모리도 더 써요. 정수 100만 개를 담을 때 얼마나 쓰는지 볼게요.

import tracemalloc
from array import array

def kept_mb(build):
    tracemalloc.start()
    kept = build()
    used = tracemalloc.get_traced_memory()[0]
    tracemalloc.stop()
    return used / 1024**2

def build_linked():
    linked = LinkedList()
    for v in range(1_000_000):
        linked.push_front(v)
    return linked

n = 1_000_000
for label, build in [("리스트", lambda: list(range(n))),
                     ("array('q')", lambda: array("q", range(n))),
                     ("연결 리스트", build_linked)]:
    mb = kept_mb(build)
    print(f"{label}: {mb:.0f}MB (원소 하나에 약 {mb * 1024**2 / n:.0f}바이트)")
리스트: 38MB (원소 하나에 약 40바이트)
array('q'): 8MB (원소 하나에 약 8바이트)
연결 리스트: 76MB (원소 하나에 약 80바이트)

파이썬 리스트의 칸에는 값 자체가 아니라 값이 있는 곳의 주소가 들어 있고, 정수 하나하나가 따로 만든 객체예요. 그래서 원소 하나에 40바이트쯤 들어요. array는 정수를 칸에 바로 8바이트씩 담아서 5분의 1이에요. 선형대수 트랙에서 쓴 넘파이 배열이 가벼운 것도 같은 이유예요. 연결 리스트는 값마다 노드 객체가 하나씩 더 붙어서 리스트의 두 배예요.

속도에서도 배열이 유리할 때가 많아요. 배열은 이웃한 칸을 차례로 읽으니 CPU가 다음 칸을 미리 가져다 두기 쉽지만(캐시), 연결 리스트의 노드는 메모리 여기저기 흩어져 있어서 따라갈 때마다 멀리 다녀와야 해요. 그래서 이론상 연결 리스트가 유리한 작업에서도 실제로는 배열이 이기는 일이 흔해요. 연결 리스트는 혼자 쓰기보다 다른 구조의 부품으로 더 자주 써요. 파이썬의 deque는 칸 묶음(블록)을 양쪽으로 이어 붙인 구조이고, OrderedDict와 functools.lru_cache도 순서를 관리하는 데 이중 연결 리스트를 써요.

스택: 마지막에 넣은 것부터

이제 이 저장 방식 위에 규칙을 하나 더해요. 스택은 넣고 빼는 곳이 한쪽 끝뿐이라 마지막에 넣은 것을 가장 먼저 꺼내요. 영어 머리글자로 LIFO(Last In, First Out)라고 해요. 접시를 쌓아 두고 맨 위부터 집는 모습이에요. 파이썬 리스트의 append와 pop()은 맨 뒤에서만 일어나니, 리스트가 그대로 스택이에요. 둘 다 O(1)이고요.

스택이 어울리는 일은 "가장 최근에 연 것을 가장 먼저 닫는" 일이에요. 괄호 짝 맞추기가 대표적이에요.

PAIRS = {")": "(", "]": "[", "}": "{"}

def check_brackets(text):
    stack = []
    for i, ch in enumerate(text, 1):
        if ch in "([{":
            stack.append((ch, i))                       # 여는 괄호는 쌓아 두고
        elif ch in PAIRS:
            if not stack or stack[-1][0] != PAIRS[ch]:
                return f"{i}번째 글자 '{ch}'의 짝이 없어요"
            stack.pop()                                 # 닫는 괄호는 맨 위의 것과 짝지어 꺼내요
    if stack:
        ch, i = stack[-1]
        return f"{i}번째 글자 '{ch}'를 닫지 않았어요"
    return "짝이 모두 맞아요"

for code in ["print(sum([1, 2, 3]))", "data = {'a': [1, 2}", "if (x > 0:"]:
    print(f"{code:<24}{check_brackets(code)}")
print(sum([1, 2, 3]))   짝이 모두 맞아요
data = {'a': [1, 2}     19번째 글자 '}'의 짝이 없어요
if (x > 0:              4번째 글자 '('를 닫지 않았어요

여는 괄호를 만나면 쌓고, 닫는 괄호를 만나면 맨 위의 것과 짝이 맞는지 보고 꺼내요. 두 번째 줄은 대괄호를 닫기 전에 중괄호를 닫아서 짝이 어긋났고, 세 번째 줄은 끝까지 갔는데 여는 괄호가 남았어요. 코드 편집기가 짝이 안 맞는 괄호에 표시를 해 주는 것도, 파이썬이 코드를 읽으며 괄호를 확인하는 것도 같은 원리예요.

되돌리기와 다시 하기도 스택 두 개로 만들어요.

class Editor:
    def __init__(self):
        self.text, self.undo_stack, self.redo_stack = "", [], []

    def write(self, s):
        self.undo_stack.append(self.text)               # 바꾸기 전 상태를 쌓아 두고
        self.redo_stack.clear()                         # 새로 쓰면 다시 하기 기록은 사라져요
        self.text += s

    def undo(self):
        if self.undo_stack:
            self.redo_stack.append(self.text)
            self.text = self.undo_stack.pop()           # 가장 최근 상태부터 되돌려요

    def redo(self):
        if self.redo_stack:
            self.undo_stack.append(self.text)
            self.text = self.redo_stack.pop()

ed = Editor()
for s in ["안녕", "하세요", "!"]:
    ed.write(s)
ed.undo()
ed.undo()
print("두 번 되돌리기:", ed.text)
ed.redo()
print("한 번 다시 하기:", ed.text)
ed.write("?")
print("새로 쓰고 나면:", ed.text, "| 다시 할 것이 남았나요?", bool(ed.redo_stack))
두 번 되돌리기: 안녕
한 번 다시 하기: 안녕하세요
새로 쓰고 나면: 안녕하세요? | 다시 할 것이 남았나요? False

되돌릴 때마다 가장 최근 상태부터 꺼내고, 꺼낸 것은 다시 하기 스택에 쌓아요. 새로 쓰면 다시 하기 스택을 비워요. 갈라진 뒤의 미래로는 다시 갈 수 없으니까요. 실제 편집기는 글 전체 대신 바뀐 부분만 쌓아서 메모리를 아껴요. 브라우저의 뒤로 가기와 앞으로 가기도 같은 구조예요.

가장 중요한 스택은 눈에 보이지 않아요. 함수가 다른 함수를 부를 때마다 "끝나면 돌아올 곳"을 쌓아 두는 호출 스택이에요. 오류가 났을 때 보는 Traceback이 바로 그 순간의 호출 스택이고요. 재귀와 동적 계획법 강의에서 다시 만나요.

큐: 먼저 넣은 것부터

큐는 먼저 넣은 것을 먼저 꺼내요. FIFO(First In, First Out)라고 해요. 번호표를 뽑고 서는 줄이에요. 뒤에서 넣고 앞에서 꺼내야 하는데, 리스트로 하면 앞에서 꺼낼 때마다 pop(0)이 나머지를 모두 당겨요. 양쪽 끝에서 O(1)로 넣고 빼는 collections.deque(덱, 양쪽 끝이 열린 큐)와 비교해 볼게요.

import time
from collections import deque

def seconds(func, *args):
    start = time.perf_counter()
    func(*args)
    return time.perf_counter() - start

def drain_list(n):
    q = list(range(n))
    while q:
        q.pop(0)                                        # 맨 앞을 꺼내면 나머지가 한 칸씩 앞으로 와요

def drain_deque(n):
    q = deque(range(n))
    while q:
        q.popleft()                                     # 맨 앞 칸에서 꺼내기만 해요

lt = [seconds(drain_list, n) for n in (20_000, 40_000, 80_000)]
dt = [seconds(drain_deque, n) for n in (200_000, 400_000, 800_000)]
print("리스트 큐: n이 2배가 될 때마다 시간이 3배 넘게 늘었나요?", lt[1] / lt[0] > 3 and lt[2] / lt[1] > 3)
print("deque 큐: n이 2배가 될 때마다 시간이 3배 안쪽으로 늘었나요?", dt[1] / dt[0] < 3 and dt[2] / dt[1] < 3)
print("8만 개를 꺼낼 때 deque가 10배 넘게 빠른가요?", lt[2] / seconds(drain_deque, 80_000) > 10)
리스트 큐: n이 2배가 될 때마다 시간이 3배 넘게 늘었나요? True
deque 큐: n이 2배가 될 때마다 시간이 3배 안쪽으로 늘었나요? True
8만 개를 꺼낼 때 deque가 10배 넘게 빠른가요? True

리스트로 만든 큐는 n이 두 배가 되면 시간이 4배 가까이 늘어요. 꺼낼 때마다 O(n)이니 전체가 O(n²)이에요. deque는 맨 앞 블록에서 꺼내기만 하니 하나당 O(1), 전체가 O(n)이에요. 큐가 필요하면 리스트 말고 deque를 써요.

waiting = deque()
for name in ["민지", "준호", "서연"]:
    waiting.append(name)                                # 뒤에 줄을 서요
print("지금 상담:", waiting.popleft(), "| 남은 줄:", list(waiting))
waiting.appendleft("장애 신고")                          # 급한 건은 맨 앞에 끼워 넣을 수도 있어요
print("다음 상담:", waiting.popleft(), "| 남은 줄:", list(waiting))

recent = deque(maxlen=3)                                # 최근 3개만 기억해요
for page in ["홈", "가이드북", "알고리즘 트랙", "복잡도 강의"]:
    recent.append(page)
print("최근 본 페이지:", list(recent))
지금 상담: 민지 | 남은 줄: ['준호', '서연']
다음 상담: 장애 신고 | 남은 줄: ['준호', '서연']
최근 본 페이지: ['가이드북', '알고리즘 트랙', '복잡도 강의']
  • append로 뒤에 줄을 서고 popleft로 앞에서 꺼내면 큐예요.
  • appendleft로 앞에도 넣을 수 있어서 급한 일을 끼워 넣을 수 있어요.
  • maxlen을 주면 가득 찼을 때 반대쪽 끝의 가장 오래된 것이 저절로 밀려나요. "최근 본 상품", "마지막 로그 100줄"처럼 마지막 몇 개만 기억할 때 딱이에요. 크기를 정해 두고 오래된 것부터 밀어내는 이런 구조를 링 버퍼(원형 버퍼)라고도 해요.
  • 대신 deque의 가운데 값을 번호로 읽는 건 O(n)이에요. 번호로 자주 읽어야 하면 리스트가 맞아요.

큐는 곳곳에 있어요. 웹 트랙의 비동기 강의에서 본 자바스크립트의 대기열도 큐예요. 서버는 메일 보내기나 썸네일 만들기처럼 오래 걸리는 일을 작업 큐에 넣어 두고, 따로 도는 일꾼 프로그램이 하나씩 꺼내 처리해요. 여러 스레드가 함께 쓰는 큐는 queue.Queue를 써요(동시성 강의). 먼저 온 순서가 아니라 급한 순서로 꺼내야 하면 우선순위 큐를 쓰는데, 파이썬에서는 heapq로 만들어요. 그 속의 힙 구조는 트리와 그래프 강의에서 다뤄요.

무엇을 고를까

자주 하는 일구조파이썬
번호로 바로 읽기, 맨 뒤에 넣고 빼기동적 배열list
마지막에 넣은 것부터 꺼내기스택list의 append와 pop()
먼저 넣은 것부터 꺼내기, 양쪽 끝에서 넣고 빼기큐, 덱collections.deque
최근 몇 개만 기억하기링 버퍼deque(maxlen=...)
숫자를 많이, 가볍게 담기타입이 정해진 배열array, 넘파이
급한 것부터 꺼내기우선순위 큐heapq (트리와 그래프 강의)
값으로 바로 찾기해시 테이블dict, set (다음 강의)

구조를 고르는 기준은 "무엇을 가장 자주 하느냐"예요. 같은 데이터라도 번호로 읽는 일이 많으면 배열, 앞에서 꺼내는 일이 많으면 덱이 맞아요.

실습

  1. DynamicArray에 맨 앞을 꺼내는 pop_front를 만들고, n개를 모두 앞에서 꺼낼 때 옮긴 칸 수를 세어 보세요.
  2. DynamicArray가 칸이 모자랄 때 두 배 대신 10칸씩만 늘리게 바꾸고, 뒤에 넣기로 옮긴 칸 수가 n에 따라 어떻게 자라는지 보세요.
  3. LinkedList에 맨 뒤 노드를 기억하는 tail을 더해서, 맨 뒤에 넣는 push_back을 O(1)로 만들어 보세요.
  4. check_brackets가 따옴표 안의 괄호는 무시하도록 고쳐 보세요. 예를 들어 print(")")는 짝이 맞아야 해요.
  5. deque(maxlen=5)로 최근 5개 값의 평균(이동 평균)을 구하는 함수를 만들어 보세요.

자주 하는 실수

  • 리스트로 큐를 만든다. pop(0)은 O(n)이에요. deque의 popleft를 써요.
  • 리스트 맨 앞에 계속 끼워 넣는다. insert(0, x)를 반복하면 전체가 O(n²)이에요. 뒤에 넣고 마지막에 한 번 뒤집거나(reverse()), deque의 appendleft를 써요.
  • 연결 리스트가 언제나 빠르다고 믿는다. 끼워 넣기 자체는 O(1)이어도 그 자리를 찾는 데 O(n)이 들고, 메모리도 더 쓰고, 캐시에도 불리해요.
  • 덱의 가운데를 번호로 읽는다. 양 끝은 O(1)이지만 가운데는 O(n)이에요.
  • 빈 스택이나 큐에서 꺼낸다. 빈 리스트의 pop()과 빈 덱의 popleft()는 오류를 내요. 꺼내기 전에 비었는지 확인해요.

점검 문제

  1. 배열에서 i번째 값을 O(1)로 읽을 수 있는 이유는?
  2. 리스트의 append는 O(1)인데 insert(0, x)는 O(n)인 이유는?
  3. 연결 리스트에서 맨 앞에 넣기가 O(1)인 이유와, i번째 값 읽기가 O(n)인 이유는?
  4. 정수 100만 개를 담을 때 리스트, array, 연결 리스트 중 메모리를 가장 적게 쓰는 것과 가장 많이 쓰는 것은? 이유는?
  5. 스택과 큐의 차이를 꺼내는 순서로 설명해 보세요.
  6. 괄호 짝 맞추기에 스택이 어울리는 이유는?
  7. 큐를 리스트로 만들면 안 되는 이유와, 대신 쓸 것은?
  8. 최근 본 페이지 10개만 기억하려면 어떤 구조가 좋을까요?

정답

  1. 같은 크기의 칸이 빈틈없이 이어져 있어서, 시작 주소에 i × 칸 크기를 더하는 계산 한 번으로 주소가 나오기 때문이에요.
  2. 맨 뒤에 넣을 때는 빈칸에 넣기만 하면 되고(가끔 자리를 늘리는 비용은 분할 상환으로 상수), 맨 앞에 넣을 때는 이미 있는 원소를 모두 한 칸씩 밀어야 하기 때문이에요.
  3. 새 노드가 지금의 맨 앞을 가리키게 하고 맨 앞 표시만 바꾸면 되니 O(1)이에요. 하지만 노드가 메모리에 흩어져 있어 주소를 계산할 수 없으니, i번째까지 하나씩 따라가야 해서 O(n)이에요.
  4. 가장 적은 건 array예요. 정수를 칸에 바로 8바이트씩 담아요. 가장 많은 건 연결 리스트예요. 값마다 다음 주소를 담은 노드 객체가 하나씩 더 붙어요.
  5. 스택은 마지막에 넣은 것을 먼저 꺼내고(LIFO), 큐는 먼저 넣은 것을 먼저 꺼내요(FIFO).
  6. 괄호는 가장 최근에 연 것부터 닫아야 하는데, 스택이 바로 가장 최근에 넣은 것을 먼저 꺼내는 구조이기 때문이에요.
  7. 앞에서 꺼낼 때마다 pop(0)이 나머지 원소를 모두 당겨서 하나당 O(n), 전체로는 O(n²)이 되기 때문이에요. 양쪽 끝에서 O(1)인 collections.deque를 써요.
  8. deque(maxlen=10)이에요. 새 페이지를 넣으면 가장 오래된 것이 저절로 밀려나요.

다음 강의

배열은 번호를 알면 O(1)로 읽지만, "민지의 전화번호"처럼 값으로 찾으려면 결국 처음부터 훑어야 해요. 그런데 딕셔너리와 집합은 값으로도 거의 한 번에 찾아요. 다음 강의에서는 값을 번호로 바꿔 배열의 칸에 바로 넣는 해시 테이블을 직접 만들어 보고, 충돌과 크기 늘리기, 좋은 해시 함수가 갖춰야 할 성질까지 다뤄요.