"저수준 배열은 크기가 고정이야. Python 리스트는 아닌 척하지. 그 시치미를 끝까지 유지하는 방법이 은근히 기막혀."
리스트가 푸는 문제
저수준 배열은 크기를 선언하는 순간 거기 묶여. 그런데 최종 크기를 미리 아는 경우가 얼마나 되겠어. 동적 배열은 그 한계를 덮어 감춰. append하면 알아서 늘어나니까 쓰는 쪽에서는 끝이 없는 것처럼 느껴지지. Python의 list가 바로 동적 배열이야. C++의 vector, Java의 ArrayList도 이름만 다르지 같은 물건이고.
원리는 분할 상환 분석에서 이미 봤어. 리스트는 속에 배열을 하나 깔아두는데, 그 배열의 용량(capacity)이 실제 길이(length)보다 넉넉해. 여유가 남아 있는 동안 append는 O(1)이야. 다 차면 더 큰 블록을 새로 잡고 기존 참조를 옮기는데, 이 재할당이 O(n)이고. 구현체는 여유 용량을 기하급수적으로 늘려서 비싼 재할당이 어쩌다 한 번만 오게 만들어. 그래서 append가 분할 상환 O(1)인 거야. CPython이 정확히 얼마씩 키우는지는 버전마다 다를 수 있는 구현 세부사항이지, 항상 두 배로 늘린다는 약속이 아니야.
길이는 용량이 아니야
이 구분 하나면 나머지가 다 풀려. len(lst)는 실제로 담긴 항목 수고, 용량은 다음 재할당이 오기 전까지 담을 수 있는 수야. Python이 용량을 직접 보여주진 않지만 예약된 바이트로 짐작할 수 있어. 용량이라는 게 따로 있다는 걸 알고 나면 "append는 보통 즉시인데 가끔 걸린다"는 현상이 더 이상 이상하지 않아.
동적 배열은 고정 배열에 여유 용량과 기하급수적 성장 정책을 얹은 거야. 길이는 담긴 원소 수, 용량은 재할당 없이 담을 수 있는 수. 둘 사이의 여유가 append를 분할 상환 O(1)로 만들어.
연산과 그 진짜 비용
리스트가 한 줄로 붙어 있으니, 연산 비용은 "뭐가 움직여야 하나" 하나만 따지면 바로 나와.
lst[i]읽기와 쓰기는 O(1). 주소만 계산하면 끝이야.lst.append(x)와lst.pop()은 분할 상환 O(1). 끝에서만 일하니까 밀리는 게 없어.lst.insert(0, x)와lst.pop(0)은 O(n). 그 자리 뒤가 통째로 밀려.x in lst는 O(n). 처음부터 훑거든. 복잡도 트랙에서 본 숨은 반복문 함정이 이거야.lst[a:b]슬라이스는 O(b−a). 그 범위를 새 리스트로 복사해.
피파의 고백
평범한 리스트로 큐를 만들고
lst.pop(0)으로 꺼내 쓰던 시절이 있어. 작은 테스트에서는 멀쩡히 돌았지. 그런데 진짜 데이터를 넣으니까 O(n)이던 반복문이 소리 없이 O(n²)이 돼 있더라. pop(0)을 할 때마다 리스트 전체가 왼쪽으로 밀렸던 거야. 아빠가 앞에서 빼는 게 O(1)인 collections.deque를 보여줬어. 발상은 그대로고 구조만 맞게 바꾼 거지. 리스트가 잘못된 게 아니라, 내가 리스트의 비싼 쪽 끝을 공짜인 줄 알고 쓴 거였어.