|
!Implementation
!Growth factor (''a'')
|-
|Java ArrayList<ref name="java_util_ArrayList" />
|1.5 (3/2)
|-
|[[Python (programming language)|Python]] PyListObject<ref>[https://github.com/python/cpython/blob/bace59d8b8e38f5c779ff6296ebdc0527f6db14a/Objects/listobject.c#L58 List object implementation] from github.com/python/cpython/, retrieved 2020-03-23.</ref>
|~1.125 (n + n >> 3)
|-
|[[Microsoft Visual C++]] 2013<ref>{{Cite web|title = Dissecting the C++ STL Vector: Part 3 - Capacity & Size|url = https://hadibrais.wordpress.com/2013/11/15/dissecting-the-c-stl-vector-part-3-capacity/|website = Micromysteries|access-date = 2015-08-05|first = Hadi|last = Brais}}</ref>
|1.5 (3/2)
|-
|[[G++]] 5.2.0<ref name=":0" />
|2
|-
|[[Clang]] 3.6<ref name=":0" />
|2
|-
|Facebook folly/FBVector<ref>{{Cite web|title = facebook/folly|url = https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md|website = GitHub|access-date = 2015-08-05}}</ref>
|2
|}
== Performance ==
{{List data structure comparison}}
The dynamic array has performance similar to an array, with the addition of new operations to add and remove elements:
* Getting or setting the value at a particular index (constant time)
* Iterating over the elements in order (linear time, good cache performance)
* Inserting or deleting an element in the middle of the array (linear time)
* Inserting or deleting an element at the end of the array (constant amortized time)
Dynamic arrays benefit from many of the advantages of arrays, including good [[locality of reference]] and [[data cache]] utilization, compactness (low memory use), and [[random access]]. They usually have only a small fixed additional overhead for storing information about the size and capacity. This makes dynamic arrays an attractive tool for building [[Cache (computing)|cache]]-friendly [[Data structure|data structures]]. However, in languages like Python or Java that enforce reference semantics, the dynamic array generally will not store the actual data, but rather it will store [[Reference (computer science)|references]] to the data that resides in other areas of memory. In this case, accessing items in the array sequentially will actually involve accessing multiple non-contiguous areas of memory, so the many advantages of the cache-friendliness of this data structure are lost.
Compared to [[linked list]]s, dynamic arrays have faster indexing (constant time versus linear time) and typically faster iteration due to improved locality of reference; however, dynamic arrays require linear time to insert or delete at an arbitrary ___location, since all following elements must be moved, while linked lists can do this in constant time. This disadvantage is mitigated by the [[gap buffer]] and ''tiered vector'' variants discussed under ''Variants'' below. Also, in a highly [[Fragmentation (computer)|fragmented]] memory region, it may be expensive or impossible to find contiguous space for a large dynamic array, whereas linked lists do not require the whole data structure to be stored contiguously.
A [[Self-balancing binary search tree|balanced tree]] can store a list while providing all operations of both dynamic arrays and linked lists reasonably efficiently, but both insertion at the end and iteration over the list are slower than for a dynamic array, in theory and in practice, due to non-contiguous storage and tree traversal/manipulation overhead.
== Variants ==
[[Gap buffer]]s are similar to dynamic arrays but allow efficient insertion and deletion operations clustered near the same arbitrary ___location. Some [[deque]] implementations use [[Deque#Implementations|array deques]], which allow amortized constant time insertion/removal at both ends, instead of just one end.
Goodrich<ref>{{Citation | title=Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences | first1=Michael T. | last1=Goodrich | author1-link=Michael T. Goodrich | first2=John G. | last2=Kloss II | year=1999 | url=https://archive.org/details/algorithmsdatast0000wads/page/205 | journal=[[Workshop on Algorithms and Data Structures]] | pages=[https://archive.org/details/algorithmsdatast0000wads/page/205 205–216] | doi=10.1007/3-540-48447-7_21 | volume=1663 | series=Lecture Notes in Computer Science | isbn=978-3-540-66279-2 | url-access=registration }}</ref> presented a dynamic array algorithm called ''tiered vectors'' that provides ''O''(''n''<sup>1/''k''</sup>) performance for insertions and deletions from anywhere in the array, and ''O''(''k'') get and set, where ''k'' ≥ 2 is a constant parameter.
[[Hashed array tree]] (HAT) is a dynamic array algorithm published by Sitarski in 1996.<ref name="sitarski96">{{Citation | title=HATs: Hashed array trees | department=Algorithm Alley | journal=Dr. Dobb's Journal | date=September 1996 | first1=Edward | last1=Sitarski | volume=21 | issue=11 | url=http://www.ddj.com/architect/184409965?pgno=5}}</ref> Hashed array tree wastes order ''n''<sup>1/2</sup> amount of storage space, where ''n'' is the number of elements in the array. The algorithm has ''O''(1) amortized performance when appending a series of objects to the end of a hashed array tree.
In a 1999 paper,<ref name="brodnik">{{Citation | title=Resizable Arrays in Optimal Time and Space |type=Technical Report CS-99-09 | url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf | year=1999 | first1=Andrej | last1=Brodnik | first2=Svante | last2=Carlsson | first5=ED | last5=Demaine | first4=JI | last4=Munro | first3=Robert | last3=Sedgewick | author3-link=Robert Sedgewick (computer scientist) | publisher=Department of Computer Science, University of Waterloo}}</ref><!-- Defined in {{List data structure comparison}}: {{Citation | title=Resizable Arrays in Optimal Time and Space | date=Technical Report CS-99-09 | url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf | year=1999 | first1=Andrej | last1=Brodnik | first2=Svante | last2=Carlsson | first5=ED | last5=Demaine | first4=JI | last4=Munro | first3=Robert | last3=Sedgewick | author3-link=Robert Sedgewick (computer scientist) | publisher=Department of Computer Science, University of Waterloo}} --> Brodnik et al. describe a tiered dynamic array data structure, which wastes only ''n''<sup>1/2</sup> space for ''n'' elements at any point in time, and they prove a lower bound showing that any dynamic array must waste this much space if the operations are to remain amortized constant time. Additionally, they present a variant where growing and shrinking the buffer has not only amortized but worst-case constant time.
Bagwell (2002)<ref>{{Citation | title=Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays | first1=Phil | last1=Bagwell | year=2002 | publisher=EPFL | url=http://citeseer.ist.psu.edu/bagwell02fast.html}}</ref> presented the VList algorithm, which can be adapted to implement a dynamic array.
== Language support ==
[[C++]]'s [[Vector (C++)|<code>std::vector</code>]] and [[Rust (programming language)|Rust]]'s <code>std::vec::Vec</code> are implementations of dynamic arrays, as are the <code>ArrayList</code><ref>Javadoc on {{Javadoc:SE|java/util|ArrayList}}</ref> classes supplied with the [[Java (programming language)|Java]] API and the [[.NET Framework]].<ref>[https://msdn.microsoft.com/en-us/library/system.collections.arraylist ArrayList Class]</ref>
The generic <code>List<></code> class supplied with version 2.0 of the .NET Framework is also implemented with dynamic arrays. [[Smalltalk]]'s <code>OrderedCollection</code> is a dynamic array with dynamic start and end-index, making the removal of the first element also O(1).
[[Python (Programming Language)|Python]]'s <code>list</code> datatype implementation is a dynamic array.
[[Delphi (programming language)|Delphi]] and [[D (programming language)|D]] implement dynamic arrays at the language's core.
[[Ada (programming language)|Ada]]'s [[wikibooks:Ada Programming/Libraries/Ada.Containers.Vectors|<code>Ada.Containers.Vectors</code>]] generic package provides dynamic array implementation for a given subtype.
Many scripting languages such as [[Perl]] and [[Ruby_(programming_language)|Ruby]] offer dynamic arrays as a built-in [[primitive data type]].
Several cross-platform frameworks provide dynamic array implementations for [[C (programming language)|C]], including <code>CFArray</code> and <code>CFMutableArray</code> in [[Core Foundation]], and <code>GArray</code> and <code>GPtrArray</code> in [[GLib]].
[[Common Lisp]] provides a rudimentary support for resizable vectors by allowing to configure the built-in <code>array</code> type as ''adjustable'' and the ___location of insertion by the ''fill-pointer''.
== References ==
<references />
== External links ==
* [https://xlinux.nist.gov/dads/HTML/dynamicarray.html NIST Dictionary of Algorithms and Data Structures: Dynamic array]
* [http://www.bsdua.org/libbsdua.html#vpool VPOOL] - C language implementation of dynamic array.
* [https://web.archive.org/web/20090704095801/http://www.collectionspy.com/ CollectionSpy] — A Java profiler with explicit support for debugging ArrayList- and Vector-related issues.
* [http://opendatastructures.org/versions/edition-0.1e/ods-java/2_Array_Based_Lists.html Open Data Structures - Chapter 2 - Array-Based Lists], [[Pat Morin]]
{{Data structures}}
{{DEFAULTSORT:Dynamic Array}}
[[Category:Arrays]]
[[Category:Articles with example pseudocode]]
[[Category:Amortized data structures]]
| 