CS1027b Computer Science Fundamentals II

Learning Outcomes

• Design simple programs that manipulate linked lists and double linked lists.
• Find and fix errors in programs that manipulate linked lists.

General Lab Instructions

• Read through the lab instructions before coming to the lab.
• Read the lecture notes on linked lists.
• Download file AnswersLab8.txt and open it with a text editor.

IMPORTANT. Make sure you attend the lab session to which you registered, show the result(s) of each exercise to your TA, and submit the .java files that you wrote and AnswersLab8.txt through OWL by 11:55pm on the same day as your lab session to get your marks for the lab.

Exercise 1: Removing a node from a singly linked list

• Download the file RemoveLinkedList.java from the course webpage. It contains a main method that
  1. Builds a linked list of integers from 1 to 5
  2. Prints the values stored in the nodes of the list
  3. Invokes method remove to delete from the list the node storing the value 3
  4. Prints the values stored in the nodes of the list to verify that the value 3 was indeed removed.
• In order to run this program, you will also need to download LinearNode.java.
• Run the program and see what is printed out.
Note that the program has a bug as the node storing the value 3 is not deleted from the list.
• Use Eclipse's debugger to find out which part of the program is incorrect. If you need help with this, read the following hints.
• Explain what is wrong with the program. Indicate which method is incorrect and where the error is. Write your answers in AnswersLab8.txt.
• Fix the program and run it again to verify that the node storing the value 3 was removed.
• Modify the main method so that after removing the node storing the value 3 and printing the values stored in the list, method remove(1) is invoked and then printElements() is invoked.
  Run the program and verify hat the value 1 was removed from the list. If your program crashes, use the debugger again to find the error and fix it.
• Add to the main method invocations to the method remove to also remove the values 2, 4, and 5 from the list, so the list is empty; then invoke the method printElements() to verify that the list is empty.
  The program will crash. Read the error message printed by the virtual machine. Which exception was thrown? In which method was the exception thrown? To what other method was the exception propagated? Write your answers in AnswersLab8.txt.
  Explain what the error is (if you are not sure about why the exception is being thrown, use the debugger to find out). Write your answer in AnswersLab8.txt.
• Fix the error and run the program. Show your program to your TA.

Exercise 2: Completing the DoublyLinkedStack class

• Download from the Code page of the course webpage the java classes DoublyLinkedStack.java, TestStackDLL.java, DoublyLinkedList.java, StackADT.java, and EmptyCollectionException.java.
• Fill in the missing code in method toString of class DoublyLinkedStack so that it returns a string of the form "Stack: value_1, value2_, ..., value_n", where "value_1" is the value stored at the bottom of the stack, "value_2" is the second value from the bottom of the stack, and "value_n" is the value at the top of the stack.
  For example, if in an empty stack we push in order the following integer values: 1, 2, and 3, the value 1 would be at the bottom of the stack and the value 3 would be at the top of the stack. Method toString would return in this case the string "Stack: 1, 2, 3".
  Notice that class DoublyLinkedStack implements a stack using a doubly linked list. Instance variable top points to the first node of the linked list; the linked list can be traversed forward using method getNext and it can be traversed backwards using method getPrevious from class DoublyLinkedList.
  Please try to write the algorithm on your own. If you need help you can read this hint.
• Run TestStackDLL. A null pointer exception will be thrown. Use the debugger to find out which statement throws the exception and why. Explain where and why the exception was thrown. Write your answers in AnswersLab8.txt.
• Fix the error and run TestStackDLL. It must print "Stack: 0, 1, 2, 3, 4".

Exercise 3: Adding a node to a doubly linked list