CS 221 Lab--Introduction to Linked lists
Fall 2006
Lecture Schedule
TA (Sam Gardner) page
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
- 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.
- 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