Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Ordered Lists

Figure: Object Class Hierarchy

The most basic of the searchable containers is an ordered list . In Chapter we defined a searchable container as a container which supports the following additional operations:

Insert: used to put objects into a the container;
Withdraw: used to remove objects from the container;
Find: used to locate objects in the container; and,
IsMember: used to test whether a given object instance is in the container.

An ordered list is a container which holds a sequence of objects. Each object has a unique position in the sequence. In addition to the basic repertoire of operations supported by all searchable containers, ordered lists provide the following operations:

FindPosition: used to find the position of an object in the ordered list;
operator []: used to access the object at a given position in the ordered list;
Withdraw(Position&): used to remove the object at a given position from the ordered list.
InsertAfter: used to insert an object into the ordered list after the object at a given position; and
InsertBefore: used to insert an object into the ordered list before the object at a given position.

Program declares two abstract classes--List and OrderedList. The List class is derived from the SearchableContainer class which is in turn derived from the Container class. Consequently, the List class interface comprises all of the member functions inherited from these base classes plus four additional member functions, FindPosition, two versions of operator[] and Withdraw. As befits the definition of an abstract class, all of these functions are pure virtual member functions of the List class.

program9348
Program: List and Ordered Class Definitions

The OrderedList class extends the List class by adding two more member functions--InsertAfter and InsertBefore. The two functions provided by the OrderedList class have been separated out from the List class interface because the List class is used as the base class from which other types of lists are derived.

Program also defines the abstract class Position. The Position class abstracts the notion of the position of an item in a list. Since this is abstraction is almost identical to that of an iterator, the Position class is derived from the Iterator abstract class. No additional member functions are defined.

As we did in the previous chapter with stacks, deques and queues, we will examine two ordered list implementations--an array-based one and a pointer-based one. Section presents an implementation based on the Array<T> class; Section , a pointer-based implementation based on the LinkedList<T> class.