|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
Program 
defines
and DequeueTail and getTail methods
of the DequeAsArray class.
Program: DequeAsLinkedList class dequeueTail and getTail methods.
The getTail method
returns the object at the tail of the deque.
The tail of the deque is in the last element of the linked list.
In Chapter we saw that the running time of
LinkedList.last property is a constant,
Therefore, the normal running time for this accesor is O(1).
The dequeueTail method removes an object from the tail
of the deque and returns that object.
First, it verifies that the deque is not empty
and throws an exception when it is.
If the deque is not empty,
dequeueTail saves the last item in the linked list
in the local variable result.
Then that item is extracted from the linked list.
When using the LinkedList class from Chapter ,
the time required to extract the last item from a list is O(n),
where 
is the number of items in the list.
As a result,
the running time of DequeueTail is O(n).
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.