|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
The running times calculated for the various
methods of the two sorted list implementations,
SortedListAsArray and SortedListAsLinkedList,
are summarized below in Table 
.
With the exception of two methods,
the running times of the two implementations
are asymptotically identical.
| sorted list implementation | |||
|
| SortedList- | SortedList- | |
| method | AsArray | AsLinkedList | |
| __contains__ | O(n) | O(n) | |
| find |  |  | O(n) |
| findPosition | | | O(n) |
| __getitem__ | O(1) | | O(n) |
| insert | O(n) | O(n) | |
| withdraw | O(n) | O(n) | |
| Cursor.datum | O(1) | O(1) | |
| Cursor.withdraw | O(n) | O(n) | |
Neither the SortedListAsArray nor SortedListAsLinkedList
implementations required any additional instance attributes
beyond those inherited from their respective base classes,
OrderedListAsArray and OrderedListAsLinkedList.
Consequently, the space requirements analysis
of the sorted list implementations
is identical to that of the ordered list implementations
given in Section .
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.