Dynamic Arrays

The fix is to wrap the fixed-size array in a class that does the bookkeeping for us. That class still holds a fixed-size array underneath, but it tracks how many values the array holds and resizes the array on its own when the array is full. A structure that does this is called a dynamic array, and a client uses it like this:

DynamicArray numbers = new DynamicArray();  // No size to declare!

numbers.add(10);
numbers.add(25);
numbers.add(7);
numbers.add(42);
// ... keep adding as many as you like; you never run out of room ...

System.out.println(numbers.get(0));     // 10
System.out.println(numbers.size());     // 4  (how many we've added)

You might have used a dynamic array already. Java’s ArrayList, Python’s list, C++'s std::vector, and JavaScript’s Array are all dynamic arrays. Every time you appended to a list without worrying about its size, one of these was doing the resizing for you.

Notice how little the client (the code using the dynamic array) has to know. There are really just three operations:

• add(value) — put a new value at the end of the collection.
• size() — how many values have been added so far.
• get(index) — retrieve the value at a given index.

There is no resize operation. The client does not need to worry about the array’s fixed size. They do not even know how big the underlying array is.

We will implement this data structure over the next several sections.