Inserting an Item at an Arbitrary Position

Data Structures and Algorithms with Object-Oriented Design Patterns in Python

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. In addition to self, both of these take one argument, obj, the object to be inserted. 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.Cursor class. The code for the insertBefore method is identical except for one line as explained below.

program9051
Program: OrderedListAsArray.Cursor class insertAfter method.

In addition to self, the insertAfter method takes one argument, obj. 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 11 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 13-15 moves items over and then object being inserted is put in the array on line 16.

If we assume that no exceptions are raised, 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 .