[Think Data Structures] Java ArrayList 클래스 구현 및 분석

MyArrayList 구현 및 분석

---

Java List 인터페이스를 구현한 MyArrayList<E>를 작성

public class MyArrayList<E> implements List<E> {
    ...
}

get 메서드 구현

@Override
public E get(int index) {
    if(index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    return array[index];
}

=> get 메서드에 있는 모든 것은 상수 시간

set 메서드 구현

@Override
public E set(int index, E element) {
    E old = get(index);
    array[index] = element;
    return old;
}

set메서드에서 명시적으로 배열의 범위를 검사하지 않는다. (set 메서드는 인덱스가 유효하지 않으면 예외를 던지는 get 메서드를 호출하기 때문)

=> get 메서드 호출을 포함한 set 메서드의 모든 것은 상수 시간

----------------------- 선형 메서드 알아보기 -----------------------

indexOf 메서드 구현

@Override
public int indexOf(Object o) {
    for(int i=0; i<size; i++){
        if(equals(o, array[i])){
            return i;
        }
    }
    return -1;
}

private boolean equals(Object target, Object element){
    if(target == null){
        return element == null;
    }else{
        return target.equals(element);
    }
}

반복문을 돌 때마다 indexOf 메서드는 equals 메서드를 호출한다.

따라서 equals 메서드를 먼저 분류해야 하는데, equals 메서드는 target 또는 element의 크기에 의존한다. 하지만 배열의 크기에는 의존하지 않으므로, indexOf 메서드를 분석하기 위해 equals 메서드를 상수시간으로 생각하면된다.

다시 indexOf 메서드에서 반복문안에 있는 모든 것은 상수시간 이므로, 반복문이 몇 번 실행됬는지를 생각해 봐야 한다.

운이 좋다면, 1번 실행되겠지만 운이 없다면 모든 요소를 테스트를 해야 한다. 평균적으로 요소 개수의 절반을 테스트하기를 기대하기 때문에 indexOf 메서드는 선형이라고 할 수 있다.

remove 메서드 구현

@Override
public E remove(int index) {
    E element = get(index);
    for(int i = index; i<size-1; i++){
        array[i] = array[i+1];
    }
    size--;
    return element;
}

remove 메서드도 indexOf 메서드와 비슷한데, 상수 시간인 get메서드를 사용하고 index부터 배열에 반복문을 실행하게 된다.

리스트의 마지막 요소를 제거하면 반복문은 실행되지 않고 상수시간이 되지만, 첫 번째 요소를 제거하면 나머지 모든 요소에 접근하여 선형이 된다.

따라서 remove 메서드는 선형으로 간주한다.

add 메서드 구현

@Override
public void add(int index, E element) {
    if(index <0 || index > size){
        throw new IndexOutOfBoundsException();
    }
    // 크기 조정을 통해 요소 추가
    add(element);
    // 다른 요소를 시프트
    for(int i = size-1; i>index; i--){
        array[i] = array[i-1];
    }
    // 올바른 자리에 새로운 값을 넣습니다.
    array[index] = element;
}

add 메서드를 호출하면 단일인자 add 메서드를 호출 한후, 다른 요소를 오른쪽으로 이동시키고 올바른 자리에 새로운 요소를 넣게된다.

따라서 add(int, E)메서드를 분류하려면 먼저 add(E) 메서드를 분류해야 한다.

@Override
public boolean add(E e) {
    if(size >= array.length) {
        E[] bigger = (E[]) new Object[array.length * 2];
        System.arraycopy(array, 0, bigger, 0, array.length);
        array = bigger;
    }
    array[size] = e;
    size++;
    return true;
}

배열에 미사용 공간이 있다면 add 메서드는 상수 시간을 갖게된다.

하지만 배열의 크기를 변경하면 System.arraycopy 메서드 호출이 되고 실행시간이 배열의 크기에 비례하기 때문에 add 메서드는 선형시간을 갖게된다.

=> 일련의 n개 요소를 추가할 때의 평균 연산 횟수를 고려하여 메서드를 분류

n번 추가하면 요소 n개를 저장하고 n-2개를 복사해야 하기 때문에 총 연산 횟수는 2n-2가 나온다.

평균 연산 횟수를 구하려면 합을 n으로 나눠야하기 때문에 (2n-2)/n = 2-2/n 이 나오게 되는데, n이 커지면 두번째 항인 2/n이 작아지기 때문에 add(E)는 상수시간이라고 볼 수 있다.

선형인 알고리즘이 평균적으로 상수시간이 된다는 것이 어색해 보일 수 있는데, 핵심은 배열의 크기를 조정할 때마다 배열의 길이가 2배로 는다는 것이다. 이것으로 각 요소를 복사하는 횟수를 제한하게 된다.

일련의 호출에서 평균 시간을 계산하는 알고리즘 분류 방법을 분할 상환 분석(amortized analysis)라고 한다. (일련의 호출을 하는 동안 배열을 복사하는 추가 비용이 분산되거나 분할 상환되었다는 것임)

add(int, E)는 add(E)가 상수시간이고, 반복문은 리스트의 끝에 요소를 추가하는 특별한 경우만 제외하면 선형이기 때문에 선형시간을 갖게된다.

※나머지 구현은 https://github.com/ksh901016/thinkDataStructure/ 에서 확인