CSC 321: Data Structure
Fall 2017

HW4: References & Inheritance


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.

Part 1: Extending the class

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.

Part 2: Comparing performances

Will the 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.

Part 3: Big-Oh efficiency

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.