Array Lists(Vector)

●Array List(Vector)

 ▷Array의 개념을 확장한것으로, 연속된 object들을 저장

 ▷저장, 삽입, 삭제는 모두 index를 통해 이루어짐.

 ▷중간에 빈 인덱스가 있을 수 없음.

  ▶주요 명령

   ▷at(index): index에 있는 object 반환

   ▷set(index, object): index에 해당 object 할당.

   ▷insert(index): index에 해당 object 삽입

   ▷erase(index): index에 있는 object 제거.

  ▶보조 명령

   ▷size(): deque의 elements의 수를 반환

   ▷empty(): deque가 비어있으면 True, 아니면 False를 반환

 

○Array-based Array list

 ▷Size N의 Vector 사용, 공간 O(n)차지.

 ▷Array list의 크기를 나타내는 정수 n

 ▷at(i) = A[i], set(i, o) = A[i] = o -> O(1)

 ▷insert(i, e) -> O(n), 최대 이상일경우 마지막 원소

 ▷erase(e) -> O(n)

 

 ▶Growable Array-based Array List

  ▷배열이 다 찬 상태에서 insert할 경우, 크기가 더 큰 새로운 배열을 만들어 넣음.

  ▷T(n) : n까지 insert하는데 걸리는 시간 -> insert 한번 당 평균 시간: T(n)/n

  ▶Incremental Strategy (상수 c만큼 크기 늘림)

   ▷배열을 k = n/c번 대체

   ▷T(n) = O(n^2), 1회 평균 O(n)

 

  ▶Doubling Strategy (2배만큼 크기 늘림)

   ▷배열을 k = log_2(n)번 대체

   ▷T(n) = O(n), 1회 평균 O(1)