CPSC 170 Lab 8: Linked Lists
As usual, create a lab8 subdirectory for today's lab, open this
document in Netscape, and start emacs.
File IntList.java contains the definitions
for a linked list of integers that we discussed in class today. In
addition to inner class IntNode, which holds information for a
single node in the list, the following IntList methods are defined:
- public IntList() -- constructor; creates an empty list of integers
- public void addToFront(int val) -- takes an integer and puts it on
the front of the list
- public void addToEnd(int val) -- takes an integer and puts it on
the end of the list
- public void removeFirst() -- removes the first value from the list
- public void print() -- prints the elements in the list from first to last
File IntListTest.java contains a driver
that allows you to experiment with these methods, much as we did in lab 5.
Save both of these files to your directory, compile and run IntListTest, and
play around with it to see how it works. The do the following
exercises.
- Replace the while loops in addToEnd and print with for
loops. Test your revised methods to be sure they work. Think about which
style you are most comfortable with.
- Add the following methods
to the IntList class. For each, add an option to the driver to test it.
- public int length() -- returns the number of elements in the list
- public String toString() -- returns a String containing the print value
of the list.
- public void removeLast() -- removes the last element of the list. If
the list is empty, does nothing.
- public void replace(int oldVal, int newVal) -- replaces all
occurrences of oldVal in the list with newVal. Note that you can still
use the old nodes; just replace the values stored in those nodes.
- public void printRec() -- prints the list from first to last
using recursion. Hint: Use a helper method.
- public void printRecBackwards() -- prints the list from last to first
using recursion. Hint: Printing backward recursively is just
like printing forward recursively except you print the rest of the list
before printing this element. Simple!
- A list of objects is a lot like a list of integers, except the value
stored is an Object, not an int. Write a class ObjList that contains
arbitrary objects and that has
addToFront, addToEnd, removeFirst, removeLast, and print methods similar
to those in IntList. Note that you won't have to write all of these
again; you can just make very minor modifications to your IntList methods.
Also write an ObjListTest class that creates an ObjList and puts
various different kinds of objects in it (String, array, etc) and then
prints it. (Don't bother with a general driver like we used for IntList.)
HAND IN:
- Hand in hardcopy of your IntList.java, IntListTest.java, ObjList.java, and
ObjListTest.java files.
- Tar the files in your lab8 directory and email the .tgz file
to me (bloss@cs.roanoke.edu).