Category Archives: Computer Science

ootl::vlist – An Implemenation of the vlist data structure

Posted on by
Reply

The ootl::vlist is an implementation of a data structure called the Vlist described in the paper Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays by Phil Bagwell. The Vlist is implemented a linked list of arrays, each one twice the size of the next. When the array of the first node (or last node depending on how you want to envision it) is filled to capacity, a new node is created with twice the capacity as the previous. Since the original data isn’t moved, only 2N memory is used at any one time, no deallocation occurs, and no need for the N destruction and copy-construction operations.

Quite clearly this data structure supports efficient growth, since there are no copies, and less wasted space. However what is somewhat counterintuitive is that this data structure provides, on average, random element access with constant complexity. The key to achieving indexing with O(1) complexity the list must be traversed from the biggest node to the smallest.

One of the other important advantages of a Vlist is that memory locations remain fixed as the structure grows. This makes it a very useful data-structure when the number of elements is not known in advance.

via ootl::vlist – An Implemenation of the vlist data structure.

Advertisement