Content deleted Content added
m →Variations: Word fix |
→Overview: Link big-O notation, add braces |
||
Line 9:
To deal with this, we instead resize the array by a large amount, such as doubling its size. Then, the next time we need to enlarge the array, we just expand it into some of this reserved space. The amount of space we have allocated for the array is called its ''capacity'', and it may be larger than its current logical size. Here's how the operation adding an element to the end might work:
'''function''' insertEnd(''dynarray'' a, ''element'' e) {
'''if''' a.size = a.capacity {
resize a to twice its current capacity
Line 16:
a[a.size] := e
a.size := a.size + 1
}
Using [[amortized analysis]], it can be shown that as long as we expand the array by some fixed percentage each time, the cost for inserting ''n'' elements will be O(''n''); we say the insertions have an ''amortized cost'' of O(1) each (see [[big-O notation]] for an explanation of this notation).
Many dynamic arrays also deallocate some of the underlying storage if its size drops below a certain threshold, such as 30% of the capacity.
| |||