Summary: We study a data structure \({\mathfrak L}\) referred to variously as a padded list, controlled density array or sparse table containing records \(\{R_ i\}\) each uniquely identified by a key \(\{k(R_ i)\}\). \({\mathfrak L}\) is required to support the operations Search(\({\mathfrak L},k)\), Insert(\({\mathfrak L},k)\) and Delete(\({\mathfrak L},k)\) to search, insert and delete a record with key k. To optimize Search(\({\mathfrak L},k)\), records are stored with their keys in sorted order. If the order of the keys is to be maintained under insertion, records currently in \({\mathfrak L}\) must be moved to free space. To improve the efficiency of Insert(\({\mathfrak L},k)\), records are stored in a circular buffer with ``gaps'' so that insertion necessitates moving only records up to the next gap. The array is expanded and contracted during a sequence of insertions and deletions depending upon the current number of gaps. In this paper we assess the amount of work required to insert a sequence of records.