Your first task is to create a node class.
1-Create a file called SinglyLinkedNode.java and put it in a package named ser222.
2-Create a class (guess what it should be named) with private attributes value of type String and next of type SinglyLinkedNode.
3-Create a constructor for your class that takes two parameters, one for value and the other for next. Which order do you think I want the parameters listed? What do you think I want you to name the parameters?
4-Create public access functions getValue and setValue and getNext and setNext. What do you think getValue returns? Does setNext expect a parameter?
5-Test your node class by creating a main function in the SinglyLinkedNode class.
(a) Add a single line that asserts false (forcing an assertion to be raised). Then run your program with assertions enabled and verify that the assertion is indeed raised. Once you have verified that you can run java with assertions enabled, comment out the line that asserts false (do not delete it). Place a comment before the assertion indicating to the grader for this assignment that you have done item 5a.
(b) From within main, create three nodes named node1, node2, and node3. Use them to create a linked representation for the sequence < 1, 2, 3 >. What should node3.getNext() return? Add code to the main function that uses assertion to check that the result is correct. Run your java program to verify that it works as you expected. Add a comment just before the code that creates the nodes to indicate where the grader should look for item 5b.
(c) Now create a variable called head and make it a reference to node1. What should head.getNext().getValue() return? Use an assertion to verify that it returns what you expect. Run the program again before proceeding. Add a comment before the assertion so that the grader knows where to look when grading item 5c.

Singly Linked Stack
A Stack is a collection that only allows access to the most recently added item. You may only add new values ( push them) or remove items ( pop them) from the top of the stack. A stack is a Last In First Out (LIFO) collection. The
operate like a stack of bowls in a soup kitchen; you can place a bowl at the top of the stack or grab one from the top.
1. Create a java class ser222.SinglyLinkedStack.
2. GiveSinglyLinkedStackasingleprivateattributeheadoftypeSinglyLinkedNode
and assign it to null.
3. Create a push method that puts a new node at the front of the list.
4. Create a isEmpty method that returns true if no items are on the stack and false otherwise.
5. Create a toString method. It should return a left angle brace, followed by the values of each item in the stack, each separated by a comma. The last character output should be a right angle bracket.
6. The stack is not complete, but now I want you to create a main function to begin checking it before things get too complicated.
(a) Verify that a newly constructed stack is empty, using an assertion. Name your stack myStack. Run the program. Add a comment to the grader to indicate where you have done item 6a.
(b) . Verify that an empty stack, when converted to a string, is the string "<>". Test this using an assertion. Add a comment to the grader to indicate which code is addressing item 6b.
(c) Use an assertion to verify that, after pushing the string "A" onto the stack, it is not empty. Add a comment for the grader (continue to do so for all items).
(d) Use an assertion to verify that myStack.toString() is "".
(e) Use an assertion to verify that, after pushing another string "B" onto
the stack, it is not empty.
(f) Use an assertion to verify that myStack.toString() is "".
7. Create a top method that returns the value of first node from the list. Use an assertion to make sure that the stack is not empty when top is called.
8. Create a pop method that removes the first node from the list. Use an assertion to make sure that the stack is not empty when pop is called. The pop function should not return anything.
9. Continue editing the main function to cover the new code.
(a) Verify that the top of the myStack is "B" using an assertion.
(b) Pop the top item off of the stack, and then verify that the top of the stack is "A" and that the entire stack is now "".
(c) Pop the top item off of the stack and verify that the stack is empty.
(d) Use a try/catch block and a boolean variable in order to verify that an assertion fails if you try to pop from an empty stack. If popping from an empty stack does not cause the exception handler to execute, then you should assert false after the try/catch block.
(e) Verify that you can add the strings "s", "t", "u", "d", "e", "n", "t" and that the stack becomes "".
(f) Verify that you can pop seven items from the stack, and then it is empty.

Single Linked Queue
A queue is similar to a stack only it is a First In First Out (FIFO) collection. New items are always pushed onto the back, using an operation called enqueue. The only item you can access is the the item at the front of the queue, and you remove it with an operation called dequeue. A queue operates the way a line at a soup-kitchen would work, the first in line is the first one served.
1. Create a java class ser222.SinglyLinkedQueue. You should be able to deduce which package the class belongs to, and what the name of the Java file should be.
2. Give SinglyLinkedQueue a private attribute head of typeSinglyLinkedNode and assign it to null.
3. Give SinglyLinkedQueue a private attribute tail of typeSinglyLinkedNode and assign it to null. Why do you think I am asking you to store a ref- erence called tail? What should head and tail be when the queue is empty? When it has only one item? Two items?
4. Create a isEmpty method that returns true if no items are on the queue and false otherwise.
5. Copy the toString method from SinglyLinkedStack.
6. Create an enqueue method that puts a new node at the end of the queue.
Your enqueue method must be an Θ(1) worst-case operation,
7. The queue is not complete, but now I want you to create a main function to begin checking it before things get too complicated (if you haven't started it already).
(a) Verify that a newly constructed queue is empty, using an assertion. Name your queue myQueue. Add a comment indicating where you did item 7a.
(b) Verify that an empty queue, when converted to a string, is "<>". Test this using an assertion. Add a comment to help the grader locate the code.
(c) Use an assertion to verify that, after you enqueue the string "A" onto the queue, it is not empty. Add a comment to help the grader find your solution to this item (continue for all items)
(d) Use an assertion to verify that myQueue.toString() is "".
(e) Use an assertion to verify that, after you enqueue another strings "B"
and then "C" onto the queue, it becomes "".
8. Create a front method that returns the value of first node from the queue. Use an assertion to make sure that the queue is not empty when front is called.
9. Create a dequeue method that removes the first node. The dequeue function should not return a value. Use an assertion in tbe function to make sure that the queue is not empty when dequeue is called. Make sure you implement it in such a way that the worst-case running time is Θ(1).
10. Continue editing the main function to cover the new code.
(a) Verify that the front of the myQueue is "A" using an assertion.
(b) Dequeue the first item from the queue, and then verify that the front of the queue is "B" and that the entire queue is now "".
(c) Dequeue and then verify that the queue is "".
(d) Dequeue and then verify that the queue is "<>".
(e) Verify that an assertion fails if you try to dequeue from an empty queue. If and only if an assertion is not raised by dequeue, then raise one from main.
(f) Verify that you can add the strings "s", "t", "u", "d", "e", "n", "t" and that the queue becomes "".
(g) Verify that you can dequeue seven items from the queue, and then it is empty.

Wrapping it up
This activity used a very simplistic method to test your code using assertions from a main function. In other situations you will most likely use a unit testing framework such as JUnit to accomplish that goal and also generate reports. We also made sure that we only produced a very small piece of code before running a test that covered the code we just added. This is an important part of managing code with data structures that can become complicated. Our tests were automated in the sense that they required no user input, and they were cumulative so that when we added new code we could rerun the old tests in addition to new ones and made sure we did not break anything.
We did not handle the more complicated operations on linked lists in this activity (deleting or inserting form an arbitrary position in a list). Neither did wo experiment with other variants such as a doubly linked list or a circularly linked list or a list with a dummy node.