Quick Index
Overview


We'll look at algorithms (recipes) that are central to a dynamic array.

Let's go here first for a very quick visit: Recipes (Algorithms). Especially see the topic on "context and scope".

Requirements


On this page we will try to figure out the idea for an object that would have these characteristics:


Notes:


Fixed Array


Advantages
Fixed array indexed access is lightening fast no matter how large the array is.
Integer[] a = new Integer[2];
//Add an element
a[0] = 10;
//Add an element
a[1] = 20;
int n = a[1];
Disadvantages (Limitations)
We blowup at the highlighted line. We would get some sort of "index out of bounds" exception.

Fixed arrays have a fixed size, thus we can not append, insert or remove. This is often too limiting.
Integer[] a = new Integer[2];
//Add an element
a[0] = 10;
//Add an element
a[1] = 20;
//Add an element
a[2] = 30;

Our Plan


Impossible Problem?
These two hints, from the requirements, tell us (#1) we need a real fixed array (#2) a fixed array is too limiting.

It seems like an impossible problem (a paradox).

A fixed array but not a fixed array?
Objects to the Rescue
We'll use the oop approach of using components. Our object (e.g. "DynamicArray") will have a component (e.g. "elements") that is a fixed array.

This will solved 50% of the problem right away (the fast access)! We are left with figuring out how to allow dynamic sizing.

Design 1


Extra Capacity
If we gave the fixed array extra capacity, then we would have space to e.g. append a new element.

Our next "append" of an actual element would go into the first blank slot.
Actual Elements vs Blank Slots
The blank slots might be nulls, but we don't really care. We don't use them for anything.

We will not access and return them. We will only return "actual elements" to our object user.
Size and Capacity
  • capacity -- total length of the fixed array (10)
  • size -- count of actual elements (6)

We have extra capacity of 4
Object Diagram
We can see that we'll need to have these available to our logic: "capacity" and "size".

We can derive "capacity" from the our "elements" component.

We'll need to keep track of "size". We'll need a simple (integer) component for that called "size".

Adding / Appending


Note: we use append and add interchangeably here.

Appending (Sufficient Capacity)


Before Append
Let us say we have five extra capacity blank slots.

NOTE WELL:
size = 5
capacity = 10
Append
To append, we simply put the new element into the first blank slot (immediately after the actual elements).

NOTE WELL -- you can determine the append position using "size"
After Append
We now have one more "actual element" and one less "extra capacity"

NOTE WELL:
size = 6
capacity = 10


Appending (No Capacity)


No Extra Capacity
In this case, there is no capcity (slot) for the new element.

We're not able to append.
Two Helper Methods Needed
We need two helper methods:

  • hasCapacity - will answer true if there is sufficient capacity
  • grow - will add more capacity


Algorithm


Try to Devise an Algorithm
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 "append(newElement)" --
-- or "add(newElement)"

1. If !hasCapacity()
	grow()
2. elements[size] = newElement
3. size++

hasCapacity


We will need to be able to ask ourself (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 (growth factor of 2).
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
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

We partition the work to simplify.
Steps #1 and #3 are simple, let us look at #2.

-- Recipe for "copyElementsInto(newArray)"
//Let us call the loop variable "index"
Iterate from 0 to (size - 1)
	element = get element at index
	put element into newArray at index
	index++

Insert


Insertion Position
The index where we want to insert is indicated.
Shift
We need to shift all elements from the insertion position and beyond to the right to make room for insert.

NOTE -- before shifting, we want to check hasCapacity (and grow if necessary).
Empty Position For Insert
We now have an empty slot, ready for a new element.
Insert
With the blank slot now open, it's easy to insert the new element.
Algorithm
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 "insert(index, newElement)" --

1. If index is not valid (0 to size)
	throw exception
2. If !hasCapacity()
	grow()
3. shiftRightFrom(index)
4. elements[index] = newElement
5. size++

-- Recipe for "shiftRightFrom(shiftStartIndex) --
//shiftStartIndex is where we start the shift
//We work backwards from end (do you know why?)
//Let us call the loop variable "i"
Iterate from size down to shiftStartIndex
	element = get element at (i-1)
	put element into newArray at i
	i--

Design 2


Updated Object Diagram
As usual we learn new things while working through algorithms.

We needed a "growth factor" for the "grow" algorithm. Let's add that as an ivar.

Note: when coding you may add additional components, not shown here, that are specific to your coding solution.

Getting and Setting 👍🏽


Goal Achieved


Our goal has been achieved. Our growing and shifting recipes paid off because we have achieved our primary goal:


Getting and Setting


The algorithm for "get" is a non-algorithm (it's too simple). This is good.

We would simply access our fixed array component in the typical ways

And even better, this applies to any of our solution (code) that uses indexed access (for getting or setting fixed array elements).

Iteration


Just like "getting and setting", the algorithm for iteration is a non-algorithm because it is too simple (again this is good).

We would simply iterate over the fixed array in the standard ways:


References




































Coding Fundamentals (Chapter 302 - Dynamic Array Algorithms)










< Dynamic Array Algorithms

Chapter Top Search Site TOC