In class, we studied the
MyLinkedList class, which implements a doubly-linked list using the same techniques as Java's
LinkedList class. For this assignment, you will utilize inheritance to extend
MyLinkedList to try and improve its performance.
Define a class named
MidLinkedList that extends the
MyLinkedList class by maintaining a reference to the middle of the list. That is, there should be a field that references the middle node in the list. So, if there are 7 nodes in the list, the middle field will reference the 4th node. Assume that the middle rounds down, so the middle of 8 nodes is still the 4th node. The
getNode operation should be modified to take advantage of this middle reference, so that if
getNode is called with an index that is closer to the middle than to either end, then the traversal will start at the middle.
When defining your class, you should only override those methods that manage or take advantage of the middle reference. Note that the
MyLinkedList has been modified so that the fields, inner class
DNode, and helper method
getNode are now declared
protected. This allows for any methods in your derived class to access these parts of the class.
get operation always be faster for
MidLinkedLists (when compared with
MyLinkedLists)? If not, under what conditions would it be faster?
An average, how much faster would you expect the
get operation to be for
MidLinkedLists? Explain your reasoning, then design one or more drivers to test this hypothesis. You will need to turn in the driver(s), timings using the driver(s), and analysis of how the timings support or refute your hypothesis.
What is the Big-Oh efficiency of the
get operation? Explain your reasoning, then design one or more drivers to test this claim. You will need to turn in the driver(s), timings using the driver(s), and analysis of how the timings support or refute your claim.