List ADT and
provides two different implementations:
DynList.
The array size changes dynamically as element insertions or deletions
are done. The array is a built-in C++ array, not an instance of the
Array class.
SlList. This list
uses singly-linked nodes and is circular.
Additionally, the text defines iterators for each list type. These
iterators are used to implement some of the List ADT
operations.
The text does not define a List class and does not set up
a relationship between DynList and SlList.
The text also does not define an Iterator class and does
not set up a relationship between DynListIterator and
SlListIterator.
It is therefore not possible to write polymorphic programs involving
lists and iterators.
In this project, you will correct those deficiencies. This will give you first-hand experience with coding to interfaces. You will see some of the power of dynamic binding and polymorphism. You will get to work in the details of list data structures. Finally, you will write your own iterators and see how the fabulous OOP idea of using iterators works out in practice.
There are three abstract classes (interfaces) in this project. The definitions of the ADTs for these classes are given below.
List the interface for all lists.
Iterator the interface
for all iterators.
ListIterator the
interface for all list iterators.
You are to write the following six concrete classes:
Array. This is the very same class you defined in
Project 1. You should be able to use it as-is.
ArrayList. This is
very similar to DynList but uses an Array
rather than an ordinary array. ArrayList is derived from
List and uses an aggregated Array in its
implementation.
DlNode. This is very
similar
to SlNode except that DlNode is
doubly-linked. DlNode is used by LinkedList.
LinkedList. This is very
similar to SlList, but uses a doubly-linked node rather
than a singly-linked node. Like SlList, this list is
circular. LinkedList is derived from List.
ArrayListIterator.
This is the class of Iterator created by
ArrayLists. It is derived from Iterator and
is specialized to work with ArrayLists.
LinkedListIterator.
This is the class of Iterator created by
LinkedLists. It is derived from Iterator
and is specialized to work with LinkedLists.
There is one concrete class
IteratorConstants that
contains static constants for use with iterators.
This class is fully defined, you don't have to make any changes.
Since the constants are static members of the class, they can be
referred to directly, without instantiating an object. For example,
to refer to the FORWARD constant, use the expression
IteratorConstants::FORWARD.
Take a look at the class diagram for these classes. The abstract classes are indicated by boxes with rounded corners. The concrete classes have square corners.
ArrayList and LinkedList are subclasses of
List; we say that each "is-A" List.
List creates an Iterator and
Iterator uses a List. Since both
List and Iterator are abstract, this
statement really means that every instance of a concrete subclass of
List creates an instance of a concrete subclass of
Iterator, and the concrete instance of
Iterator uses the concrete instance of List.
For example, ArrayList creates an
ArrayListIterator. The iterator that the list creates
uses the list that created it.
ArrayList has an Array (an example of
aggregation or composition). The Array is created
internally by ArrayList when the list is constructed.
LinkedList has a DlNode (again, an example
of aggregation or composition). The DlNode is created
internally by LinkedList when the list is constructed.
ListIterator is an Iterator specialized for
use with lists. It is an abstract subclass because it does not
implement all the methods of the superclass. It does not implement
the next() method since its definition differs for
ArrayListIterator and LinkedListIterator.
The two concrete iterators are specialized for use with their appropriate lists.
.H file and implemented in a
corresponding .C file.
You are then to exercise your classes by running the specified main function. Sample output from the main function is provided below. Try your program with a variety of command line arguments including with LinkedList and with ArrayList. Test it with invalid arguments.
IteratorConstants.H
to your directory. No changes are necessary in this file.
Proj2.C file. You will have to document it and
include the appropriate header files.
getCommandLine(int,char*[],int*,int*,List**)
function in your Proj2.C file.
List.H,
Iterator.H,
ListIterator.H,
Array.H,
ArrayList.H,
DlNode.H,
LinkedList.H,
ArrayListIterator.H, and
LinkedListIterator.H.
List,
Iterator,
ListIterator,
Array,
ArrayList,
DlNode,
LinkedList,
ArrayListIterator, and
LinkedListIterator.
umbc9: Proj2 3 5 LinkedList ------- Using LinkedList ------- -- Insert (at index 1) 3 elements, starting with 5 -- (7,6,5) length = 3 -- Clear the list -- () length = 0 -- Insert (in-order) 3 elements, starting with 5 -- (5,6,7) length = 3 -- Clear the list -- () length = 0 -- Append 3 elements, starting with 5 -- (5,6,7) length = 3 -- Use multiple iterators simultaneously -- 12 12 12 -- Output directly from reverse iterator -- 7,6,5 Repeatedly delete 1st element, even on empty list (5,6,7) 1 (6,7) 1 (7) 1 () 0 ()