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.
Will the get
operation always be faster for MidLinkedList
s (when compared with MyLinkedList
s)? If not, under what conditions would it be faster?
An average, how much faster would you expect the get
operation to be for MidLinkedList
s? 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 MidLinkedList
's 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.