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.
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).
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
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
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.
get operation always be faster for
MidLinkedLists (when compared with
MyLinkedLists)? If not, under what conditions would it be faster?
On 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.