|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
Program 
defines the __init__ method
of the OrderedListAsArray class.
In addition to self,
the __init__ method takes a single argument which specifies
the length of array to use in the representation of the ordered list.
Thus if we use an array-based implementation,
we need to know when a list is declared
what will be the maximum number of items in that list.
The __init__ method initializes the _array variable as
an array with the specified length.
The running time of the __init__ method is clearly O(n),
where 
.
Program defines the insert method
of the OrderedListAsArray class.
The insert method is implemented by all searchable containers.
Its purpose is to put an object into the container.
The obvious question which arises is,
where should the inserted item be placed in the ordered list?
The simple answer is, at the end.
Program: OrderedListAsArray class insert method.
In Program we see that the insert
method simply adds the new item to the end of the list,
provided there is still room in the array.
Normally, the array will not be full,
so the running time of this method is O(1).
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.