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 ()