CPSC 170 Lab 8: Linked Lists
- 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.
- 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
- Add code for the constructor. It should initialize variables
front, count, and generator.
- 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.
- Add code for method toString. Like the array version, it
should return a string containing the toString of each element,
separated by newline characters.
- 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.
- 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.
- 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
- 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
- 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.
- 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.
- 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
Turn in hardcopy of your completed AddNode, LinkedIterator, LinkedBag and
TestLinkedBag classes. Tar up your lab8 directory and e-mail it
to me with cpsc170 lab8 in the Subject line.