Dynamic array

As we saw in the section on arrays, static arrays aren't able to grow or shrink in size. Dynamic arrays overcome this limitation.

What is a dynamic array?

At the risk of repeating myself: a dynamic array is an array that is able to shrink and grow in size. It's commonly implemented using a static array and, as with a static array, it allows updating of values, but it also allows the user to delete, append and insert values.

Let's look at how the various dynamic array operations work, before diving into some code. We won't cover searching in much detail. As with a static array, it's $O (n)$ . Also, access is constant-time like a static array.

Appending an element

To implement a dynamic array using a static array, we typically start with a static array of a particular capacity, say four. When we want to append the first value, we append it to the next empty slot in the array. What happens when the array is full, though?

Well, we create a new, larger array, copy over the elements from the previous array and then append the new value. We can choose how large the new array is going to be. One common strategy is to double the capacity of the previous array. So now our array has a capacity of eight and a "size" of five.

So what's the time complexity of appending an element to a dynamic array? It depends. In most cases, the capacity of the array will be greater than the size, so the time complexity will be constant. Simply append the new element to the next available slot.

When the size equals the capacity, though, a new array of double the capacity is created and each element from the previous array is copied over to the new array. Then, finally, the new element is appended to the new array.

To reason about the time complexity of this, suppose first that the initial array has a capacity of 1, that we double the array capacity when it needs to be increased and that we make a total of $n$ appends.

Most of the appends will take constant time, but some will take longer. Which ones take longer? It will be the ones where the current array size is a power of two: 1, 2, 4, 8 and so on.

Each time the capacity is doubled from $x$ to $2 x$ , $x$ elements are copied from the previous array to the new array. So, to append a total of $n + 1$ elements to the array, we make roughly $n + n / 2 + n / 4 + … + 2 + 1$ copies. It's "roughly" because $n$ might not be a strict power of two.

This is a geometric series which evaluates to $2 n - 1$ . So that's $O (n)$ steps for the copies. Add this to the $O (n)$ steps needed to do the actual $n + 1$ appends and we have a total time complexity of $O (n)$ for appending $n + 1$ elements to the dynamic array.

If we evenly spread out this cost over the $n + 1$ items, we get an average cost of $O (1)$ for appending a single item. This is often referred to as the "amortised time complexity" of appending an element to a dynamic array. Again, see Introduction to Algorithms, Third Edition for a more formal treatment of amortised analysis.

Inserting an element

Inserting an element into a dynamic array is a bit different to appending an element. In addition to the amortised constant-time append of the element, we'll need to shift over some other elements in order to make room for the new element. If there are previously $n$ elements in the array, then in the worst case, we'll need to shift the majority of them into their new correct positions before inserting the new element. So the entire time complexity of inserting an element is linear, or $O (n)$ .

Deleting an element

To delete an element from an array of size $n$ , a common strategy is to create a new array of size one less than the previous array and copy over all the previous elements except the one to be deleted into the new array. This will take $O (n)$ time.

Space complexity

How about the space complexity of appending $n$ elements to a dynamic array? Suppose again that the initial capacity of the array is one and that we double the capacity each time it's reached. Then appending $n$ elements requires roughly $1 + 2 + 4 + 8 + … + n$ units of space. This is the same geometric series encountered when appending items to the array and it equals $2 n - 1$ . Therefore, appending $n$ items has a space complexity of $O (n)$ .

Implementation

Alright. Time for some code. We'll be implementing the dynamic array in the Java programming language.

Let's start with the class constructors.

Dynamic array constructors

@SuppressWarnings("unchecked")
public class DynamicArray<E> {
  private E[] array; // Internal static array
  private int size = 0;
  private int capacity = 0;

  // Default capacity is 10
  DynamicArray() {
    this(10);
  }

  DynamicArray(int initialCapacity) {
    if (initialCapacity <= 0) {
      throw new IllegalArgumentException("Initial capacity must be > 0; got: " +
        initialCapacity);
    }
    array = (E[]) new Object[initialCapacity];
    capacity = initialCapacity;
  }
}

That "SuppressWarnings" annotation at the beginning prevents the compiler from complaining about the cast from an Object array to an E array.

Next, we'll add two small methods underneath the constructors, to check if the array is empty and to return its size.

Dynamic array isEmpty() and size() methods

public boolean isEmpty() {            
  return size == 0;
}

public int size() {
  return size;
}

And now a method to add a new element to the end of the array.

Dynamic array add() method

public boolean add(E element) {
  if (size < capacity) {
    array[size++] = element;
    return true;
  }
  
  // Increase array capacity
  capacity *= 2;
  E[] newArray = (E[]) new Object[capacity];
  for (int i = 0; i < array.length; i++) {
    newArray[i] = array[i];
  }
  newArray[size++] = element;
  array = newArray;
  return true;
}

Next up is a method to get an element at a particular index.

Dynamic array get() method

public E get(int index) {
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException("Index is out of bounds; got: " + 
      index);
  }  
  return array[index];
}

And a method to set a particular index to a particular value:

Dynamic array set() method

public E set(int index, E element) {            
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException("Index is out of bounds; got: " + 
      index);
  }
  E previousElement = array[index];
  array[index] = element;
  return previousElement;
}

And finally, a method to remove the element at a given index from the array.

Dynamic array remove() method

public E remove(int index) {            
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException("Index is out of bounds; got: " + 
      index);
  }
  E element = array[index];
  E[] newArray = (E[]) new Object[size - 1];
  for (int i = 0, j = 0; i < size; i++, j++) {
    if (i == index) j--; // Skip over the element to be removed
    else newArray[j] = array[i];
  }
  array = newArray;
  capacity = --size;
  return element;
}

The Java implementation of a dynamic array is the ArrayList. The documentation lists other methods which aren't implemented here but, by all means, feel free to add them to your implementation.

Key takeaways

We've seen that a dynamic array:

Overcomes the fixed-size limitation of a static array.
Has amortised constant-time appends.
Is relatively straightforward to code up.

There's one limitation of both static and dynamic arrays which we haven't dwelt on, though: they can only hold objects which have the same size. So, typically, they're used to hold objects of the same type. The next data structure we'll look at provides a solution to this problem.