Java Collection - Vector, ArrayList, LinkedList의 비교

Collection

• Collection interface는 "내부에 포함되는 요소는 순서를 가진다"라는 특징을 가지고 있다. (Collection에 속하는 애들은 List, Set, Queue등이다) 이와 반대로 포함요소가 순서에 관계없이 저장되는 녀석이 Map 계열이다. 

 

Vector

• Vector는 Java 1.0때 만들어져 지금까지 유지되어온 클래스이다. (1.0 때에는 지금과 같은 List계열이 없었다) 기본적으로는 ArrayList와 동일하다. 
• ArrayList와의 가장 큰 차이점은 synchronized 되었다는 차이이다. Vector는 thread safe를 위해서 내부 메소드들에 synchronized를 구현하였기 때문에 ArrayList에 비해 성능이 떨어진다. 
• 요즘은 Vector를 거의 사용하지 않는데 만일 thread safe가 필요하다면 필요한 부분에만 직접 구현을 한다든지 아니면 SynchronizedList나 Map을 사용하는 것이 성능상 바람직하다. 
• 사소한 차이로는 Vector는 내부 배열을 resize할 때 두배씩 커지는 데 비해 ArrayList는 50%씩 커진다.

ArrayList

• ArrayList는 내부적인 자료구조로 배열(array)를 가지고 있다. 따라서 임의의 위치에 데이터를 추가하거나 삭제한다면 임시배열을 작성 후 데이터를 복사하는 방법을 사용한다. 

• 따라서 잦은 추가 및 삭제, 특히 임의의 위치에 해당되는 원소에 대한 작업들은 성능 저하를 가져온다. 
• 또 생성시점에 적절한 크기의 공간을 확보하지 않고 계속해서 원소를 추가하면 resize에 의한 성능 저하도 있다.
• 대신 ArrayList는 임의의 원소에 대한 read가 빠르다. 따라서 많은 데이터를 한번에 가져와서 여러 번 access할 때에 적합한 자료구조이다. 
• 아래는 실제 Java ArrayList 구현 코드 중 일부이다.  

public class ArrayList<E> extends AbstractList<E>
           implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ...
    // 'transient' means a variable should be used in memory
    // In most cases, this keyword is used for preventing serialize and deserialize
    // on object marshalling.
    private transient Object[] elementData;
    private int size;
 
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
 
    public ArrayList() {
        this(10);
    }
 
    // Increase the size of array 50% if it is too small to save data.
    // If it is still too small, make its size double and copy elements
    // (actullay elements' references) 
    public void ensureCapacity(int minCapacity) {
        modCount++;
        int oldCapacity = elementData.length;
        if (minCapacity > oldCapacity) {
            Object oldData[] = elementData;
            int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
                newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }
 
    public int size() {
        return size;
    }
 
    public boolean isEmpty() {
        return size == 0;
    }
 
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
 
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
 
    @SuppressWarnings("unchecked") 
    E elementData(int index) {
        return (E) elementData[index];
    }
 
    public E get(int index) {
        rangeCheck(index);
 
        return elementData(index);
    }
 
    public E set(int index, E element) {
        rangeCheck(index);
 
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
 
    public boolean add(E e) {
        ensureCapacity(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
 
    public E remove(int index) {
        rangeCheck(index);
 
        modCount++;
        E oldValue = elementData(index);
 
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        elementData[--size] = null; // Let gc do its work
 
        return oldValue;
    }
 
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
...

• 라인 25의 ensureCapacity() 메소드를 보면 필요한 공간보다 배열의 크기가 작을 경우 resize하는 방식이 나온다. 일단 50% 증가를 한다음 그래도 작다면 100% 증가를 하는 방식이다. 그리고 나서 원소들을 모두 복사한다. 

LinkedList

• LinkedList는 double linked된 list를 내부 자료구조로 사용한다. 따라서 임의의 위치에 있는 원소를 삽입, 삭제하는데 효과가 좋다. 
• 다만 임의의 위치에 있는 데이터를 읽을 때 순차적으로 접근해야 하기 때문에 효과가 떨어진다. 
• 물론 ArrayList에 비해 offer(), peek(), poll()와 같은 queue기반 operation들을 추가적으로 제공한다는 점도 차이점이긴 하다.

 

성능비교