Inserting and Accessing Items in a List

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

Inserting and Accessing Items in a List

Program gives the code for the constructor, Insert method, and this[int] indexer of the OrderedListAsLinkedList class. The constructor simply creates an empty linked list. Clearly, the running time of the constructor is O(1).

program9495
Program: OrderedListAsLinkedList class constructor, Insert method, and this[int] indexer.

The Insert method takes a ComparableObject and adds it to the ordered list. As in the case of the ArrayAsLinkedList class, the object is added at the end of the ordered list. This is done simply by calling the Append method from the LinkedList class.

The running time of the Insert method is determined by that of Append. In Chapter this was shown to be O(1). The only other work done by the Insert method is to add one to the count variable. Consequently, the total running time for Insert is O(1).

Program also defines an indexer that provides a get accessor which takes an argument of type int. This method is used to access elements of the ordered list by their position in the list. In this case, the position is specified by a non-negative, integer-valued index. Since there is no way to access directly the element of linked list, the implementation of this method comprises a loop which traverses the list to find the item. The method returns a reference to the item, provided . Otherwise, i is not a valid subscript value and the method throws an exception.

The running time of the accessor method depends on the number of items in the list and on the value of the subscript expression. In the worst case, the item sought is at the end of the ordered list. Therefore, the worst-case running time of this algorithm, assuming the subscript expression is valid, is O(n), where .