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.