Positions of Items in a List

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

Positions of Items in a List

Program gives the definition of a the OrderedListAsLinkedList.MyCursor private nested class. The MyCursor class implements the Cursor interface defined in Program . The purpose of this class is to record the position of an item in an ordered list implemented as a linked list.

program9580
Program: OrderedListAsLinkedList.MyCursor class.

The MyCursor class has two fields, list and element. The list field refers to an OrderedListAsLinkedList instance and the element refers to the linked-list element in which a given item appears. Notice that this version of MyCursor is fundamentally different from the array version. In the array version, the position was specified by an offset, i.e, by an ordinal number that shows the position of the item in the ordered sequence. In the linked-list version, the position is specified by a reference to the element of the linked list in which the item is stored. Regardless of the implementation, both kinds of position provide exactly the same functionality because they both implement the Cursor interface.

The Datum property of the OrderedListAsLinkedList.MyCursor class is also defined in Program . This property provides a get accessor that dereferences the element field to obtain the required item in the ordered list. The running time is clearly O(1).