Incomputer science, adynamic array,growable array,resizable array,dynamic table,mutable array, orarray list is arandom access, variable-sizelist data structure that allows elements to be added or removed. It is supplied withstandard libraries in many modern mainstreamprogramming languages. Dynamic arrays overcome a limit of staticarrays, which have a fixed capacity that needs to be specified atallocation.
A dynamic array is not the same thing as adynamically allocated array orvariable-length array, either of which is an array whose size is fixed when the array is allocated, although a dynamic array may use such a fixed-size array as a back end.[1]
A simple dynamic array can be constructed by allocating an array of fixed-size, typically larger than the number of elements immediately required. The elements of the dynamic array are stored contiguously at the start of the underlying array, and the remaining positions towards the end of the underlying array are reserved, or unused. Elements can be added at the end of a dynamic array inconstant time by using the reserved space, until this space is completely consumed. When all space is consumed, and an additional element is to be added, then the underlying fixed-size array needs to be increased in size. Typically resizing is expensive because it involves allocating a new underlying array and copying each element from the original array. Elements can be removed from the end of a dynamic array in constant time, as no resizing is required. The number of elements used by the dynamic array contents is itslogical size orsize, while the size of the underlying array is called the dynamic array'scapacity orphysical size, which is the maximum possible size without relocating data.[2]
A fixed-size array will suffice in applications where the maximum logical size is fixed (e.g. by specification), or can be calculated before the array is allocated. A dynamic array might be preferred if:
To avoid incurring the cost of resizing many times, dynamic arrays resize by a large amount, such as doubling in size, and use the reserved space for future expansion. The operation of adding an element to the end might work as follows:
functioninsertEnd(dynarraya,elemente)if(a.size==a.capacity)// resize a to twice its current capacity:a.capacity←a.capacity*2// (copy the contents to the new memory location here)a[a.size]←ea.size←a.size+1
Asn elements are inserted, the capacities form ageometric progression. Expanding the array by any constant proportiona ensures that insertingn elements takesO(n) time overall, meaning that each insertion takesamortized constant time. Many dynamic arrays also deallocate some of the underlying storage if its size drops below a certain threshold, such as 30% of the capacity. This threshold must be strictly smaller than 1/a in order to providehysteresis (provide a stable band to avoid repeatedly growing and shrinking) and support mixed sequences of insertions and removals with amortized constant cost.
Dynamic arrays are a common example when teachingamortized analysis.[3][4]
The growth factor for the dynamic array depends on several factors including a space-time trade-off and algorithms used in the memory allocator itself. For growth factora, the average time per insertion operation isabouta/(a−1), while the number of wasted cells is bounded above by (a−1)n[citation needed]. If memory allocator uses afirst-fit allocation algorithm, then growth factor values such asa=2 can cause dynamic array expansion to run out of memory even though a significant amount of memory may still be available.[5] There have been various discussions on ideal growth factor values, including proposals for thegolden ratio as well as the value 1.5.[6] Many textbooks, however, usea = 2 for simplicity and analysis purposes.[3][4]
Below are growth factors used by several popular implementations:
| Implementation | Growth factor (a) |
|---|---|
| Java ArrayList[1] | 1.5 (3/2) |
| Python PyListObject[7] | ~1.125 (n + (n >> 3)) |
| Microsoft Visual C++ 2013[8] | 1.5 (3/2) |
| G++ 5.2.0[5] | 2 |
| Clang 3.6[5] | 2 |
| Facebook folly/FBVector[9] | 1.5 (3/2) |
| Unreal Engine TArray[10] | ~1.375 (n + ((3 * n) >> 3)) |
| Rust Vec[11] | 2 |
| Go slices[12] | between 1.25 and 2 |
| Nim sequences[13] | 2 |
| SBCL (Common Lisp) vectors[14] | 2 |
| C# (.NET 8) List | 2 |
| Peek (index) | Mutate (insert or delete) at … | Excess space, average | |||
|---|---|---|---|---|---|
| Beginning | End | Middle | |||
| Linked list | Θ(n) | Θ(1) | Θ(1), known end element; Θ(n), unknown end element | Θ(n) | Θ(n) |
| Array | Θ(1) | N/a | N/a | N/a | 0 |
| Dynamic array | Θ(1) | Θ(n) | Θ(1)amortized | Θ(n) | Θ(n)[15] |
| Balanced tree | Θ(log n) | Θ(log n) | Θ(logn) | Θ(logn) | Θ(n) |
| Random-access list | Θ(log n)[16] | Θ(1) | N/a[16] | N/a[16] | Θ(n) |
| Hashed array tree | Θ(1) | Θ(n) | Θ(1)amortized | Θ(n) | Θ(√n) |
The dynamic array has performance similar to an array, with the addition of new operations to add and remove elements:
Dynamic arrays benefit from many of the advantages of arrays, including goodlocality of reference anddata cache utilization, compactness (low memory use), andrandom 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 buildingcache-friendlydata 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 storereferences 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 tolinked lists, 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 thegap buffer andtiered vector variants discussed underVariants below. Also, in a highlyfragmented 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.
Abalanced 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.
Gap buffers are similar to dynamic arrays but allow efficient insertion and deletion operations clustered near the same arbitrary location. Somedeque implementations usearray deques, which allow amortized constant time insertion/removal at both ends, instead of just one end.
Goodrich[17] presented a dynamic array algorithm calledtiered vectors that providesO(n1/k) performance for insertions and deletions from anywhere in the array, andO(k) get and set, wherek ≥ 2 is a constant parameter.
Hashed array tree (HAT) is a dynamic array algorithm published by Sitarski in 1996.[18] Hashed array tree wastes ordern1/2 amount of storage space, wheren is the number of elements in the array. The algorithm hasO(1) amortized performance when appending a series of objects to the end of a hashed array tree.
In a 1999 paper,[19] Brodnik et al. describe a tiered dynamic array data structure, which wastes onlyn1/2 space forn 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)[20] presented the VList algorithm, which can be adapted to implement a dynamic array.
Naïve resizable arrays -- also called "the worst implementation" of resizable arrays -- keep the allocated size of the array exactly big enough for all the data it contains, perhaps by callingrealloc for each and every item added to the array. Naïve resizable arrays are the simplest way of implementing a resizable array in C. They don't waste any memory, but appending to the end of the array always takes Θ(n) time.[18][21][22][23][24]Linearly growing arrays pre-allocate ("waste") Θ(1) space every time they re-size the array, making them many times faster than naïve resizable arrays -- appending to the end of the array still takes Θ(n) time but with a much smaller constant.Naïve resizable arrays and linearly growing arrays may be useful when a space-constrained application needs lots of small resizable arrays;they are also commonly used as an educational example leading to exponentially growing dynamic arrays.[25]
C++'sstd::vector andRust'sstd::vec::Vec are implementations of dynamic arrays, as arejava.util.ArrayList[26] inJava[27]: 236 andSystem.Collections.ArrayList in the.NET Framework.[28][29]: 22
The genericSystem.Collections.Generic.List<T> class in version 2.0 of the.NET Framework is also implemented with dynamic arrays.Smalltalk'sOrderedCollection is a dynamic array with dynamic start and end-index, making the removal of the first element also O(1).
Python'slist datatype implementation is a dynamic array the growth pattern of which is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...[30]
Delphi andD implement dynamic arrays at the language's core.
Ada'sAda.Containers.Vectors generic package provides dynamic array implementation for a given subtype.
Many scripting languages such asPerl andRuby offer dynamic arrays as a built-inprimitive data type.
Several cross-platform frameworks provide dynamic array implementations forC, includingCFArray andCFMutableArray inCore Foundation, andGArray andGPtrArray inGLib.
Common Lisp provides a rudimentary support for resizable vectors by allowing to configure the built-inarray type asadjustable and the location of insertion by thefill-pointer.
{{citation}}: CS1 maint: work parameter with ISBN (link){{citation}}: CS1 maint: work parameter with ISBN (link)ArrayList