Linked List Iterators
In this lab we want to give you some hands-on experience using
abstraction and Iterators.
The Assignment
7 points
Download the following files:
- lab3main.cc - a testing file
- lab3list.h - an ADT List interface
- lab3alist.h - The interface to a
self-expanding array implementation of the ADT List in lab3list.h
- lab3alist.cc - The implementation
of lab3alist.h
- lab3llist.h - A starter for the interface
of a singly-linked-list implementation of ADT List from lab3list.h
- lab3llist.cc - A starter for the implementation
of a singly-linked-list version of ADT List from lab3list.h
These files provide an array-based list implementation, some tests for
ADT List, and the interface for ADT List. Your job is to implement
lab3llist.cc
which implements ADT List as a singly-linked list
using exactly the same interface.
You can search lab3list.cc for "TODO" to find where there are functions
you need to write.
To see the desired functionality, leave the declaration of l in
lab3main.cc as
ArrayList l;
When you are done implementing your linked list, change to
LinkedList l;
Everything else should be the same.
NOTE: LinkedList is a wrapper-class around the more basic linked-list
type that we have been working with so far this quarter, Node*.
Don't get the two confused!
.2 points: Implement a Makefile for this code that uses the
correct compiler flags.
.2 points: Implement LinkedList.size() as an O(1) operation.
.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 lab3main.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
lab3main.cc. If you did not change the interface for LinkedList or
LinkedListIterator, this should be no problem.
.5 points: Edit the List types to work as templated datatypes
rather than using typedef. Do this only after sending out
your function to the mailing list, this change will certainly make your
code not interoperate!