Inserting an Item at an Arbitrary Position

Two methods for inserting an item at an arbitrary position in an ordered list are declared in Program --insertBefore and insertAfter. Both of these take one arguments--a Comparable object. The effects of these two methods are illustrated in Figure .

  
Figure: Inserting an item in an ordered list implemented as an array.

Figure  shows that in both cases a number of items to the right of the insertion point need to be moved over to make room for the item that is being inserted into the ordered list. In the case of insertBefore, items to the right including the item at the point of insertion are moved; for insertAfter, only items to the right of the point of insertion are moved, and the new item is inserted in the array location following the insertion point.

Program  gives the implementation of the insertAfter method for the OrderedListAsArray.MyCursor class. The code for the insertBefore method is identical except for one line as explained below.

  
Program: OrderedListAsArray.MyCursor class insertAfter method.

The insertAfter method takes one arguments--a Comparable object. The method begins by performing some simple tests to ensure that the position is valid and that there is room left in the array to do the insertion.

On line 19 the array index where the new item will ultimately be stored is computed. For insertAfter the index is as shown in Program . In the case of insertBefore, the value required is simply offset. The loop on lines 21-22 moves items over and then object being inserted is put in the array on line 23.

If we assume that no exceptions are thrown, the running time of insertAfter is dominated by the loop which moves list items. In the worst case, all the items in the array need to be moved. Thus, the running time of both the insertAfter and insertBefore method is O(n), where .

Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.