CSC 321: Data Structure
Fall 2013

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: Implementing the class

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.

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?

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.

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.