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

  • Mutaz Rasmi Abu Sara Taibah University
  • Mohammad F. J. Klaib Taibah University
  • Masud Hasan Taibah University
Abstract views: 47 , 572-1 downloads: 33

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.

Downloads

Download data is not yet available.

Author Biographies

Mutaz Rasmi Abu Sara, Taibah University
Department of Computer Science, Taibah University, Madina Al Munawarah, Saudi Arabia
Mohammad F. J. Klaib, Taibah University
Department of Computer Science, Taibah University, Madina Al Munawarah, Saudi Arabia
Masud Hasan, Taibah University
Department of Computer Science, Taibah University, Madina Al Munawarah, Saudi Arabia

References

Coreman, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009) Introduction to Algorithms. The MIT Press, Cambridge.

Goodrich, M. T. and Tamassia, R. (2014) Algorithm Design and Applications. Wiley, U.S.

Kleinberg, J. and Tardos, E. (2005) Algorithm Design. Pearson, U.S.

Weiss, M. A. (2011) Discrete Structures and Algorithms Analysis in java. Pearson, U.S.

Goodrich, M. T. and Tamassia, R. (2001) Algorithm Design: Foundations, Analysis, and Internet Examples, Wiley, U. S.

Lambert, K. A. (2009) Fundamentals of Python: From First Programs through Data Structures. Course Technology, Boston.

Brodnik, A., Carlsson, S., Demaine, E. D., Munro, I. J., and Sedgewick, R. (1999), Resizable Arrays in Optimal Time and Space. Proceedings of the Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vancouver, BC, Canada, 11- 14 August, pp. 37-48, Springer, Berlin, Heidelberg.

Goodrich, M. and Kloss, J. (1999) Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences, Proceedings of the Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol. 1663, Vancouver, BC, Canada, 11-14 August, pp 205-216, Springer, Berlin, Heidelberg

Sitarski, E. (1996), HATs: Hashed Array Trees., Dr. Dobb's Journal, 21, 11.

IC_TECH_REPORT_200244 (2002) Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays, EPFL, Geneva, Switzerland.

Oracle, The source code of java.util.ArrayList class from OpenJDK 6, http://hg.openjdk.java.net/jdk6/jdk6/jdk/file/e0e25ac28560/src/share/classes/java/util/ArrayList.java, last accessed: 16 April 2019.

Sergei Danielian, C++ STL vector: definition, growth factor, member functions, https://web.archive.org/web/20150806162750/http:/www.gahcep.com/cpp-internals-stl-vector-part-1/, last accessed: 16 April 2019.

Google Groups, vector growth factor of 1.5. comp.lang.c++.moderated, https://groups.google.com/forum/#!topic/comp.lang.c++.moderated/asH_VojWKJw%5B1-25%5D, last accessed: 16 April 2019

python.org, List object implementation from python.org, http://svn.python.org/projects/python/trunk/Objects/listobject.c, last accessed: 16 April 2019.

Brais, Hadi, Dissecting the C++ STL Vector: Part 3 - Capacity & Size, https://hadibrais.wordpress.com/2013/11/15/dissecting-the-c-stl-vector-part-3-capacity/, last accessed: 16 April 2019.

GitHub, Inc. facebook/folly, https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md, last accessed: 16 April 2019.

Oracle, Javadoc on ArrayList, https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html, last accessed: 16 April 2019.

Mark C. Chu-Carroll, Gap Buffers, or, Don’t Get Tied Up With Ropes?, https://scienceblogs.com/goodmath/2009/02/18/gap-buffers-or-why-bother-with-1, last accessed: 16 April 2019.

The Buffer Gap, https://www.gnu.org/software/emacs/manual/html_node/elisp/Buffer-Gap.html, last accessed: 16 April 2019.

Published
2021-01-09
How to Cite
Abu Sara, M. R., Klaib, M. F. J., & Hasan, M. (2021). Hybrid Array List: An Efficient Dynamic Array with Linked List Structure. Indonesian Journal on Computing (Indo-JC), 5(3), 47-62. https://doi.org/10.34818/INDOJC.2020.5.3.527
Section
Computer Science