[ Java ] ArrayList, Vector, LinkedList

List Interface를 구현하는 ArrayList, Vector, LinkedList에 대해 알아보도록 하겠습니다.

 

3 자료구조에 대한 클래스 계층은 아래 그림과 같습니다. 

 

 

 

ArrayList vs Vector

Vector 는 ArrayList와 거의 동일하며, 유일한 차이점은 동기화(synchronized)입니다.

 

이로 인해 ArrayList 보다는 오버헤드가 더 있습니다.

 

그래서 대부분의 자바 프로그래머들은 ArrayList를 더 많이 사용하고,

 

동기화가 필요한 경우에는 명시적으로 동기화를 구현합니다.

 

ArrayList vs LinkedList

두 자료구조의 시간 복잡도를 살펴보겠습니다.

	ArrayList	LinkedList
get()	O(1)	O(n)
add()	O(1)	O(1) amortized
remove()	O(n)	O(n)

 

LinkedList의 get()에서 시간 복잡도가 ArrayList에 비해 느린데,

 

값끼리 서로 링크가 연결되어 있어 이를 따라가서 값을 읽어와야 하기 때문에 O(n)의 시간 복잡도를 가집니다.

 

remove()에서는 두 자료구조가 같은 시간복잡도를 가지지만

 

ArrayList는 첫 번째 값을 삭제 시, 마지막 값을 삭제하는 것보다 더 느리다는 것을 알고 있는 것이 좋습니다.

 

ArrayList는 내부적으로 배열로 이루어져 있기 때문에 첫 번째 값을 삭제하면,

 

그 뒤의 모든 값의 인덱스를 하나씩 당겨줘야 하기 때문입니다.

 

결론

 

시간 복잡도를 봐서는 ArrayList 대신 LinkedList를 굳이 사용할 이유는 없는 것 같습니다.

 

그럼, 동기화의 여부에 따라 ArrayList나 Vector를 선택하여 사용하면 됩니다.