Editing Dynamic array (section)

== 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 [[Time complexity#Constant time|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.<ref>{{citation|author=Lambert, Kenneth Alfred|title=Physical size and logical size|work=Fundamentals of Python: From First Programs Through Data Structures|page=510|url=https://books.google.com/books?id=VtfM3YGW5jYC&q=%22logical+size%22+%22dynamic+array%22&pg=PA518|publisher=Cengage Learning|year=2009|isbn=978-1423902188}}</ref>  

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