[Vector/List]17. Vector ADT

목차

1. Vector ADT

2. Application of Vector

3. Array-based Vector

 

1. Vector ADT

 Vector ADT(벡터)는 배열과 비슷하며, 여러 특징을 지니고 있습니다.

 

1) 특징

- 초기에 크기 지정을 하지 않는다.

- Vector의 element는 index에 따라서 접근되거나, 삽입/삭제 된다.

 

2) 주요 기능

- at(int i): index i에 저장되어 있는 element를 반환한다.

- set(int i, object o): index에 저장되어 있는 element를 o로 바꾼다.

- insert(int i, object o): 새로운 element o를 index i 자리에 삽입한다.

- erase(int i): index i의 위치하고 있는 element를 삭제한다.

 

3) 부가 기능

- size(): Vector의 크기를 반환한다.

- empty(): Vector의 빈 여부를 반환한다.

 

2. Application of Vector

 벡터 또한 여러 상황에서 사용됩니다.

- data를 모으는 database

- 여러 data structures의 구성 요소들

 

3. Array-based Vector

1) Array-based Implementation(배열 기반 벡터 구현)

 전체 크기가 정해져있는 array를 이용하여 벡터를 구현해보면 다음과 같습니다.

 

1-1) at(i), set(i, o)

- at(i): O(1)의 시간이 소모되며, A[i]를 반환한다.

- set(i, o): O(1)의 시간이 소모되며, A[i]자리에 element o 값을 입력한다.

 

1-2) insert(i, o)

- insert(i, o): O(n)의 시간이 소모된다.

- index i의 자리에 element o의 값을 대입한다.

- A[i], ... , A[n-1]의 값들을 한 칸씩 미루게 된다.

 

1-3) erase(i)

- erase(i): O(n)의 시간이 소모된다.

- index i의 자리에 있는 element를 제거하고, 뒤에 있는 값들을 땡겨온다.

- 삭제 후, A[i+1], ... , A[n]의 값들을 한 칸씩 앞으로 땡긴다.

 

1-4) Performance

- size, empty, at, set 함수들은 O(1)의 시간이 소요된다.

- insert과 erase는 O(n)의 시간이 소요된다.

 

 

2) Growable Array-based Vector

 배열을 기반으로 벡터를 만들 경우, 처음 지정한 배열의 최대 값 만큼의 element를 저장한 경우, 새로운 element를 받지 못하는 상황이 발생합니다. 이를 방지하기 위해, insert(o) 함수에서 array가 가득 차있다면, 더 큰 크기의 배열을 배정해주는 방법이 있습니다.

 

 이때 array의 크기를 늘려야 하는 경우, 얼마나 크기를 늘리는지에 대한 방법이 여러가지가 있습니다.

1) Incremental strategy: 일정한 상수 c만큼 배열의 크기를 늘린다.

2) Doubling strategy: 기존 array 크기의 2배에 해당하는 배열을 사용한다.

보통의 경우, 2번을 택하고는 합니다.