CS 14 - Fall 2003

CS 14 - Lab 4

In this lab we want to give you some hands-on experience using abstraction and Iterators.

The Assignment

7 points Download the following files:

lab4main.cc - a testing file
lab4list.h - an ADT List interface
lab4alist.h - The interface to a self-expanding array implementation of the ADT List in lab4list.h
lab4alist.cc - The implementation of lab4alist.h
lab4llist.h - A starter for the interface of a singly-linked-list implementation of ADT List from lab4list.h
lab4llist.cc - A starter for the implementation of a singly-linked-list version of ADT List from lab4list.h

These files provide an array-based list implementation, some tests for ADT List, and the interface for ADT List. Your job is simply to fill in some unfinished functions in lab4llist.cc and lab4llist.h which implement ADT List as a singly-linked list using exactly the same interface.

You can search these files for "TODO" to find where there are functions you need to write.

To see the desired functionality, leave the declaration of l in lab4main.cc as

ArrayList l;

When you are done implementing your linked list, change to

LinkedList l;

Everything else should be the same.

.2 points: Implement a Makefile for this code that uses the correct compiler flags.

.2 points: Implement LinkedList.size() as an O(1) operation.

.4 points: Add appropriate exceptions to lab4llist.cc, lab4llist.h and lab4list.h to deal with requests too large for the current list size.

.2 points: Write a function that uses your LinkedListIterator to make some change to a LinkedList passed into it.

.2 points: From your CS email account, send the function you wrote above to the CS14 mailing list. ONLY send the function using your LinkedListIterator. If ANY implementation code goes to the list, you will get a 0 for the lab.

.2 points: Edit your makefile and lab4main.cc to allow the makefile to easily build both versions of the program: the one using the LinkedList implementation and the one using the ArrayList implementation. You'll want to investigate the -D flag to g++. .1 points/function, max .5 points: Take the functions being sent to the mailing list and demonstrate that they work with your implementation by adding calls to them to your main function in lab4main.cc. If you did not change the interface for LinkedList or LinkedListIterator, this should be no problem.