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.
The MidLinkedList
class is intended to extend MyLinkedList
by adding a field that references the middle node in the list. For example, 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. By keeping track of the middle element, it should be possible to speed access to items in the list (since traversals can start in the middle of the list for indices that are closer to the middle than to either end).
The provided MidLinkedList
class extendss MyLinkedList
by adding the middle
field and overriding the add
method. You will need to similarly override the remove
method, so that it updates the middle
field as necessary when a value is removed from the list. You will also need to override the getNode
method so that it makes use of the middle
field and starts the traversal at the middle if the index is closer to the middle than to either end. Note that the get
, add
, and remove
methods of MyLinkedList
all utilize getNode
to access the appropriate node in the list, so overriding the getNode
method will automatically speed up all of these methods (without having to explicitly override them in MidLinkedList
).
Be sure to test your modifications thoroughly. Adding temporary print statements to the methods, showing the contents of the list and the middle value, can be useful in verifying that each addition and removal update the middle
field correctly. Simlarly, temporary print statements in getNode
can verify that the appropriate traversal is used to access the specified index.
Will the get
operation always be faster for MidLinkedList
s (when compared with MyLinkedList
s)? If not, under what conditions would it be faster?
On 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.