CPSC 170 Lab 8: Linked Lists

1. File AddNode.java contains a simple program that creates a list with one element, then calls method addSecondNode several times to insert an element after the first item in the list (this is the same task as the last problem on your prelab). File LinearNode.java contains the LinearNode class we discussed in class. Save both of these to your directory. Fill in the code for addSecondNode in the AddNode class and test your program. You don't need to modify LinearNode.java.

2. We talked in class about the BagADT interface and the ArrayBag implementation of that interface. You now have the tools you need to write most of a linked bag implementation. File LinkedBag.java contains a skeleton for this class -- it contains instance variables front and size, along with empty (or trivial) bodies for each method in the BagADT interface. Save it and BagADT.java to your directory and modify LinkedBag as described below.
   1. Add code for the constructor. It should initialize variables front, count, and generator.

   2. Add code for method add. No order is specified in a bag, and the easiest place to add to a linked list is at the front, so put the element there. Remember that you will have to create a node to put it in.

   3. Add code for method toString. Like the array version, it should return a string containing the toString of each element, separated by newline characters.

   4. File TestLinkedBag.java contains a program that creates a linked bag, adds some items to it, and prints it. It uses only the add and toString methods of the Bag ADT, so you can save it to your directory and use it to test your LinkedBag class so far. Be sure it works correctly before you go on.

   5. Add code for method contains. Be sure to use the equals method of each element to determine whether it is the same as the parameter. Then modify TestLinkedBag so that it reads in a string from the user and prints a message indicating whether or not it is in the bag.

   6. Add code for the isEmpty and size methods. Modify TestLinkedBag so that it calls them and prints their results both when the bag is empty (before you put anything in it) and after you add several items.

   7. Add code for the removeRandom method. (The other remove method is somewhat more difficult to write, so we'll skip it for now.) Like the array version, you will need to generate a random integer between 0 and size-1 to determine which element to remove -- if you generate integer i, you'll remove the ith item in the list. Then walk down the list until you get to the node before the one to be removed and take it out of the list. (Be sure you understand why you have to stop one before the one you want to remove.) Note that it's a special case when you remove the first element -- this is the only case in which you modify front.

   8. Modify TestLinkedBag so that after looking for items in the bag, it repeatedly removes random elements until the bag is empty. Print each item as it is removed.

   9. The remaining methods (addAll, union and equals) require an iterator, so we'll write it next. File LinkedIterator.java contains the skeleton for a general iterator on a linear linked structure. Fill in the bodies of the methods -- you may want to refer to the ArrayIterator class, but of course here you are manipulating a linked list, not an array. Then use your LinkedIterator class to write the iterator method in the LinkedBag class. To test it, add code to TestLinkedBag that uses an iterator to print the elements of the bag all on the same line, with spaces between elements. (You'll have to import java.util.Iterator to have access to the Iterator class.) Do this just before you remove all of the items from the bag.

   10. Now add code for method addAll. This looks a lot like the addAll method in ArrayBag! To test it, add code to TestLinkedBag that creates a second bag, puts a couple of items in it, adds it to the first bag, and prints both bags.

What to turn in