Homework answers / question archive / In this assignment we continue our investigation of implementing \sequence" ADTs

In this assignment we continue our investigation of implementing \sequence" ADTs

Computer Science

Share With

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 specically say
how to implement Sequence with linked lists. We will instead be implementing our version
of Sequence that keeps track of the location even when the current element is removed.
Use this link to accept the assignment:
https://classroom.github.com/a/xtHscnzd
1 The (New!) Implementation of TransactionSeq
The TransactionSeq class will have the same public declarations as the TransactionSeq you
implemented before (except no way to specify an initial capacity), but the data structure
(private elds) will be completely dierent. Declare a node class as a \private static
class" inside the class. Such a class (one declared inside another class) is called a \nested"
class. The node class should have two elds: the data (of type Transaction) and the next
node. It should have a constructor taking values for the data and next elds. The class
should have no other methods. Despite what it says in the textbook, do not write methods
in the \Node" class.
The design in the textbook starting on page 232 (225, 3rd ed.) has some redundancy
that isn't needed for eciency. This week's online activity will help you decide which of the
elds to make model elds: elds that are not stored but are conceptually part of the ADT.
For the model elds, you will declare private methods to compute their values on demand, if
these elds are needed. Then in the (public) methods, you should use the private method(s)
to avoid the need to re-compute the model eld(s).
Unlike in the past assignment, clone requires some (dicult!) work for you to do: the
list must be copied, cell by cell, and pointers of the clone made to point to the appropriate
copied nodes.
1.1 The Invariant
The invariant is more complex than in the previous implementation. It has the following
parts:
1. The list may not include a cycle, where the next link of some node points back to
some earlier node.
2. The precursor eld is either null or points to a node in the list. It cannot point to a
node that is no longer in the list|the node must be reachable from the head of the
list.
3. The eld manyNodes should accurately represent the number of nodes in the list.
SPring 2023 page 1 of 2
CS 351: Data Structures & Algorithms Homework #4
4. If isCurrent is true, the cursor must not be null. (You will determine that the cursor
isn't stored in a eld and instead be computed on demand.)
We have implemented the rst part for you; you should implement the other parts yourself.
You should do this early on in developing the implementation|it will help you catch bugs
as quickly as possible. We provide code to test the invariant checker.
Be very careful that you never change any elds in the invariant checker, wellFormed. It
is ONLY supposed to check the invariant and return true or false (with a report). It should
never change things.
2 Files
The repository includes the following les:
src/TestInvariant.java Tests of wellFormed.
src/TestTransactionSeq.java Same testss as in Homework #2, omitting locked tests.
src/TestEciency.java Eciency tests.
src/edu/uwm/cs351/TransactionSeq.java Skeleton le.
lib/homework4.jar JAR le containing the other ADTs, and random testing.
There are no locked tests for this homework assignment.