Vector (ADT)

A vector is the simplest indexed data type. It is essentially an abstraction of an array.

Functions

• int size() — Returns how many items are in the vector.
• bool isEmpty() — Returns whether the vector is empty (i.e. size is 0).
• Object elemAtRank(Rank r) — Returns the element stored at rank $r$ (similar to [] operator).
• void replaceAtRank(Rank r, Object o) — Puts an object $o$ at the specified rank $r$.
• void insertAtRank(Rank r) — Inserts an element at rank $r$ and shifts all following items down a rank.
• void removeAtRank(Rank r) — Removes an element from rank $r$ and shifts all following items up a rank to fill in the gap.

Implementations

Array-based

• Use an array of actual size $N$, but keep track of true size with an auxiliary variable $n$
• Fixed or growable does not affect the speed

Analysis

	best	average	worst
elemAtRank	$O(1)$
replaceAtRank	$O(1)$	$O(n)$
insertAtRank	$O(1)$	$O(n)$
removeAtRank	$O(1)$	$O(n)$