Making Room For New Elements

Inserting elements in the middle of the list presents similar problems as removing elements from the list. In order to squeeze a new element in to the middle of a list, the entire list has to shift over the elements that come after this spot to make room for it.

First, let's just visualize how the underlying array looks as the list grows. When you're doing append, it's adding an element - we'll make sure there's enough room for one new element in the unused space at the end of the list in the underlying array. You use the grow method to double the size of the array if you're trying to append something when the underlying array can't fit anything more.

This table uses underscore characters to represent indexes in the array that have undefined values, for the sake of brevity. The internal array starts with a default size of 2, so grows occur often.

Action Contents Grows? List Size Array Length
create the array [\_, \_] 0 2
append 1 [1, \_] no 1 2
append 2 [1, 2] no 2 2
append 3 [1, 2, 3, \_] yes 3 4
append 4 [1, 2, 3, 4] no 4 4
append 5 [1, 2, 3, 4, 5, \_, \_, \_] yes 5 8
append 6 [1, 2, 3, 4, 5, 6, \_, \_] no 6 8
append 7 [1, 2, 3, 4, 5, 6, 7, \_] no 7 8
append 8 [1, 2, 3, 4, 5, 6, 7, 8] no 8 8
append 9 [1, 2, 3, 4, 5, 6, 7, 8, 9, \_, ...] yes 9 16

Exercise: Write an Insert method

Using your JSBin with your list (so you have a spot to write and can test it out!), write an .insert(i, item) method for the ArrayList class that inserts new items at the given index.

  • Make sure to scoot previous items at the index out of the way with a for loop.
  • Make sure there's enough room for one new element in the unused space at the end of the list in the array.
    • Use the grow method to double the size of the array if you're trying to insert something when the underlying array can't fit anything more.

It might be helpful to fill out a table representing the state of the list as it changes to help you figure out when exactly to grow the array.

Check your solution here Don't close the JSBin! There are more exercises to come...

results matching ""

    No results matching ""