컨테이너 선택에서 “삽입이 O(1)인가”라는 한 숫자만으로는 충분하지 않습니다. 위치를 인덱스로 받을지, 이미 유효한 노드 핸들을 가질지, 삽입 뒤 어느 범위의 데이터를 다시 순회할지를 한 작업 흐름으로 묶어야 실제 지연과 메모리 비용을 비교할 수 있습니다.
위치 탐색·변경·후속 조회 비용
목록의 네 번째 위치에 새 항목을 넣는 것과, 이미 가진 노드 핸들 뒤에 넣는 것은 다른 입력입니다. 연결 리스트는 위치를 이미 알고 있으면 링크 몇 개만 바꿀 수 있지만, 네 번째 노드를 찾으려면 앞에서 따라가야 합니다. 배열은 인덱스로 바로 찾지만 뒤 원소를 밀어야 합니다.
자료구조를 비교할 때 위치 찾기 + 변경 + 이후 조회를 합해야 합니다. 링크 변경만 O(1)이라는 사실을 전체 작업 비용으로 해석하면 선택을 잘못할 수 있습니다. 같은 중간 삽입이라도 인덱스 5,000을 받는 연결 리스트는 먼저 5,000번 가까이 링크를 따라간 뒤 O(1) 변경을 수행할 수 있습니다. 배열은 위치를 즉시 얻은 뒤 뒤 원소를 이동합니다. 따라서 실험에서는 “핸들을 미리 제공한 경우”와 “인덱스만 제공한 경우”를 분리하고, 삽입 직후 전체를 순회하는 비용까지 합산해야 두 자료구조의 선택이 바뀌는 이유가 드러납니다.
삽입 작업의 위치 탐색·변경 비용 분리
배열 [A,B,C,D]의 인덱스 1에 X를 넣으면 B·C·D를 옮겨 [A,X,B,C,D]로 만듭니다. 이중 연결 리스트에서 A 노드 핸들을 알고 있으면 X를 A와 B 사이에 연결합니다.
그림을 글로 읽기
- A 노드
- 새 X 노드: prev=A · next=B
- B 노드
- A 노드 → 새 X 노드: next 갱신
- 새 X 노드 → B 노드: next 연결
| 요구 | 배열 | 연결 리스트 |
|---|---|---|
| i번째 위치 찾기 | O(1) | 보통 O(n) |
| 알려진 위치에 중간 삽입 | 뒤 원소 O(n) 이동 | 노드 확보 뒤 링크 O(1) |
| 순차 전체 조회 | 연속 메모리 활용 | 포인터 추적·분산 할당 |
| 값으로 찾기, 색인 없음 | O(n) | O(n) |
리스트 노드를 새로 할당하는 비용도 남습니다. 단일 연결 리스트에서 삭제 대상 노드만 알면 일반적으로 직전 노드가 필요합니다. 다음 값을 복사해 삭제를 흉내 내는 방법은 마지막 노드에서 불가능하고 객체 정체성을 바꾸므로 일반 해법이 아닙니다.
객체 이동·포인터 이동과 간접 접근 비용 비교
객체 하나가 1KB이고 뒤에 1,000개를 밀어야 한다면 객체 저장 배열은 약 1MB의 이동이 필요할 수 있습니다. 8바이트 포인터 배열이라면 포인터 이동량은 약 8KB입니다. 이는 단순 바이트 이동 모형이며 실제 복사 생성·참조 관리 비용은 다를 수 있습니다.
대신 객체를 읽을 때 포인터를 한 번 더 따라가고, 대상이 흩어져 있으면 캐시 miss가 늘 수 있습니다. 배열 자체가 이동해도 대상 객체 주소가 유지되는 설계는 가능하지만, 소유자가 삭제한 객체를 관찰 포인터가 계속 읽어도 된다는 뜻은 아닙니다. 배열 삽입으로 논리 인덱스도 바뀝니다. 주소·인덱스·객체 ID의 안정성을 구분합니다.
deque 인터페이스와 구현별 비용
양끝 삽입·삭제가 주된 요구라면 deque가 자연스럽습니다. 하지만 deque라는 이름은 양끝 연산의 인터페이스를 뜻하며, 모든 언어가 같은 구현과 임의 인덱스 비용을 제공하지 않습니다. 블록 배열·원형 버퍼·연결 블록에 따라 참조 무효화와 인덱스 접근이 달라집니다.
정렬 키의 몇 번째 원소인지 자주 찾고 중간 삽입도 필요하면 순서 통계 트리처럼 각 노드의 subtree 크기를 저장할 수 있습니다. 왼쪽 크기 s를 보면 0-based 순위 k가 s보다 작은지, 같은지, 큰지에 따라 왼쪽·현재·오른쪽으로 이동합니다.
select(node,k):
require 0 <= k < subtreeSize(node)
while node exists:
leftSize = subtreeSize(node.left)
if k < leftSize: node = node.left
else if k == leftSize: return node
else:
k -= leftSize + 1
node = node.right
트리 높이가 O(log n)으로 유지되면 순위 조회도 O(log n)입니다. 삽입·삭제·회전마다 subtree 크기를 함께 고쳐야 합니다. deque의 단순한 양끝 연산보다 노드·회전·간접 접근 비용이 추가됩니다. 정렬 키 순위와 편집 목록의 임의 위치 순서를 같은 의미로 사용하지 않습니다.
참조 수명과 링크 변경의 원자성
배열의 재할당이 일어나면 논리 인덱스 3의 네 번째 원소는 그대로여도, 이전 버퍼를 가리키던 포인터·iterator는 무효가 될 수 있습니다. 리스트에서 노드를 삭제하면 그 노드를 가리키던 참조가 무효가 되며, 다른 노드의 주소가 유지된다는 사실만으로 모든 반복자의 안전을 보장하지 않습니다. 어떤 변경 뒤 참조를 계속 써도 되는지는 언어 라이브러리의 구체 계약을 확인해야 합니다.
이중 리스트에서 X를 A와 B 사이에 넣을 때 A.next만 먼저 X로 바꾸고 X.prev나 B.prev 갱신 전에 실패하면 정방향과 역방향 연결이 서로 다른 상태를 가리킬 수 있습니다. 필요한 노드와 자원을 먼저 준비한 뒤 링크 변경을 한 경계로 공개하고, 동시 독자에게 중간 상태가 보이지 않게 잠금이나 적절한 불변 구조를 사용합니다.
자료구조별 작업 부하와 지연 비교
인덱스로 삽입 위치를 받는 부하, 핸들을 이미 가진 커서 주변 편집, 전체 순회, 임의 키 검색을 따로 시험합니다. 자료구조 하나의 미세 연산만 비교하면 실제 비율을 놓칩니다. 빈 목록·앞·뒤·중간 삭제와 반복자 수명, 메모리 피크·할당 수·최대 지연을 함께 기록합니다.
작은 값의 연속 순회가 많다면 이동 비용이 있어도 배열이 유리할 수 있습니다. 알려진 노드 주변 편집이 많다면 리스트가 자연스러울 수 있습니다. 선택은 “삽입이 많다”가 아니라 어떻게 위치를 얻고 어떤 데이터를 다시 읽는가에서 시작합니다.