As we mentioned in class, the LinkedList
class implements the Queue
interface efficiently, providing O(1) implementations of add
, remove
, and peek
. For the first part of this assignment, you will write a short driver program to experimentally verify these efficiencies. Your program should prompt the user for a size and construct a queue containing that many random values. It should then traverse the entire queue ten times, peeking at the front, removing the front, and adding it to the back each time. For example, if the queue contained 1,000 values, a single traversal of the list would perform the peek-remove-add sequence 1,000 times. Ten traversals of the list would result in 10,000 of each operation. Your program should time how long it takes to make these ten traversals using the provided
StopWatch class. Be aware that a StopWatch
measures clock time, which is affected by many factors other than code execution (e.g., background jobs, garbage collection). To minimize these factors, limit background jobs and also perform multiple timings to identify and disregard outliers.
For example, execution of your program might appear as follows (with the timing being purely fictional):
Enter the queue size: 10000 Time (in msec): 5
Since each peek
, remove
, and add
operation on a LinkedList
is O(1), and your program is doing 10*N of each operation (where N is the size of the queue), you would expect the overall program to exhibit O(N) performance. Extend your program to help verify this. In particular, prompt the user for an initial queue size, and repeatedly double that size until it reaches an upper limit (also specified by the user). Display the sizes and timings for each generated queue.
For example (also with fictional timings):
Enter the initial queue size: 10000 Double the size up until: 200000 list size time (in msec) --------- -------------- 10000 5 20000 6 40000 8 80000 9 160000 11
Run your program on list sizes sufficient to demonstrate a reasonable and consistent pattern, and record the timings in a separate document. Do these experimental timings demonstrate the expected patterns for an O(N) algorithm? Justify your answer in the document.
What we would like to do next is compare the LinkedList
implementation of a Queue
with an ArrayList
based one. We could implement our own class from scratch that has an array as a field and provides all the methods required by the Queue interface. There is a simpler way, however. The existing ArrayList
class already has methods for adding, removing, and looking at elements in an array. We can use inheritance to extend this class, building on existing methods to implement the required Queue
methods. For example, the definition of the offer
method in the new class ArrayQueue
is provided below:
Complete the definition of the ArrayQueue
class so that it fully implements the Queue
interface. Then modify your program so that it utilizes an ArrayQueue
instead of a LinkedList
. Note that this should require change to only one line of code.
Since the remove
method for ArrayQueue
is O(N), you would expect this version of your program to be significantly slower than the original version. Do your timings confirm this? What would you expect the Big-Oh efficiency of this modified program to be? Is that supported by your timings? Use your program to generate a table of timings and justify your answers based on those timings.