|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
Program 
gives
the code for the __init__ method
of the OrderedListAsLinkedList class.
The __init__ method simply creates an empty linked list.
Clearly, the running time of the __init__ method is O(1).
Program gives
the code for the insert and __getitem__ methods
of the OrderedListAsLinkedList class.
The insert method takes an object
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.
Program: OrderedListAsLinkedList class insert and __getitem__ methods.
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 the __getitem__ method.
In addition to self,
the __getitem__ method 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 raises 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 
.
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.