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 toinsert
something when the underlying array can't fit anything more.
- Use the
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...