벡터(Vector)

자료구조 특징

동적으로 요소를 할당할 수 있는 동적 배열(Dynamic Array)이다. 컴파일 시점에 개수를 모른다면 벡터를 써야 한다.

배열은 크기가 고정되어있어 마지막 요소 뒤에 새로운 요소를 추가하고자 할 땐 기존 배열의 크기보다 큰 배열을 생성한 뒤 모든 요소를 복사하고 그 뒤에 새로운 요소를 추가해야 한다. 이 때 \(O(N)\)의 시간복잡도를 갖는다.

하지만 벡터의 경우 평균적으로  \(O(1)\)의 시간복잡도를 갖는다. 이부분은 밑에서 자세히 알아보도록 하자.

시간복잡도

접근(검색)	탐색	삽입(맨 뒤 삽입)	삭제(맨 뒤 삭제)
\(O(1)\)	\(O(N)\)	\(O(N)\)(\(O(1)\))	\(O(N)\)(\(O(1)\))

벡터의 크기 증가

벡터에 요소를 추가할 때, 현재 크기(size)가 내부 용량(capacity)을 초과하면 크기가 자동으로 증가한다. 

이 과정에서 내부적으로 배열의 복사과정을 거치고 이 때, \(O(N)\)의 시간복잡도가 발생한다.

하지만 평균 시간복잡도를 계산해본다면 맨 뒤에 삽입하는 과정은 상수 시간에 가까운 시간복잡도 즉, O(1)을 가진다.

 

자바에서는 일반적으로 현재 크기가 용량의 75%이상이 되는 경우 capacity를 2배로 증가시킨다. 

자바에서의 벡터 활용

앞서 설명했다시피 벡터 자료구조는 동적으로 요소를 할당하기 위한 목적으로 사용한다고 했다. 그러나, 자바에서는 같은 목적이라면 벡터보다 ArrayList를 더 많이 사용한다. 그렇다면 이 둘의 차이점은 무엇이고 벡터는 언제 사용할까?

 

ArrayList와 Vector의 차이점은 동기화 기능 유무에 있다. 동기화란 간단히 말해서 멀티 스레드 환경에서 하나의 공유자원을 여러 스레드가 동시에 접근하지 못하도록 하는 것이다.

 

ArrayList는 동기화 기능이 없어 thread-safe하지 못한 자료구조이며, Vector는 thread-safe한 자료구조로 멀티 스레드 환경에서 안전하게 사용할 수 있다.(단, 동기화 시 성능이 떨어진다는 단점이 있다.)

 

따라서 멀티 스레드 환경이라면 Vector를, 단일 스레드 환경이라면 ArrayList를 사용하는 게 적절하다고 할 수 있다.

하지만 java 5 이후부터 동기화를 위한 다양한 컬렉션 프레임워크들이 제공되고 있기 때문에 멀티 스레드 환경에서도 ArrayList를 사용하는 경우가 많아졌다고 한다.

 

의문점

잠깐? 배열에서 마지막 요소를 추가할 때도 결과적으로 배열 복사를 사용해서 \(O(N)\)의 시간복잡도를 갖는다고 했는데 그러면 배열을 쓰나 벡터를 쓰나 똑같은 거 아닌가?

 

따지고 보면 그렇다. 벡터도 내부적으론 배열로 구현이 되어있는 것이다. 하지만 사용하는 입장에서 동적 크기 조절과 자동 크기 증가 로직을 직접 짜지 않아도 되기 때문에 사용할 이유가 충분히 있다.

 

 

공식문서

Vector (Java SE 17 & JDK 17)