Content deleted Content added
Add discussion of and reference for Resizable Arrays in Optimal Time and Space |
→Performance: Disadvantage |
||
Line 36:
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-friendly data structures.
The main disadvantage of dynamic arrays compared to normal arrays is that when they grow they reserve a great deal of space (linear space in fact) that may never be used. This becomes especially problematic when there are a large number of such arrays. There are variants however (see [[#Variants|Variants]]) which waste only <math>\sqrt{n}</math> space at any time.
== Analysis ==
| |||