|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
Program 
gives the definition of a the
OrderedListAsLinkedList.Cursor nested class.
This class extends the abstract Cursor class
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.
Program: OrderedListAsLinkedList.Cursor class __init__ and getDatum methods.
The Cursor class has two instance attributes, _list and _element. The _list instance attribute 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 Cursor 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 methods defined in the abstract Cursor class.
The getDatum method
of the OrderedListAsLinkedList.Cursor class
is also defined in Program .
This method dereferences the _element instance attribute
to obtain the required item in the ordered list.
The running time is clearly O(1).
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.