Hybrid Array List: An Efficient Dynamic Array with Linked List Structure

Abstract

In this paper, we present an efficient dynamic array, called hybrid array list (HAL), whose structure is a linked list and each node is an array. In a HAL H, each node, called a chunk, is an array of size at most 2c, where c is an initial array size determined by the user. As the elements are added or deleted in H, it grows or shrinks by the number of nodes in the linked list as well as by the sizes of the chunks. We consider the operations append, insert and delete as well as a helping operation actual position in H. These operations run in O(1), O(m+c), O(m+c) and O(m) time, respectively, in worst case, where m is the number of chunks in H. These running times are much less than the worst case running time, which is O(n), where n is the total number of elements in H, taken by these operations in linked list or array. We implement HAL and compare these operations with similar operations in array list of Java and vector of C++. Our results show that H can perform substantially better when c is about half of the total number of elements.