Array list

General information

Abstract Data Structure: Linear sequence

Implementation Invariant:

   There is a fixed number .
   An object contains a linked list whose keys are pairs consisting of
       an array , whose index range is and whose component type is , and
       a natural number . 
   For an array list item:
       The components of are the elements of the ordered sequence that are stored in this item (in this order).
       The components of are void.

Remark

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

   If is sufficiently large and the 's are close to , the space consumption is significantly reduced because there is only one next pointer per array, not per element.
   If there are many insertion and removal operations, arrays instead of single list items may reduce space fragmentation.
   If 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.