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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} (similar to [] operator).
• void replaceAtRank(Rank r, Object o) — Puts an object Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle o} at the specified rank Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} .
• void insertAtRank(Rank r) — Inserts an element at rank Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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)$	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)}