CPSC 170 Lab 9: 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. (Remember the count variable that holds the number of items in the bag.) 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 the removeRandom method. Code for this method is in the text (Lewis and Chase); feel free to refer to it. Note, however, that the method given throws an EmptyBagException if the bag is empty, while you will simply return null. Look carefully at what this code does: after generating a random integer, it walks down the list until it gets to the node before the one to be removed, then takes it out of the list. Note that it's a special case when the first element is removed. We'll talk more about removing elements in class tomorrow.

   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. (LinkedIterator is also in the text, but it's different in several ways, so you're better off writing it yourself. You'll also learn more!) 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.

   11. Now add code for method union. This method is not paticularly well done in the ArrayBag class; think about the methods you have, and come up with a cleaner solution! To test it, union the two bags you already have and print the result. Remember that unlike a set, it's ok to have duplicate items in a bag.

   12. Finally, add the equals method. Study the ArrayBag version; how much of this can you use? To test your method, write a new test program TestEquals that that creates two new bags, asks the user to add items to each, and prints whether they are equal. Be sure to give the user enough flexibility to thoroughly test equals, including cases where one or both bags are empty, the bags are of the same size, and the bags are of different sizes.

What to turn in