The List ADT: 

  1. Elements of a List are homogeneous in type. There is a notion of a 
first element. Given a current element, there is a notion of a next 
element and a notion of a previous element. 
  2. Operations on the List include: 
    (a) Test for the List being empty 
    (b) Find an element in the List 
    (c) Find the predecessor element of an element in the List 
    (d) Find the first element in the List 
    (e) Remove an element from the List 
    (f) Insert an element in the List at the current position 

• An ADT does not say anything about implementation.

20.1 An Array­Based Implementation 

class ArrayList         // restricted to int 
{
  private: 

    unsigned int length; 
    int * buffer; 

  public: 

    // Constructors, destructor, etc. 

};

A major problem with this implementation is that it is restricted to int 
data. If we want to make a list of some other type, we need to re­write the 
code. It is possible to use typedef to allow easy modification, but we are 
still restricted to one type at a time.

• Templates allow parameterization of class and function definitions so they can ``take'' different types without re­writing code

21 Templates

C++ allows functions and classes to be parameterized by type. This means the same function or class can be used with many different data types.

• Class and function template declarations both start off with the prefix template <class T>
• The prefix template <class T> specifies that a template is being declared and that an argument of type T is going to be used. T is then used just like any other type within the declaration. T is called a template argument.
• In this context, class means ``type.'' It has nothing to do with classes.
• There can be more than one template argument.

2.1 Function Templates

template <class Etype>
int foo (Etype x) 
{ 
... // Etype can be used as a type in the body of the code, too. 
}

• foo can be called with any type of data.
• foo can be thought of as a large number of overloaded functions, one for each possible type.
• The definition starts with the prefix template <class Etype>
• It is necessary to use every template argument in the argument types of the template function.

2.2 Class Templates

template <class T>
class ArrayList 
{
  private: 

    unsigned int length; 
    T * buffer; 

  public: 

    ArrayList(); 

};

// definition of the constructor 
template <class T>
ArrayList<T>::ArrayList()
{
  // code here
}

// another constructor
template <class T>
ArrayList<T>::ArrayList(const unsigned int len)
{
  // code here
}

22. Linked Implementation of List

The SGI compiler does not permit nested template classes. 
Therefore, to make this work we need to make Node a separate 
class. We make List a friend of the Node class. In List, every 
reference to Node must be parameterized by type

The following is a version of the List class which uses an 
external Node class.   Put this code into node.h

template <class T> class List; // forward declaration of List 
template <class Etype>
class Node 
{
  protected: 

    Etype Element; 
    Node *Next; 
    Node( Etype E = 0, Node *N = NULL )
      : Element( E ), Next( N ) { }
 
    friend class List;      // now all functions in List have 
};                               // access to members of Node

// put this declaration into List.h
template <class Etype>
class List 
{
  protected: 

    Node<Etype> *List_Head; 
    Node<Etype> *Current_Pos; 
    void Delete_List( ); 

  public: 
    // Constructors and destructor 
    List( ) : List_Head ( new Node<Etype> ), Current_Pos( List_Head ) {}
    List( List & Value ); 
    virtual ~List( ) { Delete_List( ); } 

    // Operators. 
    const List & operator = ( List & Value ); 
    const List & operator ++ ( ); 
    int operator ! ( ) const; 
    Etype operator ( ) ( ) const; 

    // Member functions. 
    int Is_Empty( ) const { return List_Head->Next == NULL; }
    virtual int Find( const Etype & X ); 
    virtual int Find_Previous( const Etype & X ); 
    int In_List( const Etype & X ); 
    void First( )
      {
        if ( List_Head->Next != NULL ) 
          Current_Pos = List_Head­>Next; 
      }
    void Header( ) { Current_Pos = List_Head; }
    int Remove( const Etype & X ); 
    virtual void Insert( const Etype & X ); 
    virtual void Insert_As_First_Element( const Etype & X ); 
}; 

• A List Node is represented as a struct member of the class. This struct has its own constructor which takes an Element and a pointer to Node. The pointer to Node is a pointer to the ``next'' node on the list.
• Stroustroup (``The C++ Programming Language'', page 164) says that nesting of classes has the advantage of minimizing the number of global names, but the disadvantage of hindering unanticipated uses of nested types.

22.1 Node

A List Node is represented by a class (or struct) which has two data fields 
(Etype Element and Node *Next) and a constructor. Figure below represents 
a node as a box with two compartments, one for Element and one for Next. 

The Node constructor takes two arguments 
    1. the datum which is to be used as the Element, and 
    2. what the Next pointer is to point to.

22.2 Making a List

A List is headed by a dummy node called a ``header.'' This is a 
convenient way to avoid difficulties with empty lists. An ``empty'' 
list has just the header node. 
The figure below shows the construction of a list by insertion
of the elements ``1'' and ``2'' using the member function 
Lists::Insert As First Element(const Etype &). 

    Diagram to be supplied in class


 The "1" is inserted at the head. The Node is constructed with 
"1" as the Element and with List Head­>Next (i.e., NULL) as its Next 
pointer. After Node construction, the node is "hooked"into the 
list by setting List Head­>Next to point to it. 

The "2" is now inserted at the head. The operations performed 
are identical to those performed for inserting "1". A new Node is 
created with "2" as its Element and with List Head­>Next as its 
Next pointer. This time, List Head­>Next points to the Node which 
has "1" as its Element. The List Head­>Next pointer is then set to 
point to the new Node.

A List can also be made by Insert which inserts a new Node 
after the Node at Current Pos, then sets Current Pos to point the 
the new Node. Insert works like Insert As First Element except 
that the new Node is constructed with Current Pos­>Next (rather 
than List Head­>Next) as its Next field.