List Data Structures & Testing
Recall that an interface in Java defines methods but not implementations. My P6List is a little easier to implement than Java's List and it's a little more specific for the data structures we learned. These 11 methods already have stubs in the starter code for this assignment for all data structures.
public interface P6List<T> {
public T removeFront();
public T removeBack();
public T removeIndex(int index);
public void addFront(T item);
public void addBack(T item);
public void addIndex(T item, int index);
public T getFront();
public T getBack();
public T getIndex(int index);
public int size();
public boolean isEmpty();
}Where appropriate, you should throw my error classes instead of NullPointerExceptions or ArrayIndexOutOfBoundsExceptions. It is good programming practice to not expose those to your users, and it also demonstrates that you're reasoning about your code and its failure cases.
I provide errors for:
P6NotImplemented, so I can quickly tell if you have not changed the starter code in a particular case. You will be deleting these errors, not adding them.EmptyListError, when a remove or get operation is called on an empty list.BadIndexError, when a getIndex, addIndex or removeIndex operation is called with an index that does not exist.RanOutOfSpaceError, when an add method fails on aFixedSizeList.
Prefer the most precise error: EmptyListError rather than a BadIndexError when looking for the 5th thing in an empty list.
Writing good test code is likely to be redundant. This is OK, as it is a stylistic (opinion) choice. I have provided good test cases for most of FixedSizeList. In Lab, we will focus on getting the code-coverage of FixedSizeList to 100%.
Note that the maximum here is lower than usual. This assignment has many sections where you are implementing what was discussed in class, and therefore has far less room for interpretation and extra-credit work.
In some ways this assignment is much easier than past assignments. In other ways, it is much more difficult. Do not leave it until the last minute.
It is very important your code compiles and you do not change the directory structure. If you have issues importing the code into Eclipse, let me know and we can fix it together. I plan to grade these as automatically as possible.
I will not be grading your tests, but you must pass all of my tests.
This is newer, but I have completed part of the implementation for you.
We did a variation on this in Lab last week (where e.g., remove did not crash on an empty list). However, we have covered singly-linked lists in great detail.
Getting this right can be very tricky, even with tests. You may refer to algorithmic pseudocode, if you cite it.
Comment the methods in FixedSizeList, GrowableList, SinglyLinkedList, DoublyLinkedList and ChunkyLinkedList with their big-O efficiency, where O(n) is the size of the list.
This is a data structure described in the comments and in the partial code given. Work on this after you have implemented SinglyLinkedList for reasons that will become obvious if you open the code :) The closest reference I've found for this data structure online is the so-called Unrolled Linked List on Wikipedia. We're not making our own "Node" class for ChunkyLinkedList, but it's roughly the same idea.
I have made SinglyLinkedList<T> an associated class Iter<T> which knows how to loop over that list. SinglyLinkedList<T> implements (therefore is-a P6List<T> but also is-a Iterable<T>) this means that in the provdied ChunkyLinkedList.size(), I can use a for loop to iterate over the chunks in the list. The for loop works on anything that is-a Iterable<T>. Read about Iterator and Iterable and understand my implementation. Doing this for DoublyLinkedList will be fewer points than doing it for FixedSizeList and GrowableList because the implementation will be very different for the array-based lists.