ArrayList 클래스

>>>>>>> 소스코드.git

MyArrayList 메서드 분류하기

다음은 MyArrayList 클래스의 get 메서드이다. (MyArrayList.java)

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

get 메서드에 있는 모든 것은 상수 시간이다. 따라서 get 메서드는 상수 시간이다. 아무 문제 없다.

 

set 메서드도 구현해보자.

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

이 해법에서 약간 똑똑한 부분은 명시적으로 배열의 범위를 검사하지 않는다는 것이다. set 메서드는 인덱스가 유효하지 않으면 예외를 던지는 get 메서드를 호출한다.

 

get 메서드 호출을 포함한 set 메서드의 모든 것은 상수 시간이다. 따라서 set 메서드도 상수 시간이다. 

 

다음으로 몇 가지 선형 메서드를 알아보자. 다음은 indexOf 메서드이다.

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

반복문을 돌 때마다 indexOf 메서드는 equals 메서드를 호출한다. 따라서 equals 메서드를 먼저 분류해야한다. 코드는 다음과 같다.

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

이 메서드는 target.equals 메서드를 호출한다. 이 메서드의 실행시간은 target 또는 element의 크기에 의존한다. 하지만 배열의 크기에 의존하지 않으므로 indexOf 메서드를 분석하기 위해 equals 메서드를 상수 시간으로 생각한다.

 

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

 

운이 좋다면 대상 객체를 단번에 찾아서 한 개의 요소만 테스트 후 반환하고, 운이 없다면 모든 요소를 테스트해야 한다. 평균적으로 요소 개수의 절반을 테스트하기를 기대한다. 따라서 indexOf 메서드는 선형이다(대상 요소가 배열의 시작에 있는 거의 일어나지 않을 경우는 제외).

 

remove 메서드의 분석도 비슷하다. 코드는 다음과 같다. 

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

상수 시간인 get 메서드를 사용하고 index부터 배열에 반복문을 실행한다. 리스트의 마지막 요소를 제거하면 반복문은 실행되지 않고 이 메서드는 상수 시간이 된다. 첫 번째 요소를 제거하면 나머지 모든 요소에 접근하여 선형이 된다. 따라서 remove 메서드는 선형으로 간주한다(요소가 배열의 끝에 있거나 끝에서 상수 거리에 있음을 아는 특수한 경우는 제외).