Dynamic array: Difference between revisions

Revision as of 09:29, 20 March 2021

Revision as of 04:18, 28 March 2021

Line 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 [[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-sizedsize 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: