HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, a dynamic array, growable array, resizable array, dynamic table, mutable array, or array list is a
random access Random access (also called direct access) is the ability to access an arbitrary element of a sequence in equal time or any datum from a population of addressable elements roughly as easily and efficiently as any other, no matter how many elemen ...
, variable-size list data structure that allows elements to be added or removed. It is supplied with standard libraries in many modern mainstream
programming language A programming language is a system of notation for writing computer programs. Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
s. Dynamic arrays overcome a limit of static
arrays An array is a systematic arrangement of similar objects, usually in rows and columns. Things called an array include: {{TOC right Music * In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
, which have a fixed capacity that needs to be specified at allocation. A dynamic array is not the same thing as a dynamically allocated array or variable-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.See, for example, th
source code of java.util.ArrayList class from OpenJDK 6


Bounded-size dynamic arrays and capacity

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 in constant 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 its ''logical size'' or ''size'', while the size of the underlying array is called the dynamic array's ''capacity'' or ''physical size'', which is the maximum possible size without relocating data. 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: * the maximum logical size is unknown, or difficult to calculate, before the array is allocated * it is considered that a maximum logical size given by a specification is likely to change * the amortized cost of resizing a dynamic array does not significantly affect performance or responsiveness


Geometric expansion and amortized cost

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: function insertEnd(dynarray a, element e) 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 .size← e a.size ← a.size + 1
As ''n'' elements are inserted, the capacities form a geometric progression. Expanding the array by any constant proportion ''a'' ensures that inserting ''n'' elements takes ''O''(''n'') time overall, meaning that each insertion takes amortized 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 provide
hysteresis Hysteresis is the dependence of the state of a system on its history. For example, a magnet may have more than one possible magnetic moment in a given magnetic field, depending on how the field changed in the past. Plots of a single component of ...
(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 teaching amortized analysis.


Growth factor

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 factor ''a'', the average time per insertion operation is . If memory allocator uses a first-fit allocation algorithm, then growth factor values such as ''a''=2 can cause dynamic array expansion to run out of memory even though a significant amount of memory may still be available. There have been various discussions on ideal growth factor values, including proposals for the
golden ratio In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their summation, sum to the larger of the two quantities. Expressed algebraically, for quantities and with , is in a golden ratio to if \fr ...
as well as the value 1.5. Many textbooks, however, use ''a'' = 2 for simplicity and analysis purposes.. Below are growth factors used by several popular implementations:


Performance

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 In computer science, locality of reference, also known as the principle of locality, is the tendency of a processor to access the same set of memory locations repetitively over a short period of time. There are two basic types of reference localit ...
and data cache utilization, compactness (low memory use), and
random access Random access (also called direct access) is the ability to access an arbitrary element of a sequence in equal time or any datum from a population of addressable elements roughly as easily and efficiently as any other, no matter how many elemen ...
. 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-friendly
data structures In computer science, a data structure is a data organization and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, and the functi ...
. 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
references A reference is a relationship between Object (philosophy), objects in which one object designates, or acts as a means by which to connect to or link to, another object. The first object in this relation is said to ''refer to'' the second object. ...
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 In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whi ...
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 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 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 buffers are similar to dynamic arrays but allow efficient insertion and deletion operations clustered near the same arbitrary location. Some deque implementations use array deques, which allow amortized constant time insertion/removal at both ends, instead of just one end. Goodrich presented a dynamic array algorithm called ''tiered vectors'' that provides ''O''(''n''1/''k'') 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. Hashed array tree wastes order ''n''1/2 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, Brodnik et al. describe a tiered dynamic array data structure, which wastes only ''n''1/2 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) 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 calling realloc 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. 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.


Language support

C++'s std::vector and Rust's std::vec::Vec are implementations of dynamic arrays, as are the ArrayList classes supplied with the
Java Java is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea (a part of Pacific Ocean) to the north. With a population of 156.9 million people (including Madura) in mid 2024, proje ...
API and the .NET Framework. The generic List<> class supplied with version 2.0 of the .NET Framework is also implemented with dynamic arrays.
Smalltalk Smalltalk is a purely object oriented programming language (OOP) that was originally created in the 1970s for educational use, specifically for constructionist learning, but later found use in business. It was created at Xerox PARC by Learni ...
's OrderedCollection is a dynamic array with dynamic start and end-index, making the removal of the first element also O(1). Python's list datatype implementation is a dynamic array the growth pattern of which is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...listobject.c (github.com)
/ref>
Delphi Delphi (; ), in legend previously called Pytho (Πυθώ), was an ancient sacred precinct and the seat of Pythia, the major oracle who was consulted about important decisions throughout the ancient Classical antiquity, classical world. The A ...
and D implement dynamic arrays at the language's core. Ada's Ada.Containers.Vectors generic package provides dynamic array implementation for a given subtype. Many scripting languages such as
Perl Perl is a high-level, general-purpose, interpreted, dynamic programming language. Though Perl is not officially an acronym, there are various backronyms in use, including "Practical Extraction and Reporting Language". Perl was developed ...
and
Ruby Ruby is a pinkish-red-to-blood-red-colored gemstone, a variety of the mineral corundum ( aluminium oxide). Ruby is one of the most popular traditional jewelry gems and is very durable. Other varieties of gem-quality corundum are called sapph ...
offer dynamic arrays as a built-in primitive data type. Several cross-platform frameworks provide dynamic array implementations for C, including CFArray and CFMutableArray in Core Foundation, and GArray and GPtrArray in GLib.
Common Lisp Common Lisp (CL) is a dialect of the Lisp programming language, published in American National Standards Institute (ANSI) standard document ''ANSI INCITS 226-1994 (S2018)'' (formerly ''X3.226-1994 (R1999)''). The Common Lisp HyperSpec, a hyperli ...
provides a rudimentary support for resizable vectors by allowing to configure the built-in array type as ''adjustable'' and the location of insertion by the ''fill-pointer''.


See also

* Stack (data structure) * Queue (data structure)


References


External links


NIST Dictionary of Algorithms and Data Structures: Dynamic array


- C language implementation of dynamic array.
CollectionSpy
— A Java profiler with explicit support for debugging ArrayList- and Vector-related issues.

Pat Morin {{DEFAULTSORT:Dynamic Array Arrays Articles with example pseudocode Amortized data structures