Editing Dynamic array (section)

== 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.