Programming Lab #3:
Assigned: Wed 1 Apr 1998
Due: Thu 9 Apr 1998
For this project you will write a program which:
Your implementation should create an empty DLL for the user when it is first
started up, and then accept commands to traverse or modify the list. You only
need to create a single list (conceptually, creating several should be easy in
an object-oriented environment). Your list should be generic, but for the purposes
of the lab we will just use integers via the "MyInteger" wrapper.
This assignment is based on the one given in the Weiss text as Programming Project
16.14 on page 452 of the text, although with a couple of additions for advancement
and printing.
Note I am not requiring that you implement a DCL, or doubly-circularly
linked list; however, you may do so if you wish. If so, you should be prepared to
describe (in person at demo time and on paper for the hard-copy version) what
differences were motivated by this change, including e.g. changes in the command
structure and error conditions. Implementation of the DCL will not count as extra
credit, but should be motivated by your own desire for some extra fun.
For details on the methods you should support, the command-line interface,
error reporting, etc., see below.
Note that it will be helpful to consult the textbook for information on
implementation techniques.
The following provides some more explanation about each of the methods
listed in the textbook. You should write a class (say,
Note also that, just as for the linked list iterator class given in the text on
page 400, your insertion and removal methods should throw an ItemNotFound
exception.
Regarding command syntax, let's use single- or double-character commands,
corresponding to the method names as follows:
No arguments to these commands.
No arguments to these commands.
No arguments to these commands.
These should take a single integer parameter (give an error if none is given).
These should take a single integer parameter (give an error if none is given).
No arguments to these commands.
No arguments to these commands.
Note that the use of the "R" character for a single-character command as well as
for the beginning of a double-character command makes parsing a little more
difficult.
Here is a sample run showing typical input/output (you should feel free to use
appropriate introductory text and prompts of your own design):
Your project will be assessed on the basis of both a "live" demonstration
and a hard copy description and print-out of the project code.
The printed version
should specify both members of your group and should specifically mention any free
late days used, remaining problems or bugs, special enhancements, etc. In addition
to "raw code", you should include a brief introduction describing anything that is
special in your approach to the problem (bugs, enhancements, etc., should also be
mentioned here).
Your grade will be determined in part by the correctness of your code, but also
by virtue of the techniques you use to implement it.
I will be available in lab on Monday mornings from 10:00 - 11:30 for demonstrations.
You may also demonstrate at other times (Thursday morning office hours will likely
be popular), including by appointment, but you must demonstrate your project and hand
in your hard copy by the due date unless you receive a specific provision otherwise
(see also the information about free late days on the syllabus).
DLLIter)
which implements each of the methods described here.
A note on errors: for each of the above operations/methods, you should
give an explicit report if an error occurs, i.e., if there is no way to perform
the requested operation. For example, if the DLL is empty, there is no current
item to move anywhere. For the insertion commands, this will not matter. For the
search ("find") commands, you should give an error, though you may wish to
phrase it as a "warning" (the command can be properly complied with, but the
results are unlikely to reflect the user's intentions.
moveToHead and moveToTail methods:
these should dynamically update the
list so that whatever item is current is moved to the head or tail
position, respectively. The list should be "stitched back together" at the
point where the current item is removed. After one of these methods is
invoked, the current item should be changed to be the head or tail,
respectively.
first and last methods: these
should dynamically update the current item reference so that it refers to the head
or tail of the list, respectively.
advance and retreat methods: these
should move the current item reference forward or backward by one list item.
insertBefore and insertAfter methods:
these should insert a given item before or after the current item (the
item itself will be specified as an integer following the command code
on the line).
findFirst and findLast methods:
these might have been better named "findForward" and "findBackward", as
they are intended to search in the forward and backward direction, but note
that they are to begin the search at the first or last item,
respectively.
removeFirst and removeLast methods:
these should search for and remove an item, in either a forward or
backward direction, and then remove the item.
The new current item should be the one after the removed one (if searching forward with removeFirst) or before the removed item
(if searching backward with removeLast).
In the special case where the last (resp. first) item in the list is removed, make the current item the one just before
(resp. after) the removed one, if possible (i.e., if the list is non-empty after the removal).
printFirst and printLast methods:
these should print out the current list in one direction or the other
(forward or reverse). The integers should be printed with intervening
blanks, except that the current item should be printed with asterisks
on either side as well (e.g., 1 2 3 *4* 5 6).
MH and MT for the
moveToHead and moveToTail
methods.
F and L for the
first and last methods.
A and R for the
advance and retreat
methods.
IB and IA for the
insertBefore and insertAfter methods.
FF and FL for the
findFirst and findLast methods.
RF and RL for the
removeFirst and removeLast methods.
PF and PL for the
printFirst and printLast methods
Q for a
quit command (no arguments).
Welcome to List-o-Rama, your doubly-linked list service center.
Enter commands one per line, and input values where indicated:
> P
[no elements]
> MH
Error: no head to move to
> IA 5
[this is allowed, even though no current item]
> PF
*5*
> IB 4
> IA 3
> PF
4 *5* 3
> A
> PF
4 5 *3*
> Q -- OK, time to quit (end-of-line text is ignored)
Thanks for using List-o-Rama, come again soon!
