Inserting an Item at an Arbitrary Position

Data Structures and Algorithms with Object-Oriented Design Patterns in C#

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 ComparableObject. 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.

program9167
Program: OrderedListAsArray.MyCursor class InsertAfter method.

The InsertAfter method takes one argument--a ComparableObject. 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 18 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 20-21 moves items over and then object being inserted is put in the array on line 22.

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 .