Java ArrayList, Vector, LinkedList 자료형 비교 (시간 복잡도 중심으로...)

Java는 기본적인 자료구조가 구현되어 있습니다. 단순한 배열 같은 ArrayList, Vector 조금 더 유연한 LinkedList. 자료구조를 사용할 땐 어떤 사용 패턴을 보이냐에 따라 자료 구조를 선택해야 한다.

다음은 각 Java의 자료 구조의 특성을 간단하게 정리.

	ArrayList	Vector	LinkedList
Thread Safe	No	Yes	No
마지막에 추가, 삭제	O(1) or O(N)*	O(1) or O(N)*	O(1)
중간에 추가, 삭제	O(N)	O(N)	O(N)
Index 접근	O(1)	O(1)	O(N)
메모리 낭비	최대 size/2	최대 size	없음

* ArrayList의 add()함수에 새로 할당할 영역이 부족하면 size*3/2+1만큼 사이즈를 변경하고 복사한다.

* Vector의 add()함수에 새로 할당할 영역이 부족하면 capacityIncrement(생성시 지정가능) 또는 2배로 사이즈를 변경하고 복사한다.

Java.util.ArrayList 에서 add()나 ensureCapicity() 를 호출하였을 때, 

만약 지금 할당된 영역이 작다면, (현재크기*3/2+1)만큼으로 새로 영역을 할당하고,

전체 복사를 하게 됩니다. 왜 (현재크기*3/2+1)인지는 생각해볼 문제이지요. Size가 커지면 Arrays.copyOf() 내부에서 복사할 부분이 커집니다. 다르게 말하면 크기가 커지면 사이즈 증가에 부담이 된다늘 말이지요.

     public boolean add(E e) {

         ensureCapacity(size + 1);  // Increments modCount!!

         elementData[size++] = e;

         return true;

     }

     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);

         }

     }