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
20.1 An ArrayBased 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 rewrite the code. It is possible to use typedef to allow easy modification, but we are still restricted to one type at a time.
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.
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. }
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 ); };
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.