In this assignment we continue our investigation of implementing “sequence” ADTs. This week, it will be re-implemented using a linked-list. Read Chapter 4 carefully and especially make sure that you read Section 4.5, pages 232-238 (225-231, 3rd ed.) which specifically say how to implement Sequence with linked lists.
The HexTileSeq class will have the same public declarations as
the HexTileSeq you implemented before (except no way to specify an
but the data structure (private fields) will be completely different.
Declare a node class as a “private static class”
inside the HexTileSeq class.
Such a class (one declared inside another class)
is called a “nested” class.
The node class should have two fields: the
data (of type
HexTile) and the next node.
It should have a constructor but no other methods.
Despite what the textbook recommends, do not write methods in
the “Node” class.
We will use the textbook's recommended design starting on page 232 (225,
3rd ed.) for the fields of the HexTileSeq class.
Unlike in the past assignment,
requires some substantial work for you to do: the list must be
copied, cell by cell, and
tail pointers of the
clone made to point to the appropriate copied nodes.
Please read the textbook's section “Revised Sequence ADT--Design Suggestion” for information on the fields. There is a slight difference with the “precursor” pointer. The “precursor” field records the node before the current point in the sequence. If we are at the start of the sequence, then the precursor is null, since there is no node before the first one. In later assignments, we will see how using a “dummy” node can simplify the logic, avoiding this special case. If there is no current element, the precursor points to the last node (unlike in the textbook where it points to null).
The invariant is more complex than in the previous implementation. It has the following parts:
nextlink of some node points back to some earlier node.
manyNodesshould accurately represent the number of nodes in the list.
tailpointer points to the last node in the list (if any).
Be very careful that you never change any fields in the
wellFormed. It is only supposed to
check the invariant and return true or false (with a report).
It should never change things.
homework4.git includes the following files:
About this document