Data Structures and Algorithms
with Object-Oriented Design Patterns in Python|
The definitions of the __init__ and the purge methods of the StackAsLinkedList class are shown in Program . With a linked-list implementation, it is not necessary to preallocate storage space for the objects in the stack. Space is allocated dynamically and incrementally on the basis of demand.
The __init__ method simply creates an empty LinkedList and assigns it to the _list instance attribute. Since an empty list can be created in constant time, the running time of the StackAsLinkedList __init__ method is O(1).
The purge method of the StackAsLinkedList class simply calls the purge method of the LinkedList class. The purge method of the LinkedList class discards all the elements of the list in constant time. Consequently, the running time of the purge method is also O(1).