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

Having determined the position of an item in an ordered list, we can make use of that position to insert items into the middle of the list. Two methods are specifically provided for this purpose--insertAfter and insertBefore. In addition to self, both of these take a single argument--the object to be inserted into the list.

program9521
Program: OrderedListAsLinkedList.Cursor class insertAfter method.

Program gives the implementation for the insertAfter method of the OrderedListAsLinkedList.Cursor class. This method simply calls the insertAfter method provided by the LinkedList class. Assuming no exceptions are thrown, the running time for this method is O(1).

The implementation of insertBefore is not shown--its similarity with insertAfter should be obvious. Since it must call the insertBefore method provided by the LinkedList class, we expect the worst case running time to be O(n), where .