The List and PList Classes

The List and PList Classes

The List class represents a template list of objects. The PList class represents a template list of pointers to objects. Written by Ron MacCracken for the Data Structures class, they include the routines that construct and manage generic lists in C++. This class was created to generalize the use of lists in C++ programs, and as an example of how linked lists are built in C++.

To Obtain the Classes

To obtain the List class you need both the include file List.h and the source code file List.C. The user must also include the ListElement class, ListElement.h and ListElement.C, class for the lists to operate correctly. Accessing elements of the list requires the ListIterator class, ListIterator.h and ListIterator.C.

To obtain the PList class you need both the include file PList.h and the source code file PList.C. The user must also include the PListElement class, PListElement.h and PListElement.C, class for the lists to operate correctly. Accessing elements of the list requires the PListIterator class, PListIterator.h and PListIterator.C.

Notes on Templates

Template classes and functions are a special feature of C++. They allow the programmer to create classes and functions that apply to any type, such int, double, or any user-defined classes. Specific functions and member variables for these classes can not be added to the class because they are meant to be generic. This should not be a problem because those functions should be placed in the class using the List class, instead of the List class itself.

From a syntax standpoint, there are a few differences. Instead of having a STringList, you would write List< STring > - the List type does not exist on its own. Also, the header file should include the source file after the class declaration. Since the template source file is basically now an include file, it should also be protected with #ifndef...#define...#endif as are header files (see List.C for an example).

NOTE: The above syntax is for g++. I do not know how PC compilers will work with this syntax. Some compilers do not require the source file be included from the header file. I am sure there are others that require other things as well.

Notes on Iterators

Iterators are a special type of class in C++. They allow the programmer to access elements of a particular data type without having to know the implementation of that data type. In this case, the ListIterator gives the programmer access to every element in the singly-linked List from head to tail. If this was a doubly-linked List, it would probably be nice to also have an iterator going from tail to head also.

The example below shows how easy it is to access every element of the List. Also notice that no matter how the List is implemented, either using pointers, a dynamically allocated array like DynArray, or others, this code will always stay the same - so long as the appropriate changes are made internally to the ListIterator class.

Example Usage:

    List < int >       list ;

    ...

    for ( ListIterator< int > i ( list ) ; ! i.Is_Done ( ) ; ++i )
    {
        int element = i.Get_Current ( ) ;

        ...
    }

This class was generated as an example of templated linked-list design for the Data Structures class at UC Davis. It has worked in a limited set of situations. You may use it ``as is'' or can modify it. If you find errors, and can correct them, please send mail to the address below, as we would also like to know about them.

This document maintained by Ken Joy.
Comments to the author : joy@cs.ucdavis.edu

All contents copyright (c) 1994, 1995, 1996
Computer Science Department, University of California, Davis
All rights reserved.


Ken Joy Wed Apr 24 20:18:26 PDT 1996