Sequence Interface

Maintain a sequence of items $X = \{x_0, x_1, …, x_{n-1} \}$ subject to these operations*:

Function Description Dynamic Array Linked List
initialize(X, initial_size) build a DS for items in $X$ ✅ ✅ (empty initializer)
set_at(i, k) set $x_i$ to $k$ ✅ ✅
get_at(i) return $x_i$ ✅ ✅
len() return $n$ ✅ ✅
iter_seq() output $x_0, x_1, …, x_{n-1}$ in sequence order ✅
insert_at(i, k) make $k$ the new $x_i$ ✅ ✅
delete_first() ✅
delete_last() ✅
delete_at(i) ✅

*Some operations may vary slightly depending on the specific data-structure implementing this interface.

Dynamic Array

Linked List