3. ArrayList 클래스

3.1 MyArrayList 메서드 분류하기

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

 

get메서드에 있는 모든 것은 상수 시간이므로, get 메서드는 상수 시간이다.

@Override
public T set(int index, T element) {
    // TODO: FILL THIS IN!
    T old = get(index);
    array[index] = element;
    return old;
}

 

set 메서드는 배열의 범위를 검사하지 않고, 인덱스가 유효하지 않으면 에외를 던지는 get 메서드를 호출한다.

get 메서드 호출을 포함한 set메서드늬 모든 것은 상수 시간이므로, set 메서드도 상수 시간이다.

 

@Override
public int indexOf(Object target) {
    // TODO: FILL THIS IN!
    for(int i=0; i<size; i++){
       if(equals(target, array[i])){
          return i;
       }
    }
    return -1;
}

 

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

 

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

 

위 함수의 실행시간은 target또는 element의 크기에 의존한다. 하지만 배열의 크기에는 의존하지 않으므로 equals는 상수시간이다.

 

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

대상 객체를 한번에 찾아서 한개의 요소만 테스트 한 후 반환 할 수도 있고, 모든 요소를 테스트 해야되는 경우도 있을 수 있다.

따라서 indexOf는 선형이다.

 

@Override
public T remove(int index) {
    // TODO: FILL THIS IN!
    T element = get(index);
    for(int i=index; i<size-1; i++){
       array[i] = array[i+1];
    }
    size--;
    return element;
}

 

상수 시간인 get 메서드를 사용하고 index부터 배열에 반복문을 실행한다. 리스트의 마지막 요소를 제거하면 반복문은 실행되지 않고 이 메서드는 상수시간이 된다. 반대로, 첫번째 요소를 제거하면 나머지 모든 요소에 접근해야 하므로 선형이 된다.

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

 

3.2 add 메서드 분류하기

@Override
public void add(int index, T element) {
    if (index < 0 || index > size) {
       throw new IndexOutOfBoundsException();
    }
    // add the element to get the resizing
    add(element);

    // shift the elements
    for (int i=size-1; i>index; i--) {
       array[i] = array[i-1];
    }
    // put the new one in the right place
    array[index] = element;
}