동적 배열은 길이와 내부 용량을 구분하고 필요할 때 저장소를 확장하는 자료구조다. 두 배 확장 구현, 복사 횟수 분석, 삽입·삭제와 축소 진동, 참조 수명, 예약·메모리·동시성의 한계를 실행 예제와 모델 기반 검사로 설명한다.
개요: 길이는 변하지만 인덱스 접근은 유지한다
동적 배열(dynamic array)은 원소를 순서대로 담는 내부 배열을 사용하면서 필요한 경우 더 큰 저장 공간으로 옮겨 길이를 늘리는 자료구조다. 배열 인덱스로 원소를 읽는 장점과 실행 중 원소를 추가하는 편의를 함께 제공한다. 다만 모든 추가·삭제가 같은 비용으로 끝나는 것은 아니다.
예를 들어 로그 항목을 차례로 모을 때 처음부터 최종 항목 수를 알기 어렵다. 매번 정확히 한 칸만 큰 배열을 만들면 같은 항목을 반복해서 옮기게 된다. 동적 배열은 여유 공간을 확보하고 그 공간을 여러 번의 추가에 나눠 사용한다. 여유 공간은 쓸모없는 낭비만이 아니라 미래의 재할당을 줄이는 자원이다.
이 문서는 길이와 용량, 확장 비율, 분할 상환 분석, 중간 삽입과 삭제, 축소 정책을 하나의 구현으로 연결한다. 이어서 값과 참조의 차이, 반복 중 변경, 메모리와 지연 시간, 언어별 API 계약을 설명한다. 단순히 append가 빠르다는 사실보다 어떤 연산열에서 왜 빠른지를 이해하는 데 초점을 둔다.
모든 실행 예제는 Python 3.9.6으로 작성하고 검사했다. 클래스와 조작 함수는 앞 절의 정의를 이후 예제에서도 사용한다. 직접 만든 클래스는 학습용이며 Python list의 실제 내부 구현이나 성장 비율을 재현한 것이 아니다. 다른 언어의 API는 공식 문서의 계약을 비교하며 해당 런타임에서 코드를 실행했다는 뜻은 아니다.
길이 size와 용량 capacity의 차이
길이 n은 현재 사용자에게 보이는 원소의 수이고, 용량 C는 내부에 확보한 슬롯 수다. 항상 0≤n≤C를 유지한다. 유효 원소는 앞의 n칸이며 뒤의 C-n칸은 다음 추가를 위해 남겨 둔다. 용량이 8이어도 길이가 3이면 읽을 수 있는 인덱스는 0,1,2뿐이다.
아래 backing은 물리적인 슬롯을 흉내 내는 목록이다. 첫 두 칸만 원소이므로 size는 2이고 capacity는 4다. 내부 배열에 접근할 수 있다는 이유로 backing[3]을 정상 원소로 반환하면 구현의 여유 공간이 외부 계약에 새어 나온다. 경계 검사는 용량이 아니라 길이를 기준으로 해야 한다.
None도 사용자가 저장하고 싶은 정상 값일 수 있다. 따라서 None을 만날 때까지 읽는 방식으로 길이를 계산해서는 안 된다. 길이를 별도 정수로 유지하면 빈 슬롯과 값이 None인 원소를 구분할 수 있고 len 연산도 상수 시간에 처리할 수 있다. 내부 초기화 값은 구현상의 표식일 뿐 사용자 데이터의 끝을 뜻하지 않는다.
예제 코드
backing = ['A', None, None, None]
size = 2
print(size, len(backing))
print(backing[:size])
print(0 <= 3 < size)실행 결과
2 4
['A', None]
False배열과 연결 리스트 사이의 선택
고정 길이 배열은 할당 후 원소 수가 바뀌지 않는 형태를 말하고, 동적 배열은 그 위에 길이·용량 관리 규칙을 더한 구조다. 동적이라는 말은 각 원소를 임의 위치에 흩어 놓는다는 뜻이 아니다. 현재의 내부 저장소에서는 인덱스에 대응하는 슬롯이 연속적으로 배치된 모델을 사용한다.
연결 리스트는 다음 노드를 가리키는 연결을 따라가므로 i번째 위치를 찾는 데 앞에서부터 이동해야 할 수 있다. 동적 배열은 위치 계산으로 바로 슬롯에 접근하지만 가운데에 새 원소를 넣으면 뒤쪽 원소를 밀어야 한다. 빠른 임의 접근과 빠른 임의 위치 삽입을 동시에 무조건 얻는 구조는 아니다.
연결 리스트의 삽입이 O(1)이라는 비교에는 삽입 지점의 노드나 필요한 이전 노드를 이미 알고 있다는 전제가 있다. 매번 i번째 노드를 먼저 찾아야 한다면 탐색 비용을 더해야 한다. 반대로 동적 배열의 삽입 위치를 이분 탐색으로 O(log n)에 찾아도 뒤의 이동 비용은 여전히 남는다.
실무에서 순차 저장·순회·끝 추가가 많으면 동적 배열이 좋은 기본 선택이 될 수 있다. 앞쪽 삭제가 계속되는 큐, 안정된 노드 주소가 중요한 구조, 중간 편집이 많은 긴 텍스트는 덱·연결 구조·다른 편집 자료구조를 함께 비교한다. 연산 하나의 표기보다 전체 작업 비율과 참조의 수명 요구가 선택을 좌우한다.
작동하는 최소 구현: 두 배 확장
아래 DynamicArray는 최소 용량 1에서 시작하고 꽉 찼을 때 두 배로 늘린다. _resize는 새 슬롯 목록을 먼저 만들고 기존의 유효 원소만 복사한 뒤 저장소를 교체한다. append는 확보된 다음 칸에 값을 넣고 마지막에 길이를 하나 늘린다. copied는 확장으로 옮긴 원소 참조 수를 세는 교육용 계측값이다.
Python 목록을 내부 버퍼로 사용하지만 그 목록의 append를 호출해 성장시키지 않는다. [None] * capacity로 고정된 슬롯 수를 만들고 직접 인덱스로 대입하여 외부 동적 배열의 정책을 드러낸다. 따라서 이 코드는 실제 메모리 주소를 조작하지 않고도 용량·복사 횟수·길이 불변식을 관찰할 수 있다.
get은 음수 인덱스를 지원하지 않도록 계약을 단순화했다. Python list가 음수 인덱스를 지원한다고 이 학습용 클래스까지 같은 의미인 것은 아니다. 인덱스는 정수라는 전제이며 슬라이스, 반복자, 스레드 안전성, 메모리 상한 같은 완성된 컨테이너 기능은 제공하지 않는다.
to_list는 유효 원소를 복사해 외부 목록으로 반환한다. 따라서 이 호출은 O(n)이며 get과 같은 상수 시간 접근이 아니다. 디버깅 출력에 편리하지만 매 반복에서 전체 상태를 복사하면 알고리즘 자체보다 출력과 관찰 비용이 커질 수 있다.
예제 코드
class DynamicArray:
def __init__(self):
self._data = [None]
self._size = 0
self.copied = 0
def __len__(self):
return self._size
@property
def capacity(self):
return len(self._data)
def _resize(self, capacity):
if capacity < self._size or capacity < 1:
raise ValueError('invalid capacity')
new_data = [None] * capacity
for i in range(self._size):
new_data[i] = self._data[i]
self.copied += self._size
self._data = new_data
def append(self, value):
if self._size == self.capacity:
self._resize(2 * self.capacity)
self._data[self._size] = value
self._size += 1
def get(self, index):
if not 0 <= index < self._size:
raise IndexError('index out of range')
return self._data[index]
def to_list(self):
return self._data[:self._size]
a = DynamicArray()
for value in [10, 20, 30]:
a.append(value)
print(a.to_list(), len(a), a.capacity, a.copied)
print(a.get(1))실행 결과
[10, 20, 30] 3 4 3
20확장 순간을 한 단계씩 추적하기
앞의 클래스 정의 뒤에 아래 코드를 실행하면 각 추가 이후 길이·용량·누적 복사 수를 볼 수 있다. 첫 원소는 용량 1에 그대로 들어가고, 두 번째에서는 1개를 복사해 용량 2로 이동한다. 세 번째에서는 2개를 더 복사해 누적 3이 되고 용량은 4가 된다.
네 번째는 남은 칸을 사용하므로 복사가 없다. 다섯 번째에서 4개를 옮겨 용량 8로 바뀌고 누적 복사는 7이 된다. 여덟 번째까지 용량은 그대로이고, 아홉 번째에서 8개를 더 옮겨 누적 15가 된다. 모든 호출이 같은 일을 하는 것은 아니지만 큰 복사 사이에 여러 번의 가벼운 추가가 있다.
이 표의 copied는 재할당으로 옮긴 기존 원소만 센다. 새 값을 넣는 대입, 새 슬롯을 초기화하는 비용, 메모리 할당자의 내부 작업은 별도다. 정확히 무엇을 계측했는지 구분해야 15라는 숫자를 실제 CPU 명령 수나 실행 시간으로 오해하지 않는다.
예제 코드
a = DynamicArray()
for value in range(1, 10):
a.append(value)
print(len(a), a.capacity, a.copied)실행 결과
1 1 0
2 2 1
3 4 3
4 4 3
5 8 7
6 8 7
7 8 7
8 8 7
9 16 15왜 한 칸씩 확장하면 느려지는가
정확히 필요한 길이만큼 새 배열을 만들면 한 번의 추가에서 낭비되는 여유 칸은 없지만 이전 원소를 계속 옮겨야 한다. n개를 차례로 넣을 때 복사 수는 0+1+2+…+(n-1)=n(n-1)/2가 된다. 공간을 최소화하는 국소적 선택이 전체 시간에서는 이차 비용을 만든다.
아래 exact_growth는 실제 배열을 할당하지 않고 정책에 따른 복사 수를 계산한다. n=8에서는 28개, n=16에서는 120개를 옮긴다. 두 배 정책의 7개와 15개에 비해 차이가 빠르게 벌어진다. 양쪽 모두 마지막에는 같은 수의 원소를 담지만 거기까지 도달하는 작업량이 다르다.
매번 고정된 100칸씩 늘리는 정책도 입력이 계속 커지면 비슷한 문제를 갖는다. 확장 횟수는 줄어도 확장 사이의 간격이 일정하므로 이전 자료를 반복 복사하는 합이 이차로 자란다. 고정된 입력 상한에서는 실용적일 수 있지만 일반적인 분할 상환 O(1) 근거로 삼을 수는 없다.
예제 코드
def exact_growth(n):
size = copied = 0
while size < n:
copied += size
size += 1
return copied
for n in [8, 16]:
print(n, exact_growth(n), n * (n - 1) // 2)실행 결과
8 28 28
16 120 120분할 상환 O(1)의 합계 증명
두 배 확장에서 복사한 원소 수는 1+2+4+…로 늘어난다. 마지막으로 복사한 크기가 2^k이면 이 합은 2^(k+1)-1이다. n개의 추가를 마쳤을 때 마지막 복사 크기는 n보다 작으므로 누적 복사는 2n 미만이다. 새 원소를 쓰는 n번을 더해도 전체 작업은 n의 상수 배로 묶인다.
따라서 비어 있는 배열에서 시작한 끝 추가 n회의 총비용은 O(n), 연산당 분할 상환 비용은 O(1)이다. 확률 분포를 가정하거나 여러 사용자의 평균을 낸 결론이 아니다. 정의한 확장 정책을 따르는 연산열 전체에 대한 합계 보장이다.
이 구현은 새 슬롯 목록을 None으로 초기화하므로 기존 원소 복사 외에 새 용량에 비례한 초기화 비용도 있다. 새 용량들의 합 역시 기하급수 합이므로 점근적으로 선형이라는 결론은 유지된다. 다만 copied 계측값만으로 실제 총비용의 상수까지 계산했다고 할 수는 없다.
사용자가 매번 수동 축소를 요청하거나 매 추가 전에 정확히 한 칸만 예약하는 별도 정책을 끼워 넣으면 같은 증명을 그대로 적용할 수 없다. 보장은 자료구조 이름에 자동으로 붙는 것이 아니라 구체적인 연산과 용량 정책에 붙는다. 큰 원소의 복사·이동이 상수 비용이 아닌 경우에는 원소당 비용도 따로 포함한다.
비싼 한 번과 지연 시간의 차이
분할 상환 분석은 전체 처리량을 설명하지만 특정 요청의 최대 지연을 없애지 않는다. 용량 C가 꽉 찬 상태에서 한 번 추가하면 C개를 옮길 수 있다. 게임 프레임, 오디오 콜백, 지연에 민감한 서버 요청처럼 순간적인 멈춤이 문제인 상황에서는 평균적인 처리량만으로 충분하지 않다.
아래는 각 추가에서 발생한 기존 원소 복사 수에 새 값 대입 1을 더한 모델이다. 9번의 비용은 1,2,3,1,5,1,1,1,9다. 총합은 24지만 마지막 한 번은 9로 튄다. 실제 시간은 할당·페이지 접근·스케줄링에도 영향을 받으므로 이 숫자를 밀리초로 바꾸어 해석하지 않는다.
최대 크기를 합리적으로 예측할 수 있다면 여유 시간에 미리 용량을 확보할 수 있다. 상한이 고정된 실시간 경로에서는 고정 용량 버퍼와 초과 시 정책을 선택할 수도 있다. 블록 단위 저장이나 점진적 이전은 긴 복사를 나누지만 주소 연속성, 접근 로직과 구현 복잡성에 다른 비용을 만든다.
예제 코드
a = DynamicArray()
costs = []
for value in range(9):
before = a.copied
a.append(value)
costs.append(1 + a.copied - before)
print(costs)
print(sum(costs), max(costs))실행 결과
[1, 2, 3, 1, 5, 1, 1, 1, 9]
24 9성장 비율의 시간·공간 교환
성장 계수 g가 1보다 큰 고정 상수라면 확장 때마다 용량을 대략 g배로 늘리는 정책을 생각할 수 있다. g가 작으면 확장 직후의 여유 공간이 줄지만 확장이 더 자주 일어나고, g가 크면 재할당 횟수는 줄어도 사용하지 않는 슬롯이 늘 수 있다. 모든 환경에 가장 좋은 하나의 비율이 있는 것은 아니다.
다음 시뮬레이션은 정수 비율 3/2와 2를 비교하고 올림을 정수 계산으로 구현한다. n=100까지의 용량·복사 수를 직접 계산하며 특정 언어가 실제로 이 비율을 사용한다고 주장하지 않는다. 할당자 크기 등급이나 원소 크기, 대량 추가 최적화가 있으면 현실의 용량은 단순 등비수열과 다를 수 있다.
원소 참조 하나가 작아도 배열이 매우 많으면 여유 공간의 합이 커진다. 반대로 복사하는 원소가 크고 추가가 빈번하면 이동량 감소가 중요할 수 있다. 성장 계수를 평가할 때는 한 배열의 최대 여유뿐 아니라 배열 수, 생존 기간, 재사용 패턴과 순간 최대 메모리를 함께 본다.
예제 코드
def simulate_growth(n, numerator, denominator):
capacity = 1
copied = 0
for size in range(n):
if size == capacity:
copied += size
capacity = max(capacity + 1,
(capacity * numerator + denominator - 1) // denominator)
return capacity, copied
print(simulate_growth(100, 3, 2))
print(simulate_growth(100, 2, 1))실행 결과
(140, 272)
(128, 127)중간 삽입: 뒤에서부터 밀어야 한다
길이 n의 배열에서 위치 i 앞에 원소를 넣으려면 i부터 n-1까지의 원소를 오른쪽으로 한 칸 이동한다. 빈칸을 만드는 이동은 뒤에서 앞으로 해야 한다. 앞에서부터 복사하면 방금 덮어쓴 값을 다음 단계에서 다시 복사하여 원래 값을 잃는다.
아래 insert는 앞의 DynamicArray 정의와 함께 사용한다. 삽입 경계는 0부터 n까지 허용하므로 get의 0≤i<n과 다르다. i=n은 끝 추가이고 i=0은 맨 앞 삽입이다. 먼저 필요 용량을 확보한 뒤 뒤쪽부터 옮기고 새 값을 넣으며 마지막에 길이를 늘린다.
원소 이동은 n-i회이므로 재할당을 제외해도 O(n-i+1)이다. 앞 삽입을 n번 반복하면 이동 합계가 이차가 된다. 이분 탐색으로 위치를 빨리 찾거나 넉넉히 reserve해도 이 순서 유지 비용 자체는 없어지지 않는다.
이 예제의 함수는 설명을 위해 클래스 내부 필드에 접근한다. 실제 라이브러리에서는 insert를 클래스 메서드로 넣고 내부 표현을 숨기는 편이 좋다. 외부 코드가 _size나 _data를 임의로 바꾸면 길이·용량 불변식을 쉽게 깨뜨릴 수 있다.
예제 코드
def insert(array, index, value):
if not 0 <= index <= len(array):
raise IndexError('insertion index out of range')
if len(array) == array.capacity:
array._resize(2 * array.capacity)
for j in range(len(array), index, -1):
array._data[j] = array._data[j - 1]
array._data[index] = value
array._size += 1
a = DynamicArray()
for value in [10, 20, 30]:
a.append(value)
insert(a, 1, 99)
insert(a, len(a), 40)
print(a.to_list(), a.capacity)실행 결과
[10, 99, 20, 30, 40] 8잘못된 이동 순서를 실제로 비교하기
다음 첫 루프는 [10,20,30]의 위치 1에 삽입할 빈칸을 만들면서 앞에서 뒤로 복사한다. 20을 위치 2에 덮어쓴 뒤 그 위치를 다시 읽으므로 마지막에도 20을 쓰게 된다. 결과는 [10,99,20,20]이고 원래 30이 사라진다.
두 번째 루프는 마지막 원소부터 옮기므로 아직 읽지 않은 원본을 덮지 않는다. 결과 [10,99,20,30]이 계약에 맞는다. 배열 이동 코드를 검토할 때 단순히 반복 범위만 보는 대신 원본과 목적 구간이 겹치는지를 확인해야 한다.
낮은 수준의 언어에서는 겹친 영역에 안전한 복사 API인지도 구별한다. 어떤 함수는 중첩을 허용하고 어떤 함수는 허용하지 않는다. 아래 예제는 언어별 메모리 복사 함수를 호출하지 않고 인덱스 대입으로 오류의 원인을 보여준다. 작은 서로 다른 값들을 사용하면 복사 방향의 실수를 쉽게 드러낼 수 있다.
예제 코드
bad = [10, 20, 30, None]
for j in range(1, 3):
bad[j + 1] = bad[j]
bad[1] = 99
print(bad)
good = [10, 20, 30, None]
for j in range(3, 1, -1):
good[j] = good[j - 1]
good[1] = 99
print(good)실행 결과
[10, 99, 20, 20]
[10, 99, 20, 30]삭제와 사용하지 않는 참조 비우기
순서를 보존하는 삭제는 제거한 위치 뒤의 원소를 왼쪽으로 옮긴다. 삭제할 값을 먼저 저장하고 이동을 마친 뒤 길이를 줄인다. 마지막 유효 칸이었던 위치는 이제 여유 공간이므로 None으로 비운다. 그렇지 않으면 사용자에게는 삭제된 객체를 내부 저장소가 계속 참조할 수 있다.
아래 remove_at은 길이가 용량의 4분의 1 이하가 되면 용량을 절반으로 줄이는 정책도 포함한다. 최소 용량은 1이다. 확장과 축소를 서로 다른 임계점에서 수행하는 이유는 다음 절에서 설명한다. 반환값은 삭제한 원소다.
첫째 삭제는 [10,20,30]에서 20을 없애고 [10,30]을 남긴다. 다음으로 끝의 30을 제거하면 길이 1, 용량 2가 된다. 내부 여유 슬롯은 None이다. None 값을 저장한 정상 원소도 허용되므로 이것은 길이 계산 방식이 아니라 참조 정리 방식이다.
끝 삭제는 이동이 없지만 축소가 일어나면 복사가 생길 수 있다. 중간 삭제는 뒤의 원소 수에 비례한 이동이 필요하다. “삭제 O(1)”이라고 쓰려면 끝에서 지우는지, 순서를 유지하는지, 축소 비용을 어떤 방식으로 분석하는지 함께 명시해야 한다.
예제 코드
def remove_at(array, index):
if not 0 <= index < len(array):
raise IndexError('removal index out of range')
value = array._data[index]
for j in range(index, len(array) - 1):
array._data[j] = array._data[j + 1]
array._size -= 1
array._data[len(array)] = None
if array.capacity > 1 and len(array) <= array.capacity // 4:
array._resize(max(1, array.capacity // 2))
return value
a = DynamicArray()
for value in [10, 20, 30]:
a.append(value)
print(remove_at(a, 1), a.to_list(), a.capacity)
print(remove_at(a, 1), a.to_list(), a.capacity)
print(a._data)실행 결과
20 [10, 30] 4
30 [10] 2
[10, None]축소 임계점을 넓혀 진동을 막는다
가득 차면 두 배로 확장하고 절반 이하가 되면 곧바로 절반으로 축소한다고 하자. 용량 8에 원소 8개인 상태에서 추가하면 길이 9, 용량 16이 된다. 바로 한 개를 삭제해 길이 8이 되면 다시 용량 8로 줄어든다. 추가와 삭제를 반복할 때마다 많은 원소를 옮기는 진동이 생긴다.
이 문서의 정책은 확장은 가득 찼을 때, 축소는 4분의 1 이하일 때 수행한다. 용량 16에 길이 8이면 그대로 두고 길이 4까지 줄어야 용량 8로 바뀐다. 축소 직후에도 여유가 남으므로 다음 추가 하나가 곧바로 확장을 부르지 않는다. 서로 다른 임계점을 두는 히스테리시스의 예다.
아래 모델은 길이 8에서 시작해 추가·삭제 쌍을 5번 반복한다. 절반 축소는 80개를 복사하지만 4분의 1 축소는 처음 확장의 8개만 복사한다. 두 모델의 최종 길이는 같아도 용량과 이전 비용이 다르다. 이는 인위적인 극단 입력이지만 정책의 약점을 명확하게 보여준다.
자동 축소가 언제나 필요한 것은 아니다. 비슷한 최대 크기의 작업을 반복한다면 용량을 보유해 다음 작업에서 재사용할 수 있다. 한 번 큰 작업 후 오랫동안 작은 상태가 유지된다면 명시적인 축소가 유용할 수 있다. 어느 시점에 메모리를 돌려줄지는 지연과 재사용을 함께 고려한 정책이다.
예제 코드
def oscillation(shrink_divisor):
size = capacity = 8
copied = 0
for _ in range(5):
if size == capacity:
copied += size
capacity *= 2
size += 1
size -= 1
if size <= capacity // shrink_divisor:
copied += size
capacity //= 2
return size, capacity, copied
print(oscillation(2))
print(oscillation(4))실행 결과
(8, 8, 80)
(8, 16, 8)reserve와 resize는 목적이 다르다
예약은 앞으로 들어올 원소를 위한 공간을 확보하고, 크기 변경은 실제로 존재하는 원소 수를 바꾸는 개념이다. 예를 들어 빈 컨테이너의 용량을 100으로 예약했다고 100개 원소를 읽을 수 있는 것은 아니다. 길이는 여전히 0이다. 반대로 크기를 100으로 늘리는 API는 새 원소를 생성하거나 기본값으로 채우는 의미를 가질 수 있다.
아래 reserve는 학습용 클래스에 필요한 최소 용량을 보장하며 길이를 바꾸지 않는다. 빈 배열에 10칸을 확보한 뒤 10개를 추가하면 기존 원소의 재복사는 0이다. 그러나 처음 10칸을 할당·초기화한 비용이 없어진 것은 아니다. 비용이 요청 처리 중에서 준비 시점으로 옮겨진 것이다.
예상량을 알 수 있는 파일 파싱이나 데이터 일괄 적재에서는 예약이 유용하다. 하지만 신뢰할 수 없는 외부 길이를 그대로 예약하면 과도한 메모리를 요구할 수 있으므로 입력 상한을 확인한다. 작게 여러 번 정확히 예약하는 방식은 자동 성장의 이점을 약화할 수 있다.
reserve라는 이름도 언어별 인수 의미가 다르다. C++ vector의 reserve는 총 용량을 기준으로 하지만 Rust Vec의 reserve는 현재 길이에 더할 추가 원소 수를 받는다. 이름이 같다고 매개변수를 그대로 옮기지 말고 계약을 확인해야 한다.
예제 코드
def reserve(array, minimum_capacity):
if minimum_capacity < 0:
raise ValueError('negative capacity')
if minimum_capacity > array.capacity:
array._resize(minimum_capacity)
a = DynamicArray()
reserve(a, 10)
print(len(a), a.capacity)
for value in range(10):
a.append(value)
print(len(a), a.capacity, a.copied)실행 결과
0 10
10 10 0순서를 포기하면 삭제 비용이 달라진다
게임의 활성 입자 목록처럼 원소의 순서가 중요하지 않다면 삭제 위치에 마지막 원소를 옮기고 길이를 하나 줄일 수 있다. 뒤의 모든 원소를 당기지 않으므로 재할당을 하지 않는 이 삭제 단계는 상수 개의 대입으로 끝난다. 대신 원래의 순서는 유지되지 않는다.
아래 [A,B,C,D]에서 인덱스 1을 삭제하면 D가 그 자리를 채워 [A,D,C]가 된다. [A,C,D]가 필요한 요구사항에는 사용할 수 없다. 빠른 구현으로 바꾸면서 반환 순서나 외부 인덱스의 의미를 몰래 바꾸면 성능 개선이 아니라 기능 오류다.
원소 ID에서 현재 인덱스로 가는 사전을 함께 유지한다면 마지막 원소가 이동한 새 인덱스도 갱신해야 한다. 삭제된 ID를 사전에서 제거하는 작업과 배열 변경이 일관되게 이루어져야 한다. 인덱스를 외부 식별자로 노출하는 설계에서는 이런 이동이 특히 위험하므로 안정적인 별도 ID를 사용한다.
예제 코드
values = ['A', 'B', 'C', 'D']
index = 1
removed = values[index]
values[index] = values[-1]
values.pop()
print(removed, values)실행 결과
B ['A', 'D', 'C']값을 옮기는가, 객체 참조를 옮기는가
동적 배열의 슬롯에 객체 자체를 담는지 객체를 가리키는 참조를 담는지는 언어와 타입에 따라 다르다. 참조를 옮기는 배열에서는 내부 저장소를 복사해도 각 객체의 내용까지 새로 복제한 것은 아니다. 바깥 컨테이너의 독립성과 안쪽 객체의 독립성을 구분해야 한다.
다음 Python 예제에서 copy는 바깥 목록만 복사한다. copy[0]에 값을 추가하면 같은 안쪽 목록을 공유하는 original에도 반영된다. 반면 copy 자체에 새 원소를 추가하는 것은 original의 길이를 바꾸지 않는다. 동적 배열의 확장 과정에서 참조를 복사하는 것과 깊은 복사는 서로 다른 작업이다.
이 문서의 _resize도 Python 객체 참조를 옮긴다. 큰 문자열 객체를 참조한다고 그 문자열 전체를 매 확장마다 복사하는 것은 아니다. 반면 큰 값 타입을 직접 저장하는 다른 컨테이너에서는 원소 이동 비용이 커질 수 있다. O(n)의 n번 이동이라는 분석 뒤에 원소별 비용이 있음을 기억한다.
깊은 복사를 선택하면 공유 변경을 막을 수 있지만 객체 그래프 전체의 복사 비용과 의미를 검토해야 한다. 파일 핸들, 잠금, 외부 연결 같은 자원은 단순 복제로 같은 의미를 만들기 어렵다. 성능 설명에 copy라는 단어를 쓸 때 무엇을 복사하는지 구체적으로 적는 것이 중요하다.
예제 코드
original = [[1], [2]]
copy = original.copy()
copy[0].append(9)
copy.append([3])
print(original)
print(copy)
print(original[0] is copy[0])실행 결과
[[1, 9], [2]]
[[1, 9], [2], [3]]
True재할당과 포인터·반복자의 수명
내부 저장소가 교체되면 이전 저장소의 원소 위치를 가리키던 포인터나 반복자가 더 이상 유효하지 않을 수 있다. 동적 배열 객체를 가리키는 참조와 내부 원소의 주소는 같은 것이 아니다. 객체 자체의 이름이 유지되어도 내부 버퍼는 옮겨질 수 있다.
C++ vector는 재할당 시 원소를 가리키던 참조·포인터·반복자가 무효화되는 계약을 명시한다. 충분한 reserve로 일부 재할당을 피할 수 있지만 중간 삽입·삭제에 따른 무효화 규칙까지 모두 없애는 것은 아니다. 사용 중인 연산의 규칙을 따로 확인해야 한다.
Rust는 안전한 참조를 유지한 채 Vec를 변경하려는 충돌을 소유권과 대여 규칙으로 제한한다. 원시 포인터를 사용하는 unsafe 코드에서는 호출자가 수명과 재할당의 영향을 직접 책임져야 한다. 다른 언어의 포인터 오류 예제를 그대로 옮겨 같은 방식으로 동작한다고 설명하지 않는다.
Python에서 목록 안 객체의 참조를 별도로 잡아 두는 것은 내부 슬롯의 주소를 잡는 것과 다르다. 목록에서 객체를 제거해도 별도 강한 참조가 있으면 그 객체는 계속 사용될 수 있다. 그러나 저장해 둔 정수 인덱스는 앞 삽입이나 삭제 후 다른 객체를 가리킬 수 있다. 메모리 안전과 논리적인 위치 안정성은 별개의 문제다.
순회 중 삭제로 원소를 건너뛰는 오류
순회하는 컨테이너에서 원소를 삭제하면 뒤의 원소가 앞으로 당겨진다. 반복자가 다음 인덱스로 넘어가면서 방금 앞으로 이동한 원소를 건너뛸 수 있다. 오류가 항상 예외로 드러나는 것은 아니며 결과만 조용히 틀릴 수 있다.
아래 첫 코드는 짝수를 지우려 하지만 2를 지운 다음 4가 앞으로 이동하면서 검사 대상에서 빠진다. 최종 [4,7]은 의도와 다르다. 두 번째는 원본을 순회해 유지할 값으로 새 목록을 만들므로 [7]이 된다. 목록 컴프리헨션은 새 저장 공간을 사용한다는 차이가 있다.
기존 목록 객체의 정체성을 유지해야 한다면 결과를 values[:]에 대입하는 방법을 검토할 수 있다. 다른 코드가 같은 목록을 참조하는 상황에서 values=새목록은 지역 변수만 바꾸지만 슬라이스 대입은 기존 목록을 바꾼다. 어떤 별칭이 변경을 보아야 하는지 요구사항을 먼저 정한다.
Java의 fail-fast 반복자는 변경을 발견하면 예외를 내는 정책을 제공하지만 그것을 동시성 제어나 모든 경쟁 상태 검출의 보장으로 사용해서는 안 된다. 언어마다 반복 중 변경 규칙이 다르므로 Python에서 관찰한 결과를 일반 규칙으로 만들지 않는다.
예제 코드
values = [2, 4, 6, 7]
for value in values:
if value % 2 == 0:
values.remove(value)
print(values)
values = [2, 4, 6, 7]
values = [value for value in values if value % 2 != 0]
print(values)실행 결과
[4, 7]
[7]일괄 제거는 한 번의 압축으로 처리할 수 있다
지울 원소가 많을 때 매번 remove_at을 호출하면 같은 뒤쪽 원소를 여러 번 옮길 수 있다. 유지할 원소만 앞에서부터 다시 쓰는 압축 방식은 각 원소를 한 번 읽고 최대 한 번 쓰므로 전체 O(n)으로 순서를 보존할 수 있다.
아래 write는 다음 보관 위치다. 짝수만 유지하려고 [1,2,3,4,5,6]을 읽으면서 2,4,6을 앞쪽에 쓰고 마지막에 남은 꼬리를 삭제한다. 읽기 위치보다 쓰기 위치가 앞서 나가지 않으므로 아직 읽지 않은 자료를 덮지 않는다. 결과는 [2,4,6]이다.
이 예제는 길이를 바꾸는 꼬리 삭제를 순회가 끝난 뒤 한 번 수행한다. 비교 조건이 예외를 던지면 일부 값이 이미 덮였을 수 있으므로 작업 전체의 원자성을 보장하지 않는다. 실패 시 원본 보존이 필요하면 별도 결과를 만든 뒤 교체하는 방식과 추가 메모리 비용을 비교한다.
성능 최적화는 요구사항을 좁힐 때 더 명확해진다. 순서를 유지해야 하는지, 원래 컨테이너를 바꿔야 하는지, 실패 시 되돌려야 하는지를 정하면 필터링·제자리 압축·끝 원소 교환 중 어떤 방식이 맞는지 판단할 수 있다.
예제 코드
values = [1, 2, 3, 4, 5, 6]
write = 0
for value in values:
if value % 2 == 0:
values[write] = value
write += 1
del values[write:]
print(values)실행 결과
[2, 4, 6]메모리 사용량: 여유 슬롯과 순간 최대치
용량이 C이고 슬롯 크기가 s라면 저장소의 슬롯 부분은 대략 C·s 바이트다. 여기에 컨테이너 헤더, 할당자 관리 정보, 정렬을 위한 패딩과 원소가 별도로 소유하는 객체 메모리가 더해질 수 있다. len만으로 실제 메모리 전체를 계산할 수 없는 이유다.
재할당 중에는 이전 버퍼와 새 버퍼가 잠시 함께 존재할 수 있다. 용량 C에서 2C로 복사하는 단순 구현은 이전 C와 새 2C를 동시에 유지하므로 순간 슬롯 공간이 3C에 해당할 수 있다. 실제 할당자가 제자리 확장을 제공하면 상황이 달라질 수 있지만 항상 가능하다고 가정해서는 안 된다.
이 문서의 Python 구현도 새 목록을 완성한 뒤 _data를 교체하므로 두 버퍼가 겹쳐 살아 있는 순간이 있다. 다만 슬롯이 참조인 만큼 원소 객체 전체를 두 벌 복제하는 것은 아니다. 슬롯 공간, 객체 공간, 일시적인 작업 공간을 나누어 설명해야 과장이나 누락을 피할 수 있다.
원소 수를 줄여도 프로세스가 운영체제에 메모리를 즉시 반납한다는 보장은 없다. 컨테이너의 용량 정책, 런타임 메모리 관리자와 할당자의 재사용 정책이 개입한다. 메모리 문제를 조사할 때는 논리 길이, 내부 용량, 살아 있는 객체와 프로세스 측정값을 서로 구별한다.
캐시 지역성과 연속 저장의 한계
연속된 슬롯을 순서대로 읽으면 인접한 메모리를 함께 가져오는 캐시 동작과 잘 맞을 수 있다. 다음 노드를 따라가며 메모리 여기저기를 방문하는 구조보다 순회에 유리할 수 있는 이유다. 그러나 이 설명은 실제 하드웨어와 자료 표현에 따른 경향이며 모든 입력에서의 속도 순위를 보장하지 않는다.
참조 배열에서는 슬롯은 연속적이어도 각 슬롯이 가리키는 객체는 흩어져 있을 수 있다. 정수 값을 직접 담는 압축된 버퍼와 Python 객체 참조 목록은 같은 메모리 접근 패턴이 아니다. 객체의 필드를 읽는 작업에서는 추가적인 간접 접근이 필요할 수 있다.
숫자 데이터를 대량 처리한다면 원소 타입과 연속 저장을 명확히 하는 array나 전용 수치 배열을 검토할 수 있다. 대신 타입 변환, 정밀도, 브로드캐스팅 같은 API 의미가 달라진다. 동적 배열이라는 분류만으로 수치 연산의 벡터화나 병렬화를 자동으로 얻는 것은 아니다.
비교 실험에서는 동일한 작업과 동일한 결과를 만드는지 확인하고 할당·초기화·순회를 분리해 측정한다. 작은 배열에서는 언어 호출 비용이 지배할 수 있고 큰 배열에서는 메모리 대역폭이 중요해질 수 있다. 점근 표기가 같은 두 구현도 실제 비용의 상수와 병목은 다를 수 있다.
언어별 컨테이너 계약을 구분하기
Python list는 변경 가능한 시퀀스이며 일반적인 CPython 구현은 객체 참조를 담는 배열 방식이다. Python 코드에서 보통 사용하는 인터페이스는 len, append, insert, pop 등이고, 안정적인 공개 capacity 프로퍼티를 가정해서는 안 된다. 이 문서의 capacity는 직접 만든 클래스의 기능이다.
Java ArrayList는 재조정 가능한 배열 기반 List로, 끝 추가의 분할 상환 상수 비용을 문서화한다. ensureCapacity로 미리 여유를 확보할 수 있지만 구체적인 성장 배율은 API 보장이 아니다. 동시 구조 변경에 필요한 동기화와 반복자의 규칙도 함께 확인한다.
Rust Vec는 len과 capacity를 구분하고 reserve, shrink 계열과 순서를 유지하지 않는 swap_remove 같은 연산을 제공한다. 성장 전략의 세부 배율에 의존하지 않는 것이 좋다. C++ vector 역시 reserve와 resize를 구분하며 원소 타입의 이동·복사 특성과 반복자 무효화가 중요하다.
Go slice는 배열을 바라보는 길이·용량 정보를 가진 구조이며 부분 슬라이스가 같은 기저 배열을 공유할 수 있다. append가 새 저장소를 만들 수도 있으므로 반환한 슬라이스를 받아야 한다. 단순히 모든 언어의 가변 목록이 같은 소유권·복사·참조 규칙을 갖는다고 묶으면 버그가 생긴다.
할당 실패와 변경 순서
새 공간 확보는 실패할 수 있다. 길이 n이 유효하다고 해서 두 배 용량의 메모리를 반드시 확보할 수 있는 것은 아니다. 시스템 자원과 런타임 제한, 원소 크기와 주소 공간을 고려해야 한다. 고정 폭 정수로 용량을 계산하는 구현은 두 배 곱셈이나 바이트 수 계산의 넘침도 검사해야 한다.
학습용 _resize는 새 목록 할당과 원소 복사를 끝낸 뒤 _data를 교체한다. 할당이 실패하기 전에 기존 저장소를 먼저 버리지 않는 순서다. 다만 이것을 모든 상황에서 강한 예외 안전성을 제공하는 범용 구현으로 선언할 수는 없다. 복잡한 원소 이동, 사용자 콜백과 다른 언어의 예외 계약은 따로 검토해야 한다.
길이를 먼저 증가시킨 뒤 값을 쓰다가 실패하면 외부에서 초기화되지 않은 원소를 읽을 수 있는 상태가 생길 수 있다. 그래서 상태 변경 순서와 실패 지점마다 불변식이 유지되는지를 확인한다. 내부 버퍼를 직접 노출하면 중간 상태를 외부 코드가 관찰할 가능성도 커진다.
외부에서 받은 원소 수가 지나치게 크면 실제 할당 전에 거부하고 적절한 오류를 반환한다. 실패 시 일부 입력을 처리한 상태를 유지할지 전체 작업을 취소할지 API 계약에 적는다. 성능 최적화로 예약을 추가할 때도 오류가 발생하는 시점이 바뀔 수 있음을 고려한다.
동시 접근과 복합 연산
컨테이너의 어떤 개별 연산이 특정 런타임에서 원자적으로 보인다고 여러 연산을 묶은 절차까지 원자적인 것은 아니다. 길이가 남는지 확인한 다음 추가하거나, 검색한 인덱스를 나중에 삭제하는 사이에 다른 실행 흐름이 내용을 바꿀 수 있다. 자료구조 불변식과 업무 규칙의 불변식은 모두 보호해야 한다.
공유 배열을 여러 작업이 변경한다면 잠금으로 필요한 연산 묶음을 보호하거나 한 작업만 소유하고 메시지로 변경을 요청하는 구조를 사용할 수 있다. 읽기 전용 스냅샷은 변경과 조회를 분리하지만 복사 비용과 최신성의 차이를 만든다. 접근 방식은 언어의 메모리 모델과 라이브러리 보장에 맞춰 선택한다.
Java ArrayList는 기본적으로 동기화된 컨테이너가 아니다. 반복자가 변경을 감지하는 예외는 경쟁 상태를 올바르게 처리하는 설계를 대체하지 않는다. Python에서도 런타임 버전·빌드와 객체 종류를 무시한 채 모든 list 관련 절차가 안전하다고 일반화하지 않는다.
이 문서의 DynamicArray에는 잠금이 없으며 동시 쓰기를 지원하지 않는다. 예제의 단일 스레드 검사 통과는 동시 접근의 정확성을 검증한 것이 아니다. 공개 라이브러리로 발전시킬 때는 소유권, 동기화 범위, 반복 중 변경과 재진입에 대한 계약부터 정해야 한다.
모델 기반 검사: Python list와 연산열 대조
아래 검사는 앞의 DynamicArray, insert, remove_at 정의 뒤에 실행한다. 고정 시드로 끝 추가, 중간 삽입, 삭제와 조회를 섞어 총 2,000번 수행하고 Python list를 기준 모델로 사용한다. 매 단계마다 전체 원소 순서와 길이·용량 관계, 여유 슬롯이 비어 있는지도 확인한다.
임의의 큰 숫자만 넣는 검사보다 서로 다른 위치와 빈 상태를 반복해서 통과시키는 연산열이 유용하다. 확장 직전·직후와 축소 경계를 지나며 앞의 결과가 다음 연산의 입력이 되기 때문이다. 동일한 Python 환경에서 seed를 고정하면 오류가 났을 때 같은 연산열을 재현할 수 있다. 버전을 바꾸어 비교할 때는 난수 도구의 재현성 범위도 확인한다.
이 검사는 일반 정수 값과 지원한 인덱스 범위에 대한 동작을 대조한다. 메모리 부족, 사용자 정의 객체의 특수 동작과 동시 변경까지 검사한 것은 아니다. 임의 검사가 증명을 대체하지도 않는다. 구현의 기본 불변식과 독립적인 기준 모델을 함께 쓰면 단순 출력 확인보다 오류 발견에 도움이 된다.
예제 코드
import random
rng = random.Random(17)
a = DynamicArray()
reference = []
for step in range(2000):
operation = rng.randrange(4)
if operation == 0 or not reference:
value = rng.randrange(-100, 101)
a.append(value)
reference.append(value)
elif operation == 1:
index = rng.randrange(len(reference) + 1)
value = rng.randrange(-100, 101)
insert(a, index, value)
reference.insert(index, value)
elif operation == 2:
index = rng.randrange(len(reference))
assert remove_at(a, index) == reference.pop(index)
else:
index = rng.randrange(len(reference))
assert a.get(index) == reference[index]
assert a.to_list() == reference
assert 0 <= len(a) <= a.capacity
assert all(value is None for value in a._data[len(a):])
print('model steps', 2000)실행 결과
model steps 2000경계와 성장 비용을 별도로 검증하기
다음 검사는 빈 배열 조회·삭제, 범위를 벗어난 삽입과 음수 조회가 약속한 IndexError를 내는지 확인한다. 이후 None도 정상 값으로 추가·삭제할 수 있는지 검사한다. 내부의 빈칸 표시와 사용자 값이 같더라도 길이로 구분한다는 설계를 실제로 확인하는 것이다.
끝 추가만 하는 배열에서는 n=1부터 1,024까지 누적 복사 수가 2n 미만인지, 용량이 n 이상이며 2n 미만인지 매 단계에서 확인한다. 이 범위에서 2,048개의 조건이 통과한다. 정확한 성장 상한은 설명한 두 배 정책에만 적용하며 reserve로 큰 용량을 미리 잡은 배열에는 같은 용량 상한을 요구하지 않는다.
조회·삽입·삭제에서 허용하는 경계가 다르다는 점을 테스트 이름과 입력에 드러내면 off-by-one 오류를 줄일 수 있다. 실제 서비스에서는 최대 크기, 잘못된 입력 타입, 메모리 할당 실패를 주입하는 테스트도 필요할 수 있다. 교육 예제의 검사 범위를 완성된 제품의 검증 범위로 오해하지 않는다.
예제 코드
a = DynamicArray()
errors = 0
for action in [lambda: a.get(0), lambda: a.get(-1),
lambda: remove_at(a, 0), lambda: insert(a, 1, 9)]:
try:
action()
except IndexError:
errors += 1
assert errors == 4
a.append(None)
assert len(a) == 1 and a.get(0) is None
assert remove_at(a, 0) is None and len(a) == 0
print('expected errors', errors)
a = DynamicArray()
checks = 0
for n in range(1, 1025):
a.append(n)
assert a.copied < 2 * n
assert n <= a.capacity < 2 * n
checks += 2
print('growth checks', checks)실행 결과
expected errors 4
growth checks 2048실전 선택: 로그 수집, 큐, 편집 버퍼
크기를 미리 모르는 결과를 끝에 쌓고 마지막에 순회·정렬하는 작업은 동적 배열과 잘 맞는다. 검색 결과나 파싱된 레코드를 모으는 경우가 대표적이다. 예상량을 알면 한 번에 용량을 확보하고, 필요한 필드만 저장해 원소별 메모리를 줄이는 방법도 비교할 수 있다.
앞에서 하나씩 꺼내는 대기열에서는 매번 나머지를 당기는 구현이 비효율적일 수 있다. 원형 버퍼나 덱은 앞·뒤 연산에 맞는 다른 구조를 제공한다. 동적 배열을 쓰더라도 읽기 시작 인덱스를 별도로 두면 이동을 늦출 수 있지만 사용이 끝난 참조 정리와 재활용 정책을 설계해야 한다.
긴 텍스트의 중간을 자주 편집한다면 삽입 위치 뒤의 모든 문자를 계속 옮기는 비용이 커질 수 있다. gap buffer나 rope처럼 편집 위치와 변경 패턴을 이용하는 구조를 검토한다. 반면 작은 입력에서는 더 복잡한 구조의 관리 비용이 오히려 클 수 있으므로 규모와 작업 패턴에 맞춰 판단한다.
동적 배열을 이해했다는 것은 끝 추가의 O(1)을 외우는 데서 끝나지 않는다. 길이와 용량의 차이, 순서 보존 이동, 재할당 지연, 참조 수명과 실패 시 상태를 설명할 수 있어야 한다. 그 조건을 문서와 테스트에 남기면 구현을 바꾸더라도 요구사항을 유지하면서 성능을 개선할 수 있다.