Data Structures and Algorithms with Object-Oriented Design Patterns in Python
next up previous index

push, pop and getTop Methods

The push, pop and getTop methods of the StackAsLinkedList class are defined in Program gif.

   program5445
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.


next up previous index

Bruno Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.