Content deleted Content added
Undo unexplained blanking |
|||
Line 7:
The simplest dynamic array is constructed by allocating a fixed-size array and then dividing it into two parts: the first stores the elements of the dynamic array and the second is reserved, or unused. We can then add or remove elements at the end of the dynamic array in constant time by using the reserved space, until this space is completely consumed. 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=http://books.google.com/books?id=VtfM3YGW5jYC&pg=PA518&lpg=PA518&dq=%22logical+size%22+%22dynamic+array%22&source=bl&ots=9rXJ9tGomJ&sig=D5dRs802ax43NmEpKa1BUWFk1qs&hl=en&sa=X&ei=CC1JUcLqGufLigKTjYGwCA&ved=0CGkQ6AEwBw#v=onepage&q=%22logical%20size%22%20%22dynamic%20array%22&f=false|publisher=Cengage Learning|year=2009|isbn=1423902181}}</ref>
In applications where the logical size is bounded, the fixed-size data structure suffices. This may be short-sighted, as more space may be needed later. A [[List of software development philosophies|philosophical programmer]] may prefer to write the code to make every array capable of resizing from the outset, then return to using fixed-size arrays during [[program optimization]]. Resizing the underlying array is an expensive task, typically involving copying the entire contents of the array.
== Geometric expansion and amortized cost ==
Line 12 ⟶ 14:
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[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 ensures that inserting ''n'' elements takes [[Big O notation|''O''(''n'')]] time overall, meaning that each insertion takes [[Amortized analysis|amortized]] constant time. The value of this proportion ''a'' leads to a time-space tradeoff: the average time per insertion operation is about ''a''/(''a''−1), while the number of wasted cells is bounded above by (''a''−1)''n''. The choice of ''a'' depends on the library or application: some textbooks use ''a'' = 2,<ref name="gt-ad">{{citation|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|title=Algorithm Design: Foundations, Analysis and Internet Examples|publisher=Wiley|year=2002|contribution=1.5.2 Analyzing an Extendable Array Implementation|pages=39–41}}.</ref><ref name="clrs">{{Introduction to Algorithms|chapter=17.4 Dynamic tables|edition=2|pages=416–424}}</ref> but Java's ArrayList implementation uses ''a'' = 3/2<ref name="java_util_ArrayList" /> and the C implementation of [[Python (programming language)|Python]]'s list data structure uses ''a'' = 9/8.<ref>[http://svn.python.org/projects/python/trunk/Objects/listobject.c List object implementation] from python.org, retrieved 2011-09-27.</ref>
| |||