CS14, Program 2
Assigned: October 13th, 2001
Due: October 25th, 2001, 10pm
Topic
Array implementation of a list.
Background
In an array implementation of a list, the list is stored in (surprise!) an array, one item per array cell. The implementation we will work on has a cursor, which stores the index of an array cell. The cursor can be set to the beginning of the list, and can be advanced one position at a time towards the end of the list. Array items are not sorted. However, their relative order is preserved whenever an insert or remove operation is performed. This means that these methods will involve shifting of array elements.
Please note that the value stored in the cursor does not necessarily have to be a valid list position. Wherever appropriate, your methods will have to verify that the cursor position is valid, before performing certain operations. Do not leave this checking up to whoever is using the class. It is your responsibility to verify that an invalid cursor value will not cause a program crash or unexpected consequences.
Also note that some
methods require that the cursor not be moved. It is a good idea to use a
local iterator to move up and down the list. Even when the value of the cursor
is changed by the method, you may find it easier to use a local iterator,
changing the value of the cursor only towards the end of the method.
To do
In this assignment,
you will write an array implementation of a list of chars.
A header file for the list is provided, along with comments detailing the
operation of each method. Download the header file
list.h
and the shell for the implementation file list.cc
, and take it from there. Your job is
to fill in the methods in the implementation file, and then test it
to verify that all methods do what they are supposed to do.
Please note that the implementation file is not commented, but it should be before it is turned in.
What to turn
in
list.h and list.cc