동적 배열의 용량 정책
size와 용량을 분리한 MyArrayList를 만들고 가득 찬 순간 두 배 확장과 원소 복사를 확인합니다.
고정 배열 기반 목록은 남은 칸이 있는 동안 정상처럼 보입니다.
세 번째 게시글 제목이 들어오는 순간 내부 배열 예외가 나오면 호출자는 자료 구조의 정책을 알 수 없습니다.
동적 구현은 요구 크기, 현재 size, 현재 용량을 매 삽입 직전에 비교해 확장 시점을 명확히 만듭니다.
세 번째 add 전 용량 확인 누락
두 칸 배열에 세 번째 제목을 추가합니다.
예외는 호출 코드가 아니라 내부의 값[size]에서 발생합니다.
이 오류를 그대로 노출하면 “목록은 추가할 수 있다”는 추상화가 깨집니다.
public final class FixedCapacityOverflowFailure {
public static void main(String[] args) {
String[] values = new String[2];
int size = 0;
values[size++] = "array";
values[size++] = "list";
values[size++] = "growth";
}
}java.lang.ArrayIndexOutOfBoundsException삽입 전에 필요한 용량인 size + 1을 계산하지 않았습니다.
확장 정책은 새 용량이 필요 용량 이상임을 보장해야 하며, 길이가 0인 배열도 증가할 수 있도록 최소 용량을 정해야 합니다.
필요 용량과 두 배 성장 규칙
add는 저장 전에 필요 용량을 계산하고 부족할 때만 배열을 교체합니다.- 새 길이는 현재 길이의 두 배와 요구 길이 중 큰 값으로 정해 한 번에 충분히 확보합니다.
System.arraycopy는 사용 구간만 복사하며 비어 있는 용량 영역은 옮길 필요가 없습니다.- 확장 한 번은 O(n)이지만 여러 끝 삽입에 나누어 보면 평균 비용은 상수에 가까워집니다.
size는 성공적으로 값을 쓴 뒤 증가시켜 복사 실패 중간 상태가 외부에 보이지 않게 합니다.- 초기 용량은 예상 데이터 크기와 낭비 메모리 사이의 선택값이며 정답 하나가 아닙니다.
복사 뒤 배열을 교체하는 MyArrayList
DynamicTitleList는 길이 0에서도 시작할 수 있고 필수보다 작은 배열을 만들지 않습니다.
제네릭 배열을 직접 만들 수 없으므로 Object[]를 저장 지점으로 쓰고 get 한 곳에서만 검사된 캐스팅을 수행합니다.
import java.util.Arrays;
public final class DynamicTitleList {
public static void main(String[] args) {
MyArrayList<String> list = new MyArrayList<>(1);
list.add("array");
list.add("growth");
list.add("copy");
System.out.println(list);
System.out.println("size=" + list.size() + ", capacity=" + list.capacity());
}
private static final class MyArrayList<E> {
private Object[] values;
private int size;
MyArrayList(int initialCapacity) {
if (initialCapacity < 0) throw new IllegalArgumentException("capacity");
values = new Object[initialCapacity];
}
void add(E value) {
ensureCapacity(size + 1);
values[size++] = value;
}
@SuppressWarnings("unchecked")
E get(int index) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException(index);
return (E) values[index];
}
private void ensureCapacity(int required) {
if (required <= values.length) return;
int doubled = values.length == 0 ? 1 : values.length * 2;
values = Arrays.copyOf(values, Math.max(doubled, required));
}
int size() {
return size;
}
int capacity() {
return values.length;
}
public String toString() {
return Arrays.toString(Arrays.copyOf(values, size));
}
}
}성장 정책을 수열로 확인
초기 용량이 1이고 두 배 전략을 쓰면 세 번째 삽입까지 용량은 1, 2, 4로 변합니다.
네 번째는 남은 칸을 사용하고 다섯 번째에서 8로 확장됩니다.
확장은 모든 add에서 일어나는 일이 아니라 특정 접점에서만 발생합니다.
그래서 한 번의 비싼 복사와 장기간의 값싼 끝 추가를 함께 계산해야 합니다.
초기 길이가 0이면 단순한 length * 2도 계속 0입니다.
최소값 1과 필요 용량을 함께 비교해야 첫 삽입이 가능합니다.
또한 필요 용량이 두 배보다 큰 대량 추가 API를 생각한다면 Math.max(doubled, required)가 필요합니다.
상환 분석과 평균 실행 시간의 차이
n개의 원소를 넣는 동안 복사되는 원소 수는 1, 2, 4처럼 기하급수로 늘고 그 합은 최종 크기의 일정 배수 안에 머뭅니다.
이 때문에 끝 추가의 상환 비용을 O(1)이라고 설명합니다.
특정 확장 add가 O(n)이라는 사실은 그대로이며 지연 시간 상한이 중요한 시스템에서는 별도 대책이 필요합니다.
실시간 응답이 중요하면 예상 최대치에 가까운 초기 용량을 주거나, 입력을 청크로 나누거나, 확장 시점을 요청 바깥으로 옮기는 선택을 검토합니다.
메모리 낭비를 줄이는 것과 복사 횟수를 줄이는 것은 서로 반대 방향의 목표입니다.
복사 범위와 상태 갱신 순서
새 배열에는 용량 전체가 아니라 논리 원소 0..size-1만 복사하면 됩니다.
참조 배열의 빈 칸은 null로 초기화됩니다.
새 배열 생성과 복사가 성공한 뒤 값 필드를 교체하고, 실제 값을 저장한 다음 size를 증가시키면 예외가 난 중간 상태를 관찰하기 어렵습니다.
저장량이 늘어나는 게시글
게시글 저장소에 기록 수 상한을 두지 않으려면 저장소가 스스로 확장해야 합니다.
CLI는 두 개의 입력으로 시작하지만 이후 같은 add 규칙을 유지합니다.
초기 용량은 외부 기능이 아니라 성능 힌트입니다.
public final class PostRepositoryCliCH142 {
public static void main(String[] args) {
PostRepository repository = new PostRepository();
repository.add("capacity", 30);
repository.add("array-copy", 50);
repository.print();
System.out.println("total=" + repository.totalViewCount());
}
private static final class PostRepository {
private Entry[] entries = new Entry[2];
private int size;
void add(String title, int viewCount) {
if (title == null || title.isBlank()) throw new IllegalArgumentException("title");
if (viewCount <= 0) throw new IllegalArgumentException("viewCount");
ensureCapacity(size + 1);
entries[size++] = new Entry(title, viewCount);
}
private void ensureCapacity(int required) {
if (required <= entries.length) return;
Entry[] grown = new Entry[Math.max(required, entries.length * 2)];
System.arraycopy(entries, 0, grown, 0, size);
entries = grown;
}
int totalViewCount() {
int total = 0;
for (int i = 0; i < size; i++) {
total += entries[i].viewCount();
}
return total;
}
void print() {
for (int i = 0; i < size; i++) {
Entry entry = entries[i];
System.out.println(i + ":" + entry.title() + "=" + entry.viewCount());
}
}
}
private record Entry(String title, int viewCount) {}
}이 단계의 CLI는 초기 두 칸만 사용하지만 세 번째 명령을 추가해도 같은 add 경로가 확장하도록 설계되었습니다.
확인할 값은 용량 자체가 아니라 기존 두 Entry가 복사 후에도 같은 순서와 조회수를 유지하는지입니다.
성장 정책은 기능 출력에 나타나지 않는 내부 성능 결정입니다.
초기 용량과 성장 배수 결정
| 질문 | 관찰할 값 | 선택 또는 조치 |
|---|---|---|
| 증가 폭이 예측 가능한가 | 최종 size | 초기 용량 지정 |
| 끝 추가가 주 연산인가 | 확장 횟수 | 배수 성장 사용 |
| 메모리 여유가 작은가 | 미사용 슬롯 | 성장 배수 조정 |
| 대량 복사가 부담인가 | 복사 시간 | 청크 또는 연결 구조 검토 |
매번 한 칸씩 늘리면 n개 삽입에 복사량이 누적되어 제곱 비용이 됩니다.
배수 성장은 빈 슬롯을 조금 남기는 대신 복사 횟수를 크게 줄입니다.
실제 초기 용량은 예상 크기 분포를 측정한 뒤 정합니다.
연습 문제
초기 용량 1에서 원소 10개를 끝에 추가한다고 가정합니다.
확장이 일어난 횟수와 마지막 용량을 출력하는 작은 시뮬레이터를 작성하세요.
정답과 해설
삽입 직전 필수가 용량을 넘을 때만 두 배로 늘립니다.
원소를 실제로 저장하지 않아도 size와 용량 전이만으로 성장 비용을 확인할 수 있습니다.
public final class CapacityGrowthTraceSolution {
public static void main(String[] args) {
int size = 0;
int capacity = 1;
int growths = 0;
while (size < 10) {
int required = size + 1;
if (required > capacity) {
capacity = Math.max(required, capacity * 2);
growths++;
}
size++;
}
System.out.println("growths=" + growths + ", capacity=" + capacity);
}
}2, 4, 8, 16으로 네 번 커지므로 결과는 growths=4, capacity=16입니다.
마지막 size 10과 용량 16의 차이는 다음 삽입을 싸게 만들기 위해 미리 지불한 여유입니다.
동적 배열 완성 기준
빈 배열에서도 첫 add가 성공해야 하고, 확장 직후 이전 원소의 순서가 보존되어야 합니다.
용량은 절대로 size보다 작을 수 없습니다.
한 칸 성장과 배수 성장의 누적 복사량을 비교해 설명할 수 있다면 상환 비용까지 이해한 것입니다.