Java.util.List Interface(1) ArrayList

이번에는 자바에서 흔히 사용한는 컬렉션중 하나인 List를 정리하려합니다.

저는 List중에서도 거의 ArrayList만 사용을 하고 있었는데요, 최근 어쩌다 구현체를 제대로 다 모르는거 아닌가 싶은 생각이 들어서 몇가지 정리하려 합니다.

 

간단하게 List를 먼저 소개하면 다음과 같은 특징이 있습니다.

1. 인덱스를 통해서 원하는 List내부에 접근할 수 있다.

2. 중복을 허용하며, 순서가 순서가 있다.

3. 대표적인 구현체로는 ArrayList, LinkedList, Stack 등이 있다.

 

이번에 정리하려 하는 구현체는 아마 다들 매우 많이 사용하고 있을 ArrayList를 정리하려 합니다.

 

1.GET 연산

해당부분은 사실상 별다른게 없습니다. 인덱스 체크후 값을 가져오는 로직으로 되어있습니다.

 

2. ADD 연산.

먼저 간단하게 ArrayList를 생성한다음, add연산을 하는 부분을 구현했습니다.

public static void main(String[] args){
    List<String> list = new ArrayList<>();
    for(int i = 0 ; i < 10000 ; i++){
        list.add("hi"+ i);
    }
}


public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
    } else {
        if (initialCapacity != 0) {
             hrow new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }

        this.elementData = EMPTY_ELEMENTDATA;
    }
}

private static final Object[] EMPTY_ELEMENTDATA = new Object[0];

간단하게 생성자를 보면, 기본으로 생성했을경우, default new Object[0]이며, 사이드를 넣었을경우엔 해당 사이즈로 ObjectArray를 생성해줍니다. 단 음수의 경우 에러를 뱉어줍니다.

 

 

Add연산과정을 확인해보겠습니다.(불리는 순서대로 함수 나열)

public boolean add(E e) {
    ++this.modCount;
    this.add(e, this.elementData, this.size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length) {
        elementData = this.grow();
    }

    elementData[s] = e;
    this.size = s + 1;
}

private Object[] grow() {
    return this.grow(this.size + 1);
}

private Object[] grow(int minCapacity) {
    return this.elementData = Arrays.copyOf(this.elementData, this.newCapacity(minCapacity));
}


private int newCapacity(int minCapacity) {
    int oldCapacity = this.elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(10, minCapacity);
        } else if (minCapacity < 0) {
            throw new OutOfMemoryError();
        } else {
            return minCapacity;
        }
    } else {
        return newCapacity - 2147483639 <= 0 ? newCapacity : hugeCapacity(minCapacity);
    }
}

 

add를 하게 되면 add연산을 하는 도중 length를 비교하여 사이즈를 키우는 grow작업을 진행하게 됩니다.

newCapacity에 의해서 사이즈는 0 -> 10 -> 15 -> 22 -> .... 순으로 점점 증가하면서 Arrays.copyOf 동작이 돌아가게 됩니다.

 

즉 add연산이 점점 많아질수록 어마어마한 사이즈의 데이터가 Arrays.copyOf 가 동작하게 되므로 단순한 add에도 내부적으로 복잡한 연산이 추가로 일어나게 됩니다.

 

 

주로 add만 쓰긴했는데 그렇다면 remove는..?

    public boolean remove(Object o) {
        Object[] es = this.elementData;
        int size = this.size;
        int i = 0;
        if (o == null) {
            while(true) {
                if (i >= size) {
                    return false;
                }

                if (es[i] == null) {
                    break;
                }

                ++i;
            }
        } else {
            while(true) {
                if (i >= size) {
                    return false;
                }

                if (o.equals(es[i])) {
                    break;
                }

                ++i;
            }
        }

        this.fastRemove(es, i);
        return true;
    }

    private void fastRemove(Object[] es, int i) {
        ++this.modCount;
        int newSize;
        if ((newSize = this.size - 1) > i) {
            System.arraycopy(es, i + 1, es, i, newSize - i);
        }

        es[this.size = newSize] = null;
    }

내부적으로 remove하는 Object가 null인지 아닌지 체크하는 부분을 제외하고는 while을 돌면서 list의 index를 찾아내고

System.arraycopy를 사용해 해당 인덱스만 제거하여 list를 저장하게됩니다. 그리고 나서 사이즈의 마지막 값을 null로 처리하여 마무리되게됩니다.

 

빅오를 한번 정리해보면 다음과 같습니다.

GET	O(1)
INSERT	O(1), resize시 O(n)
REMOVE	O(n)

 

간단하지만, 머리속으로는 기억하지만 실제로 코드를 한번 보면서 동작방식을 확인해봤습니다.

다음에는 LinkedList구현체를 확인해볼 예정입니다.