List Class – Design

There will be several different stacks needed.  Each type of stack would have the same functionality but would hold a different type of items. The best way to implement this is by using a class template.  The list class template will have and element contained the next and previous link pointers plus the generic value. The beginning of the list class will be defined as:

    template <class T> List {...}

Where T is the generic type that the list will hold.  This generic type could be a simple like an int or double, or could be a structure. The internal element structure containing the links and value will be defined as:

    struct Element {
Element *prev;
Element *next;
T value;
    };

The list will have a master element pointer that will be a pointer to Element but that actually element allocated will be without the T value; in other words, allocated for sizeof(Element) – sizeof(T). The master element pointer will be allocated and initialized in the constructor function.

The master->next variable will point to the first element in the list (i.e. bottom of a stack) and the master->prev variable will pointer to the last element in the list (i.e. the top of a stack). Implementation of the various functions is simplified if the list is circular, in other words, the last element's next pointer points back to the master element (and the first element's previous pointer also points back to the master element). In an empty list, both the master element's next and previous pointers would point to the master element. Therefore, the master element's pointers will be initialized this way after it is allocated.