Quick Index
Index
hasCapacity


We will need to be able to ask (as the dynamic array) if we have sufficient capacity for another element.

We could call this method something like "hasCapacity".

Recipe / Algorithm
The "hasCapacity" method should answer true if we have sufficient capacity to append or insert another element.

The recipe:
	size < capacity

grow


Overview


The ability for the structure to "grow" is the essence of our dynamic array.

If we can figure out how to grow the structure, then (after the grow) we can do a simple append (with sufficient capacity).

Steps


We can add a helper method 'grow'. We would call this helper method when "hasCapacity" is false.

Step 1: Construct New Fixed Array
We first construct a new empty larger fixed array.

We use a growth factor.

For example here we have doubled the capacity (2 is a commonly used factor).
Step 2: Copy Elements Into New Fixed Array
Copy elements from old array into new array.

Note that after the copy, the fixed array now has available capacity (empty "slots").
Step 3: Reset Ivar to New Array
Finally, we assign the new array to our ivar.


Algorithm


Try to Devise an Algorithm for "grow"
First try to come up with an algorithm on your own.

If you get stuck or want to compare then click to show a solution.


-- Recipe for "grow" --
//note: we "round" product to nearest integer
1. newCapacity = round(existingCapacity * growthFactor)
2. newArray = constructNewArray(newCapacity)
3. copyElementsInto(newArray)
4. this.elements = newArray

Notes:

2. simply constructs a fixed array
3. uses basic looping and indexing to copy elements






























Data Structures And Algorithms (DSA) (Chapter 304 - Dynamic Array)










Chapter 304 - Dynamic Array Growing

Contents Intro Design Add Grow Insert Remove Access Design-2 Memory

Chapter Top Search TOC