Array list

General information

Abstract Data Structure: Ordered sequence

Implementation Invariant:

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

Remark

Admittedly, array lists are more complicated than linked lists. However, there are three advantages:

1. If [math]\displaystyle{ N }[/math] is sufficiently large and the [math]\displaystyle{ n }[/math]'s are not too far from [math]\displaystyle{ N }[/math] , the space consumption is significantly reduced compared to a linked list,because there is only one next pointer per array, not per element.
2. If there are many insertion and removal operations, arrays instead of single list items may reduce space fragmentation.
3. If [math]\displaystyle{ N }[/math] 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.