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( + 1);  // Increments modCount!!
         [++] = e;
         return true;
     }




     public void ensureCapacity(int minCapacity) {
         ++;
         int oldCapacity = .;
         if (minCapacity > oldCapacity) {
             Object oldData[] = ;
             int newCapacity = (oldCapacity * 3)/2 + 1;
             if (newCapacity < minCapacity)
                 newCapacity = minCapacity;
             // minCapacity is usually close to size, so this is a win:
              = Arrays.copyOf(newCapacity);
         }
     }


Posted by Picky Kang

댓글을 달아 주세요