Collections Framework (1) ArrayList, LinkedList

ArrayList

List 인터페이스를 구현하는 클래스이다. 따라서, 데이터의 저장 순서가 유지되고 데이터의 중복을 허용한다.

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ...
    transient Object[] elementData;
    ...
}​

ArrayList는 Object[] 타입의 elementData 멤버변수를 가지고 있는데, 이 변수에 데이터가 저장된다. 또한, Object 배열로 모든 객체를 담을 수 있다. 

데이터를 읽어오거나 저장하는 효율은 좋지만, 크기를 변경해야 하는 경우에는 새로운 배열을 생성하고 기존 배열에 저장된 내용을 복사해야하기 때문에 효율이 떨어지게 된다. 그렇기 때문에 처음 ArrayList 인스턴스를 생성할 때, 충분한 크기의 인스턴스를 생성하여 사용하는 것이 좋다.

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
}

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}

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

위 코드는 ArrayList에 정의되어 있는 add(int index, E element)와 remove 메서드들이다. add(E element)를 사용해 객체를 순차적으로 저장하는 경우와 객체를 마지막에 저장된 것부터 remove(int index)를 하는 경우에는 System.arraycopy()가 호출되지 않기 때문에 빠른 작업이 이루어진다. 반면에, 배열 중간에 객체를 추가하거나 삭제하는 경우에는 System.arraycopy()가 호출되며 데이터들의 위치를 변경해주어야 한다. 따라서 데이터의 양이 많으면 작업에 걸리는 시간도 길어지게 된다.

 

 

LinkedList

ArrayList와는 다르게, 자기 자신과 연결된 다음 요소에 대한 참조 값을 멤버 변수로 갖는다. 이동 방향이 단방향인 링크드 리스트의 낮은 접근성을 보완하기 위해서 더블 링크드 리스트로 구현되어 있다. 

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;
    
    // 첫번째 노드
    transient Node<E> first;
    
    // 마지막 노드
    transient Node<E> last;
    
    ...
}​

자기 자신과 연결된 다음 요소에 대한 참조값을 지니고 있기 때문에, 추가와 삭제가 용이하다. 참조 값은 새로운 요소 혹은 null로 수정해주기만 하면 되기 때문이다. 하지만 요소에 접근하기 위해서는 처음 요소부터 접근하고자 하는 요소까지 차례대로 이동해야 하기 때문에 데이터를 조회하는 데 있어 비효율적이다. 

 

비교

Collection	읽기	추가 / 삭제	비고
ArrayList	빠르다	느리다	충분한 초기 용량을 가지고 있고 순차적으로 데이터를 추가하는 경우와 순차(역순)적으로 삭제하는 경우에는 더 빠르다. (배열을 새로 생성하고 데이터를 복사하는 작업이 없고, 데이터의 재배치가 필요 없기 때문) 작업 속도를 위해 충분한 공간을 할당하게 되면 메모리를 비효율적을 사용하게 된다.
LinkedList	느리다	빠르다

 

결론

추가 / 삭제와 같은 작업이 이루어지기 전에 데이터를 보관하기 위해서는 ArrayList를 사용하고,
작업을 할 때는 LinkedList로 옮겨 진행하면 이 둘의 장점을 살려 효율적으로 작업을 할 수 있을 것이다.

 

 

참고: Java의 정석 (남궁 성 지음)