# Array list

## General information

Abstract Data Structure: Ordered sequence

Implementation Invariant:

1. There is a fixed number $N$.
2. An object contains a linked list whose keys are pairs consisting of an array $A$, whose index range is $1,\ldots,N$and whose component type is $\mathcal{K}$, and a natural number $n$.
3. For an array list item:
1. The components $A[1|,\ldots,A[n]$ are the elements of the ordered sequence that are stored in this item (in this order).
2. The components $A[n+1|,\ldots,A[N]$ are void.

## Remark

1. If $N$ is sufficiently large and the $n$'s are not too far from $N$ , the space consumption is significantly reduced compared to a linked list,because there is only one next pointer per array, not per element.
3. If $N$ is chosen such that the size of an array list item fits perfectly into one page of the background device, the number of accesses to the background device may be significantly reduced.