(^546) | Array-Based Lists
Assuming that indexis the place where itemis to be inserted, the algorithm for shifting
the remainder of the list down is as follows:
This algorithm is illustrated in Figure 11.7.
This algorithm is based on how we would accomplish the task by hand. Often, such an
adaptation is the best way to solve a problem. However, in this case, further thought reveals
a slightly better approach. Notice that we search from the front of the list (people always do),
and we shift down from the end of the list upward. We can, in fact, combine the searching
and shifting operations by beginning at the endof the list.
Ifitemis the new item to be inserted, we can compareitemto the value inlistItems[numItems
- 1].Ifitemisless, we putlistItems[numItems–1]intolistItems[numItems]and compareitemto
the value inlistItems[numItems–2]. This process continues until we find the place whereitem
is greater than or equal to the list item. We then storeitemdirectly after it. Here is the algorithm:
insert (revised)
if(list is not full)
Set index to numItems – 1
whileindex >= 0 && (item.compareTo(listItems[index]) < 0)
Set listItems[index + 1] to listItems[index]
Decrement index
Set listItems[index + 1] to item
Increment numItemsshiftDown
Set listItems[numItems] to listItems[numItems – 1]
Set listItems[numItems – 1] to listItems[numItems – 2]
.
.
.
Set listItems[index + 1] to listItems[index]insert
if(list is not full)
whileplace not found AND more places to look
ifitem > current item in the list
Increment current position
else
Place found
Shift remainder of the list down
Insert item
Increment numItems