Lab 5: Linked Lists

This lab will be a little different than we have been having. There are two parts to it: the part to be done in lab, and the homework part.

Part I: Do in lab

During today's lab, you are going to work with a generic linked list package. The linked list is a circular, doubly linked with a dummy header node. Before beginning the lab, download the following two files and put them into a project called IntroLinkedLists. List5.java, and UseList5.java, Open them in the BlueJ compiler. You will need to look at them to do the lab.

Familiarize yourself with the code in these files and then do as many of the following as you can in the time permitted. (No one is expected to do them all) The first is mandatory, you may choose to do the others in any order you wish. You must turn in your drawing and code at the end of lab.

What to do

1. Understand the code
   • On a sheet of paper, walk through Initialize( ) in the List5 class (when it is called in the UseList5 class), drawing the new node created and the pointers.
   • Then add four nodes using Insert( ), reassigning the pointers as directed by the code. (This without a doubt will take some erasing and redoing until you figure out exactly what the code is doing.)
   • Keep this paper to hand in; it should be reasonably neat, showing how four nodes in the linked list are connected. Perhaps you should use pencil, so you can erase arrows when pointers are reassigned.
   • It is expected that you will spend about an hour on this part of the lab. Do not get impatient if it takes a while to figure out.

2. Modify some of the code.You have several options of methods to modify. Choose the one you think will be the easiest, then modify that method. Do others if you have time.
   • Change the Insert( ) method so that it does not allow an element that is already in the linked list to be inserted again. In this case an appropriate error message should be printed. Add some statements to UseList5 to check your changed method.

   • Change the Insert( ) method so that it keeps the elements in sorted order as they are inserted

   • Add an method called Print_Backwards( ) that prints the elements in the linked list in reverse sorted order. Make sure that you don't print out the dummy header record!

   • Add an method called Remove ( ) that removes an element (if it exists) from the linked list. Remove should print a message stating whether or not the removal was successful.
Hand in:
• A printout of your modified code.
• A printout of runs of your changed methods showing that they do work.

Part II: Programming homework for the next two weeks

This is really a two week lab, but I want it done in stages:
Week October 16-23: Implement a Single-Linked List class and test it.
Week October 23-30: Modify your Single-Linked List class to be a Double-Linked, generic class, and test it.

Week October 16-23:


• Write a Node class for data type String, and a reference variable that points to an object of type Node
• Write a MyList class that implements a linked list. Put your Node class as an inner class of the MyList class. this class should implement the Comparable interface.
• The MyList class should implement the methods:
  • void addFirst(String item) // add an item to the front of MyList
  • void addLast(String item) // add an item to the end of MyList
  • void addSorted(String item) // add an item to the list, keeping it in sorted order.
  • String removeFirst() // remove the first item in MyList
  • String removeLast() // remove the first item in MyList
  • int Size() // return the number of elements in the list
  • String toString() //override the toString method. The data in the list should be listed between square brackets with a comma between each item.
    
  • boolean equals(Object other) //override the equals method. Two lists are equal if they have the same elements in the same order.

• Suggtested procedure
  • Write the MyList class with the inner class Node, then be sure it compiles.
  • Write the addFirst method and test it
  • You do not have to write the methods in the order given. Write one method, then test it. Never have more than one method that is not tested and working correctly!
  • If you write the toString method early, it will make testing easier.

This part of the lab is due on October 23.

Week October 23-30:


• Modify your Single-Linked List class to be a Double-Linked, generic class, and test it.
• It should contain all the methods of the single-lined class
• Be sure that you do not overwrite the single-linked class when you start this assignment.