CS14, Program 3
Assigned: October 28th, 2001
Due: November 11th, 2001, 10pm
Topic
Linked list implementation of a list.
Background
In a linked list implementation of a list, the list elements are stored in nodes that are linked with pointers. The implementation we will work on has a pointer, head, to the first node in the list, and a second pointer, cur, which points to a node in the list (or NULL). The cursor can be set to the head of the list, and can be advanced one position at a time towards the end of the list. List items are not sorted. However, their relative order is preserved whenever an insert or remove operation is performed.
Please note that the value stored in the cursor does not necessarily have to be the address of a list node. It could be NULL. Wherever appropriate, your methods will have to verify that the cursor points to a valid node, 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 a linked list 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