동적 배열은 크기를 유연하게 조절할 수 있어야 하며, 기본적으로 배열 기반의 자료구조로 구현된다. 이 문서에서는 자바에서 자체적으로 동적 배열을 구현하는 과정을 단계별로 설명한다. 주요 기능으로는 요소 추가, 삭제, 조회, 인덱스 기반 수정, 크기 조절 등이 포함된다.

필수 메서드 목록

int size();               // 현재 요소 개수 반환
boolean isEmpty();         // 비어있는지 여부 확인
boolean contains(E element); // 특정 요소 존재 여부 확인
void add(E element);       // 마지막 위치에 요소 추가
E get(int index);          // 지정 인덱스의 요소 가져오기
E set(int index, E element); // 지정 인덱스의 요소 교체
void add(int index, E element); // 지정 위치에 요소 삽입
E remove(int index);       // 지정 위치의 요소 제거 및 반환
int indexOf(E element);    // 요소의 첫 번째 인덱스 찾기
void clear();              // 모든 요소 제거
    

1. 기본 구성 요소 정의

동적 배열은 내부에 저장용 배열과 요소 수를 추적하는 필드가 필요하다.

public class DynamicArray<E> {
    private E[] data;
    private int elementCount;
    private static final int DEFAULT_CAPACITY = 10;

    public DynamicArray() {
        this(DEFAULT_CAPACITY);
    }

    public DynamicArray(int initialCapacity) {
        data = (E[]) new Object[initialCapacity];
    }
}
    

2. 간단한 메서드 구현

public int size() {
    return elementCount;
}

public boolean isEmpty() {
    return elementCount == 0;
}

public boolean contains(E item) {
    for (int i = 0; i < elementCount; i++) {
        if (data[i] != null && data[i].equals(item)) {
            return true;
        }
    }
    return false;
}

public void clear() {
    for (int i = 0; i < elementCount; i++) {
        data[i] = null;
    }
    elementCount = 0;
}
    

3. 인덱스 기반 요소 접근

인덱스 범위 검사 후 요소 반환.

public E get(int index) {
    validateIndex(index);
    return data[index];
}

private void validateIndex(int index) {
    if (index < 0 || index >= elementCount) {
        throw new IndexOutOfBoundsException("Invalid index: " + index);
    }
}
    

4. 요소 제거 로직

지정된 위치의 요소를 제거하고, 뒤쪽 요소들을 왼쪽으로 이동시킨다.

public E remove(int index) {
    validateIndex(index);
    E removedValue = data[index];

    for (int i = index; i < elementCount - 1; i++) {
        data[i] = data[i + 1];
    }
    data[--elementCount] = null;
    return removedValue;
}
    

5. 요소 값 변경

public E set(int index, E newValue) {
    validateIndex(index);
    E oldValue = data[index];
    data[index] = newValue;
    return oldValue;
}
    

6. 요소 위치 탐색

private static final int NOT_FOUND = -1;

public int indexOf(E item) {
    for (int i = 0; i < elementCount; i++) {
        if (data[i] != null && data[i].equals(item)) {
            return i;
        }
    }
    return NOT_FOUND;
}
    

7. 특정 위치에 요소 삽입

삽입 전에 유효성 검사를 수행하고, 데이터 이동을 통해 공간 확보.

public void add(int index, E item) {
    validateInsertIndex(index);
    ensureCapacity(elementCount + 1);

    for (int i = elementCount; i > index; i--) {
        data[i] = data[i - 1];
    }
    data[index] = item;
    elementCount++;
}

private void validateInsertIndex(int index) {
    if (index < 0 || index > elementCount) {
        throw new IndexOutOfBoundsException("Insertion index out of bounds: " + index);
    }
}
    

8. 배열 용량 증가 로직

기존 용량의 1.5배로 확장하여 성능 최적화.

private void ensureCapacity(int minCapacity) {
    int currentCapacity = data.length;
    if (currentCapacity >= minCapacity) return;

    int newCapacity = currentCapacity + (currentCapacity >> 1);
    E[] newData = (E[]) new Object[newCapacity];

    System.arraycopy(data, 0, newData, 0, elementCount);
    data = newData;
}
    

9. 기본 요소 추가 메서드

public void add(E item) {
    add(elementCount, item);
}
    

10. 테스트 코드 예시

public static void main(String[] args) {
    DynamicArray<Integer> list = new DynamicArray<>();

    list.add(100);
    list.add(200);
    list.add(300);

    System.out.println(list); // [100, 200, 300]

    list.set(1, 999);
    System.out.println(list); // [100, 999, 300]

    System.out.println("Contains 300: " + list.contains(300)); // true

    list.add(1, 555);
    System.out.println(list); // [100, 555, 999, 300]

    System.out.println("Index of 999: " + list.indexOf(999)); // 2

    list.clear();
    System.out.println(list); // []
}