Data Structures and Algorithms
with Object-Oriented Design Patterns in Python|
The push, pop and getTop methods of the StackAsLinkedList class are defined in Program .
Program: StackAsLinkedList class push, pop and getTop methods.
The implementation of push is trivial. It takes as its argument the object, obj, to be pushed onto the stack and simply prepends that object to the linked list _list. Then, one is added to the _count variable. The running time of the push method is constant, since the prepend method has a constant running time, and updating the _count only takes O(1) time.
The pop method is implemented using the first property and the extract method of the LinkedList class. The first property is used to get the first item in the linked list. The first property get method runs in constant time. The extract method is then called to extract the first item from the linked list. In the worst case, extract requires O(n) time to extract an item from a linked list of length n. But the worst-case time arises only when it is the last element of the list which is to be extracted. In the case of the pop method, it is always the first element that is extracted. This can be done in constant time. Assuming that the exception which is raised when pop is called on an empty list does not occur, the running time for pop is O(1).
The definition of the getTop method is quite simple. It returns the first object in the linked list. Provided the linked list is not empty, the running time of getTop is O(1). If the linked list is empty, the getTop method raises a ContainerEmpty exception.