Skip to main content

Welcome to Programming and Data Structures

Andrew Scholer

Section 23.13 Insert At

Although the normal use case for an ArrayList is to insert items at the end, we may also want to insert items at specific positions. However, doing so will be much more complex than simply appending to the end.
🔗
Imagine we have an ArrayList that contains 10, 20, 30, 40 and we decide that we want to insert 15 at index 1 (between 10 and 20). We don’t want to replace the value at index 1, we still want 20 to be in the list, so that means we need to shift it over to index 2. Which means 30 needs to move to index 3. And 40 needs to move to index 4... Anything after the insertion point will have to shift over so that we end up with 10, 15, 20, 30, 40.
🔗
To do this, we will need to start at the end of the list and work backwards, moving each item over one index until we reach the insertion point. Then we can place the new item in the now-empty spot.
🔗

Exploration 23.13.1.

(a)

Our initial state. We want to insert 15 at index 1.
🔗
The intList variable contains an m_size of 4 and m_capacity of 5. It also has a pointer to an array named m_arr. That array contains [10, 20, 30, 40, ???]
🔗

(b)

We work backwards using the loop counter i which starts at m_size. At each location, we copy the value from m_arr[i - 1] to m_arr[i]. First we copy 40 from index 3 to index 4.
🔗
i is 4. We copy 40 from index 3 to index 4. The array is now [10, 20, 30, 40, 40]
🔗

(c)

Now i is 3. We copy 30 from index 2 to index 3.
🔗
i is 3. We copy 30 from index 2 to index 3. The array is now [10, 20, 30, 30, 40]
🔗

(d)

Now i is 2. We copy 20 from index 1 to index 2.
🔗
i is 2. We copy 20 from index 1 to index 2. The array is now [10, 20, 20, 30, 40]
🔗

(e)

Now i is 1. That is the location we want to insert at. So we can stop our loop and place the new item (15) in this location.
🔗
i is 1. We place 15 at index 1. The array is now [10, 15, 20, 30, 40]
🔗

(f)

Finally, we need to update the size of the ArrayList.
🔗
m_size is now 5.
🔗
🔗
The core logic will look like this:
🔗
Listing 23.13.1.
🔗
template<typename T>
void ArrayList<T>::insertAt(int location, const T& insertItem) {
    // Shift elements up to make room for the new item
    for (int i = m_size; i > location; --i) {
        m_arr[i] = m_arr[i - 1];
    }
    m_arr[location] = insertItem;
    ++m_size;
}
We will want to sanity check the location we are given. Inserting at a negative index makes no sense. Nor does inserting at an index greater than m_size as that would leave a gap. (It does make sense to insert at m_size, even though there is nothing currently there, as that is the location just past the last element.) We also would want to ensure that we have enough capacity to accommodate the new item. So the complete version of the function would look like:
🔗
Listing 23.13.2.
🔗
template<typename T>
void ArrayList<T>::insertAt(int location, const T& insertItem) {
    if (location < 0 || location > m_size) {
        throw std::out_of_range("Index out of range");
    }
    if (m_size == m_capacity) {
        grow();
    }
    // Shift elements up to make room for the new item
    for (int i = m_size; i > location; --i) {
        m_arr[i] = m_arr[i - 1];
    }
    m_arr[location] = insertItem;
    ++m_size;
}

Checkpoint 23.13.1.

To do removeAt(index), we won’t actually remove anything. Instead, we just need to shift all the following downs elements down by 1 to fill the gap left by the removed item. Then we will decrease the logical size of the ArrayList.
🔗
For example, if our array is storing {10, 20, 30, 40, ???} and we remove index 1, we would want to shift the 30 and 40 down to fill the gap: {10, 30, 40, ???, ???}.
🔗
Construct a block of code that performs this operation:
🔗
Hint.
We need to loop from the index to the end so that as we shift elements down, we don’t overwrite any elements before they have been moved.
🔗
🔗
🔗
You have attempted of activities on this page.
🔗
PrevTopNext