import java.util.*;
/**
* 자료구조 8종 — 해설 주석본.
*
* 이 파일은 "이해용"이다. 필사 대조는 주석 없는 DataStructures.java 로 한다.
* 로직은 정답본과 100% 동일하며 주석만 추가되어 있다.
*
* 주석 표기 규칙
* [불변식] 이 클래스가 항상 참으로 유지하는 조건. 깨지면 그 순간이 버그다.
* [왜] 이 줄이 왜 필요한가. 지우면 무엇이 깨지는가.
* [함정] 필사할 때 실제로 자주 틀리는 지점.
* [비용] 시간/공간 복잡도.
*
* 실행: java DataStructuresAnnotated.java
*/
public class DataStructuresAnnotated {
// ════════════════════════════════════════════════════════════════
// 01. 동적 배열 (MyArrayList)
//
// 한 줄 요약: 고정 크기 배열을 "가득 차면 두 배로 갈아끼우는" 방식으로
// 무한히 커지는 것처럼 보이게 만든 것.
//
// [불변식] 0 <= size <= elements.length
// [불변식] elements[size] 부터 끝까지는 항상 null
// [비용] get O(1) / 맨뒤 add 상환 O(1) / 중간 add·remove O(n)
// ════════════════════════════════════════════════════════════════
static class MyArrayList<E> {
private static final int DEFAULT_CAPACITY = 8;
// [왜] E[] 가 아니라 Object[] 인가?
// 자바 제네릭은 실행 시점에 타입이 지워진다(type erasure).
// new E[n] 은 문법적으로 불가능하므로 Object[] 로 담고 꺼낼 때 캐스팅한다.
// java.util.ArrayList 도 내부적으로 정확히 같은 방식이다.
private Object[] elements = new Object[DEFAULT_CAPACITY];
// [함정] size 는 "담긴 개수", elements.length 는 "담을 수 있는 칸 수".
// 이 둘을 혼동하는 것이 이 클래스 버그의 90%다.
private int size;
/** 맨 뒤에 추가. [비용] 상환 O(1) */
public void add(E e) {
ensureCapacity(size + 1); // [왜] 넣기 전에 자리부터 확보
elements[size++] = e; // [왜] 현재 size 위치에 넣고 size 증가 (후위 증가)
}
/** index 위치에 끼워넣기. [비용] O(n) — 뒤쪽을 전부 한 칸씩 민다 */
public void add(int index, E e) {
// [함정] 여기만 index > size 다. checkIndex 의 >= 를 쓰면 안 된다.
// "맨 뒤에 붙이기"는 유효한 삽입이므로 index == size 를 허용해야 한다.
if (index < 0 || index > size) throw new IndexOutOfBoundsException("index=" + index);
ensureCapacity(size + 1);
// arraycopy(원본, 원본시작, 대상, 대상시작, 길이)
// [왜] index 부터 끝까지를 한 칸 오른쪽으로 민다. 겹치는 영역이지만
// System.arraycopy 는 겹침을 안전하게 처리하도록 명세되어 있다.
// 직접 for 루프로 쓴다면 반드시 뒤에서 앞으로 돌아야 한다.
System.arraycopy(elements, index, elements, index + 1, size - index);
elements[index] = e;
size++;
}
/** [비용] O(1) — 배열의 최대 장점 */
@SuppressWarnings("unchecked")
public E get(int index) {
checkIndex(index);
// [왜] @SuppressWarnings 는 "Object 를 E 로 캐스팅"이 안전함을 우리가 보장한다는 선언.
// add 로만 값이 들어오므로 실제로 E 만 담겨 있다.
return (E) elements[index];
}
/** [비용] O(n) */
@SuppressWarnings("unchecked")
public E remove(int index) {
checkIndex(index);
E old = (E) elements[index];
// [함정] 길이가 size - index 가 아니라 size - index - 1 이다.
// 지울 원소 자체는 복사 대상이 아니므로 1을 뺀다.
// -1 을 빠뜨리면 배열 끝을 넘어 ArrayIndexOutOfBoundsException.
System.arraycopy(elements, index + 1, elements, index, size - index - 1);
// [왜] 마지막 칸을 null 로 비운다. 이 줄이 없으면 지워진 객체를 배열이
// 계속 참조하고 있어서 GC가 회수하지 못한다 → 메모리 누수.
// 불변식 "elements[size] 이후는 전부 null" 을 지키는 줄이기도 하다.
elements[--size] = null;
return old;
}
public int size() { return size; }
/**
* need 개를 담을 수 있도록 용량을 보장한다.
* [비용] 확장이 일어날 때만 O(n), 두 배씩 늘리므로 상환하면 O(1)
*/
private void ensureCapacity(int need) {
// [왜] 이미 충분하면 아무 일도 하지 않는다. 이 조기 반환이 상환 O(1)의 전부다.
// [함정] <= 를 <- 로 잘못 쓰면 (need < -elements.length) 로 파싱되어
// 항상 false 가 된다. 컴파일도 되고 기능 테스트도 통과하지만
// add 마다 배열이 두 배로 재할당되어 OutOfMemoryError 로 죽는다.
if (need <= elements.length) return;
// [왜] max 가 필요한 이유: 보통은 length*2 로 충분하지만, 한 번에 수백 개를
// 추가하는 API(addAll 등)가 생기면 need 가 length*2 를 넘을 수 있다.
// [왜] 1.5배가 아니라 2배: 확장 횟수를 log n 으로 억제하기 위함.
// (참고로 java.util.ArrayList 는 1.5배를 쓴다 — 메모리 여유 우선)
int newCapacity = Math.max(need, elements.length << 1);
elements = Arrays.copyOf(elements, newCapacity);
}
/** 조회·삭제용 경계 검사. 삽입용과 구분되어야 하므로 별도 메서드다. */
private void checkIndex(int index) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException("index=" + index);
}
}
// ════════════════════════════════════════════════════════════════
// 검증 — 정답본과 동일한 테스트
// ════════════════════════════════════════════════════════════════
public static void main(String[] args) {
MyArrayList<String> list = new MyArrayList<>();
for (String s : List.of("a", "b", "c", "d")) list.add(s);
list.add(1, "x");
check(list.size() == 5 && list.get(1).equals("x"), "MyArrayList.add");
check(list.remove(1).equals("x") && list.get(1).equals("b"), "MyArrayList.remove");
}
private static void check(boolean condition, String label) {
if (!condition) throw new AssertionError("FAIL: " + label);
System.out.println("PASS " + label);
}
}
Java
복사