Growing

Section 23.11 Growing

What happens if we want to add another element to the ArrayList, but we are already using all of the available space in the array? In that case, we need to “grow the array”.

🔗

We can’t actually change the size of an allocated array. So we need to do some slight of hand. Instead, we will allocate a new array with a larger capacity, copy the existing elements over to the new array, and then delete the old array.

🔗

We will know we need to grow the array when m_size is equal to m_capacity, as in the figure below. In it, we are imagining that the originally allocated array was only size 3. Thus m_capacity is 3. We are already storing 10, 20, 30 in the array, so if we want to add another value, we need to “grow”.

🔗

Growing consists of the following steps:

Double our current capacity m_capacity. We will cover in detail why doubling is a good strategy later on. But the short version is that growing is expensive. So if we are bothering to grow, we want to make sure we don’t have to do it again right away.

🔗
Allocating a new array with the larger capacity.

🔗
Copying the existing elements over to the new array.

🔗
Delete the old array and point at the new array.

🔗

🔗

Here is one possible implementation:

🔗

template<typename T>
void ArrayList<T>::grow() {
    // double the capacity and allocate a new array of that size
    m_capacity *= 2;
    T* newArr = new T[m_capacity];
    // copy old items to new array
    for (int i = 0; i < m_size; ++i) {
        newArr[i] = m_arr[i];
    }
    // delete old array and update pointer
    delete[] m_arr;
    m_arr = newArr;
}

The following demonstration illustrates the process of growing the array:

🔗

Exploration 23.11.1.

(a)

Our initial state. We are in the stack frame of the grow function. this is the current ArrayList instance that is growing. Its size currently matches its capacity.

🔗

The intList variable contains an m_size of 3 and m_capacity of 3. It also has a pointer to an array named m_arr. That array contains [10, 20, 30]

🔗

(b)

Double our current capacity.

🔗

m_capacity *= 2;

m_capacity is now 6. The array itself is still only size 3.

🔗

(c)

We allocate a new array with the larger capacity. newArr is a temporary local variable that points to the newly allocated array.

🔗

T* newArr = new T[m_capacity];

Now there is a local variable newArr that points to the newly allocated array of size 6. It is uninitialized.

🔗

(d)

We copy the existing elements over to the new array. Note that we need to use m_size (the old size) to copy the correct number of elements.

🔗

for (int i = 0; i < m_size; ++i) {
    newArr[i] = m_arr[i];
}

Now the newArr variable contains the three elements from the old array. The last three elements are still uninitialized. It looks like [10, 20, 30, ???, ???, ???].

🔗

(e)

Delete the old array. At this point, m_arr points at a bad address.

🔗

delete[] m_arr;

🔗

(f)

Set the member variable m_arr to point at the new array.

🔗

m_arr = newArr;

Now the m_arr variable of the ArrayList points at the array containing [10, 20, 30, ???, ???, ???].

🔗

(g)

As we leave the grow function, newArr will go out of scope and disappear. But the member variable m_arr now points to the new array. (A pointer going out of scope does not delete the memory it points to!)

🔗

The newArr pointer disappears, but the memory it points to is still valid.

🔗

With this grow logic in place, we can now dynamically resize our array as needed. Any time we go to insert a new element and find that we are at capacity, we can call grow to increase the size of the underlying array. After doing so, we know there will be room to add new elements.

🔗

template<typename T>
void ArrayList<T>::insertEnd(const T& newItem) {
    if (m_size == m_capacity) {
        grow();
    }
    // Now we know there is empty space available
    m_arr[m_size] = newItem;
    m_size++;
}

We will never “shrink” the array back down. We can’t reduce the size of an allocated array, so to shrink the storage being used, we would have to allocate a new smaller array and copy everything to it before deleting the old array. Generally, doing that work is not worth saving a small amount of memory.

🔗

If the programmer knew they were going to insert a large number of elements, then remove most of them and keep working with that smaller number of elements, they could always choose to make a new smaller ArrayList once they are down to the final size.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next