Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Inserting an Item at an Arbitrary Position

Once 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. Both of these take a single argument--the ComparableObject to be inserted into the list.

   program9635
Program: OrderedListAsLinkedList.MyCursor class InsertAfter method.

Program gif gives the implementation for the InsertAfter method of the OrderedListAsLinkedList.MyCursor 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 tex2html_wrap_inline60465.


next up previous contents index

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