CSCI 162 — Lab 5

Due: Sunday October 28, 2018 @ 11:59PM

Sequence (Linked List)

Handout Code is available HERE

Goals

Overview

In this assignment, you will build the sequence class using a generic linked list as the representation instead of an array.

Linked List

The class should also be generic which allows users to have elements of different types such as String:

String Linked List

We're giving you the fully commented class outline. This project is discussed in the text beginning on page 232. Your notes concerning generics, Chapter 5 (especially sections 5.3 and 5.4), and Appendices E and F may be helpful.

Understand the data representation and keep the class invariant in mind.

The pictures above show the five instance variables, although we will replace "manyNodes" with "size". As in the first sequence assignment, it is important to understand the data representation and the method specifications. Know the class invariant and maintain it in each method. There are a multitude of JUnit tests to help you find bugs.

Provided Files

The handout contains the three files LinkedSequence.java, Node.java, and TestSeqLL.java. These files compile cleanly except for the unavoidable warning on the clone method. After you copy the directory and create a new project, build the project and run the JUnit tests. Then start making changes. If it doesn't build and run, clean and build again. Be sure you've added the JUnit library to your build path.

The Node.java file contains a generic node class implementation. This class only has two constructors. The node elements are generic and the type must be specified when a node is created. However, you will be using it within a generic class. Therefore, you can refer to the nodes generically as in this example:

head = new Node<E>(element, head);

The TestSeqLL.java file contains JUnit tests for the LinkedSequence class. Your class should pass ALL the tests with no failures.

Finally, the LinkedSequence.java file contains the start of the implementation for the generic sequence class. The clone and toString methods are already implemented. Do NOT modify them. The clone method gives an unavoidable warning. There should be no other warnings in your code.

Carefully read the pre- and post-conditions for the sequence methods. In particular, if there is no current item, addBefore places the item at the front, and addAfter places the item at the end. There are five instance variables as discussed in the text. Your implementation must match the specification described in the comments.

Your code should throw IllegalStateException as noted in the comments. The other exceptions will happen or not, and you do not need to add code to detect, throw, or handle them.

About the Class Representation

To implement the class, you must understand how the instance variables represent the object's state. You need to know the class invariant. We include it below. It is a long comment in LinkedSequence.java. "precursor" will be very useful for add and remove operations. Remember to update both "precursor" and "cursor" in the "advance" operation and to set "precursor" to null and "cursor" to "head" in the "start" operation.

CLASS INVARIANT

* the number of items in the sequence is maintained in size

* head points to the first node, if any, or it is null

* tail points to the last node, if any, or it is null

* if there is a current item, cursor points to it and precursor points to the node before it, if any

* if there is no current item, cursor and precursor are both null

How to Get This to Work

Start EARLY and work on it consistently.

You cannot do this assignment in a couple of hours. Getting it to compile is not enough. Think through what each method needs to do. Do this thinking AWAY from the computer.

Don't try to do it all at once.

Get one of the item adds ("addBefore" or "addAfter") and the basics working. Then do the other item add. Then do the remove or the container adds.

Draw pictures.

Have plenty of scratch paper and draw pictures of what you are trying to do in each method. Draw an empty sequence. Show all five instance variables. Draw a one-node sequence created by an "addBefore". Where does "cursor" point? How about "precursor"? If you apply an "advance" operation, where do they point? Now if you "addBefore" again, what does it look like? You did put the new node at the front, right? Draw pictures studying what happens when.

If you have the sequence of doubles on the front of this handout, where would an "addBefore" put the node? What instance variables would be updated? What would the values of "cursor" and "precursor" be when you were done? What would happen if you did an "addAfter" instead? We can't say enough about drawing pictures. Have paper and pencil beside you at all times.

Understand the specification.

Know what each method should do. Check the pre-conditions and throw an IllegalStateException if they are not met. Set all the instance variables in the constructor.

Check the class invariant.

Each time you complete a method, make sure the class invariant is true. Check every instance variable.

Consider all possibilities.

Does your code work on an empty sequence, a one item sequence with no current item, a one item sequence with a current item, a multi-item sequence with the current item at various places and no current item, and so forth? There is a checklist table on page 234 that might help. Often, doing something to the front item or the last item will be a different case. Consider the possibilities and handle them. Draw pictures.

REVIEW your code and SIMPLIFY.

After you have it working, set your code aside for a while. Come back to it and read each method. Does it make sense? Does it work? Is there a CLEANER way to write it? ELIMINATE special cases where you can.

Test the program and submit.

You should be able to get through all the JUnit tests in TestSeqLL with no errors. Run extra test cases. Just getting your program to compile is not enough — it has to work.

Submission

Submit this program as Lab 5: Sequence (Linked List)

Grading