자료구조 ] Vector, ArrayList, LinkedList 의 차이 정리

Vector와 ArrayList 그리고 LinkedList 각각의 개념 및 사용방법은 다음에 다룰 것이다. 이것을 제외한 차이에 대해서만 정리하겠다.

 

중요!

아래에 내용을 이해하려면 동기화에 대한 개념을 알아야하고, CS지식 중 프로세스와 스레드에대한 개념도 알아햐한다.

 

Vector

 - 동기화를 보장한다. 그래서 하나의 스레드가 하나의 자원을 이용하기 때문에 성능 저하가 발생한다.

 - 공간을 추가하는 경우 공간의 2배만큼 확보하기 때문에 메모리를 많이 확보한다.

 

ArrayList

 - 동기화를 보장하지 않는다. 그래서 명시적으로 필요한 경우 동기화를 해야한다.

   (명시적으로 동기화하는 경우 java에서 synchronized() 함수를 사용)

 - 동기화를 하지 않기 때문에 Vector보다 빠르다.

 - 메모리를 필요한 만큼만 확보한다.

 - 인덱스를 가지고 있어서 검색에 용이하다.

 - 삽입/삭제를 하는 경우 전체에서 한칸씩 밀거나 당겨야하기 때문에 빈번한 데이터인 경우 부적합하다.

 - get, append의 시간복잡도는 O(1)이다.

 

LinkedList

 - ArrayList가 한 덩어리의 큰 배열을 사용하는 방식이라면, LinkedList는 데이터가 노드로 구성되어 양방향 연결되는 구조이다.

 - get함수를 이용해서 필요한 인덱스의 값을 접근하는 경우 처음부터 끝가지 노드를 타고 이동해야하기 때문에 검색에는 적합하지 않다.

 - get, append의 시간복잡도는 O(N)이다.

 

결론.

 ① Vector의 단점을 보완하는 클래스가 ArrayList이고 Vector의 단점인 동기화는 ArrayList를 사용하면서 필요한

    시점에만 명시적으로 사용해주면 효율적이다. 왜냐하면 동기화를 남발하는 경우 성능 저하가 발생하기 때문이다.

 ② 삽입/삭제를 빈번하게 사용하는 경우엔 LinkedList를 사용하면 된다.

 ③ 검색을 주로 사용하는 경우에는 ArrayList를 사용하면 된다.