Homework answers / question archive / CompSci 351/CompSt 751: Data Structures & Algorithms Homework #6 This assignment will focus on the concepts of generics, and doubly-linked lists with dummy nodes in a collection class

CompSci 351/CompSt 751: Data Structures & Algorithms Homework #6 This assignment will focus on the concepts of generics, and doubly-linked lists with dummy nodes in a collection class

Computer Science

Share With

CompSci 351/CompSt 751: Data Structures & Algorithms Homework #6

This assignment will focus on the concepts of generics, and doubly-linked lists with dummy nodes in a
collection class.
Use this link to accept the assignment:
https://classroom.github.com/a/o9dnO44H
1 The Data Structure
For this homework, you will implement a generic implementation of the standard collection interface using
a cyclic doubly-linked list with a dummy node. The elds of the class should be exactly the following:
dummy The dummy node (never null).
count The number of elements in the collection.
version A version stamp to implement fail-fast semantics.
The nodes should be doubly linked: every link in the forward direction (p.link == q) should be re ected by
a link in the reverse direction (q.prev == p). There should be no null pointers in these links, which makes
the programming simpler. (The data in the nodes can be null, of course.) The data eld of the dummy node
should be assigned the \impossible" value of itself, that is (dummy.data == dummy) should be true. None of
the non-dummy nodes should have this data value. Finally the \count" eld should be one fewer than the
number of nodes in the (cyclic) list.
The list contains a dummy node even when it represents an empty collection. At the start, when the
collection is empty, the next and prev elds of the dummy node will point back to the dummy node. After
elements are added, the dummy node's next pointer refers to the rst (non-dummy) node in the list and the
prev pointer refers to the last node in the list.
2 Generics
In some earlier programs, you may have used generic classes. This week you will be creating your own
generic class, LinkedCollection. The purpose of this is to familiarize you with making classes that are not
limited to a specic element type. Inside the generic class, you can use type parameter E everywhere where
an explicit type would be used (e.g., Transaction in Homework # 4). Furthermore, since the Node class is
also generic, you must create instances of Node using this parameter as in new Node<E>(...).
3 The methods
As usual, you should only override the methods that need to be overridden for Java reasons (\required"),
correctness (\implementation") or eciency.
In this homework, you will nd that one of the methods implemented by AbstractCollection almost
always does the right thing, but needs to be overridden for a special case. Otherwise the overriding can call
super.methodName(...) to do the work. This kind of overriding should be commented as // decorate
because it only adds a little bit to the superclass implementation.
Don't use any auxiliary structures (arrays or other collections) to do the work of any methods. We also
don't require, or even recommend that you implement a clone() method.
You may optionally override the toString method for debugging purposes. We have no tests of toString
this time.
4 The Iterator
As with Homework #3, the collection's iterator will be \addable." Since it is a nested non-static class, it
should not have its own generic parameter. Instead it will use the outer class' generic type parameter. It
will implement Iterator with the generic parameter from the outer class.
The iterator should have the following data structure:
cursor The pointer to the node with the element that was last returned by \next" until/unless that
element is removed, in which case it moves back to the previous node. In all cases, the \next" element
(if any) will be the one in the node after the cursor. When the iterator is initialized, the \cursor" starts
on the dummy node. If the node after the cursor is the dummy node, then there is no next element.
isCurrent This boolean is true if the cursor is pointing to a node with the current element (the one
that can be removed). It should never be true that the dummy's data could be removed.
colVersion The version of the collection that this iterator can work with. It is used to implement
fail-fast semantics.
You will need to implement wellFormed for the iterator (as well as for the main class) that checks this data
structure. You should be able to gure out the conditions. Make sure to follow the convention we gave you
in Homework #3|checking the outer invariant rst and then checking for version mismatch. Remember
that if the version does not match, the the invariant is assumed to be true.
5 What You Need To Do
We recommend you proceed in the following manner:
1. Add the required data structure elds, methods and nested classes to LinkCollection.java so that all
errors are gone. In particular, the Spy class should compile without errors, and without being changed.
2. Write the wellFormed methods, using TestInvariant.
3. Implement methods needed to pass the TestDirect and TestLinkedCollection tests. (Recall that
TestCollection is an abstract class and should not be run.)
4. Make sure that every method you add is either @Override with a reason (one of the four: required,
implementation, eciency or decorate) or has a full documentation comment (with @param, @exception
and @return parts if appropriate).
5. Use random testing to nd any remaining implementation errors.
6. Use eciency testing to determine any additional overridings that may be necessary. After passing
eciency testing, check that no bugs have been introduced by running random testing again.
There are no locked tests in this assignment.
Your class should use the same style as in the previous homework assignments: it should assert the
correctness of the invariant at the beginning and end of any method that could change the state of the data
structure, and at the beginning of every public method. The invariant should also be checked at the end of
the constructor and when the iterator invariant is checked.
Remember to update version numbers whenever the collection changes the number of elements.
The homework repository contains the following les:
src/TestLinkedCollection.java This driver tests the collection operations.
src/TestDirect.java
src/TestInvariant.java Test driver for invariants of list and iterator.
src/TestEciency.java Test driver that runs with larger data sets.