Several values are inserted at the end of a dynamic array using geometric expansion. Grey cells indicate space reserved for expansion. Most insertions are fast (constant time), while some are slow due to the need for reallocation (Θ(n) time, labelled with turtles). The logical size and capacity of the final array are shown.
In computer science, a dynamic array, growable array, resizable array, dynamic table, mutable array, or array list is a random access, variable-size list data structure that allows elements to be added or removed. It is supplied with standard libraries in many modern mainstream programming languages. Dynamic arrays overcome a limit of static arrays, 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.
about a/(a−1), while the number of wasted cells is bounded above by (a−1)n. 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 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:
| Implementation | Growth factor (a) |
|---|---|
| Java ArrayList | 1.5 (3/2) |
| Python PyListObject | ~1.125 (n + (n >> 3)) |
| Microsoft Visual C++ 2013 | 1.5 (3/2) |
| G++ 5.2.0 | 2 |
| Clang 3.6 | 2 |
| Facebook folly/FBVector | 1.5 (3/2) |
| Unreal Engine TArray | ~1.375 (n + ((3 * n) >> 3)) |
| Rust Vec | 2 |
| Go slices | between 1.25 and 2 |
| Nim sequences | 2 |
| SBCL (Common Lisp) vectors | 2 |
| C# (.NET 8) List | 2 |
Performance
edit| View original on Wikipedia | Back | FazBrowse Home |