A List Class Implemented Using an Array-Based Linked List

//---------------------------------------------------------
// arrLList.cpp
//
// File for a list class based on a linked list implemented
// using an array.
//
// D. Searls
// Jan 2008
//---------------------------------------------------------

#ifndef H_LISTCLASS
#define H_LISTCLASS
 
#include<cstdlib>
#include<iostream>
using namespace std;

template<class itemType>
class list
{  
private:

    static const int MAXSIZE = 100;
    static const int NIL = -1;
    
    typedef int nodePtr;
    
    struct node
    {
        itemType info;
        nodePtr next;
    };
    
    node data[MAXSIZE];
    nodePtr head;       // pointer to first node in list
    nodePtr current;    // pointer to current node (in traversal)
    nodePtr free;       // pointer to first node in free list
    int n;              // number of items in list
  
public:

    //-----------------------------------------------------
    // Default Constructor
    //
    // Constructs an empty list.
    //-----------------------------------------------------
    list()
    {
        for (int i = 0; i < MAXSIZE - 1; i++)
        {
            data[i].next = i + 1;
        }
        data[MAXSIZE - 1].next = NIL;
        head = NIL;
        current = NIL;
        free = 0;
        n = 0;
    }
    
    //-----------------------------------------------------
    // Copy Constructor
    //
    // Constructs a list populated with the values in the
    // specified list in the same order as they appear in
    // the list.
    //
    // In Parameter: theList
    //-----------------------------------------------------
    list(const list& theList)
    {
        for(int i = 0; i < MAXSIZE; i++)
        {
            data[i] = theList.data[i];
        }
        n = theList.n;
        head = theList.head;
        free = theList.free;
        current = NIL;
    }
    
    //-----------------------------------------------------
    // push_front
    //
    // Insert the specified item at the front of the list.
    //
    // In Parameter: item
    //-----------------------------------------------------
    void push_front(const itemType& item)
    {
        nodePtr newPtr;
        
        // Get new node
        
        newPtr = free;
        if (newPtr == NIL)
        {
            cout << "MEMORY ALLOCATION FAILED!" << endl;
            exit(0);
        }
        free = data[free].next;
        
            
        
        // Initialize new node
        
        data[newPtr].info = item;
        
        // Link new node into list
        
        data[newPtr].next = head;
        head = newPtr;
        
        // Update size of list
        
        n++;
    }
    
    //-----------------------------------------------------
    // remove
    //
    // Remove the first element equal to the specified item.
    // Equality is based on the result returned by the ==
    // operator applied to items in the list.
    //
    // In Parameter: item
    //-----------------------------------------------------
    void remove(const itemType& item)
    {
        nodePtr curr; // Pointer to current node
        nodePtr prev; // Pointer to previous node
        
        curr = head;
        prev = NIL;
        while (curr != NIL && !(item == data[curr].info))
        {
            prev = curr;
            curr = data[curr].next;
        }
        
        if (curr != NIL) // item was found so remove it
        {
            if (prev != NIL)
            {
                data[prev].next = data[curr].next;
            }
            else
            {
                head = data[curr].next;
            }
            data[curr].next = free;
            free = curr;
            n--;
        }
    }
    
    //-----------------------------------------------------
    // clear
    //
    // Remove all of the items from the list.
    //-----------------------------------------------------
    void clear()
    {
        nodePtr temp;
        
        while (head != NIL)
        {
            temp = head;
            head = data[head].next;
            
            data[temp].next = free;
            free = temp;
        }
        n = 0;
        current = NIL;
    }
   
    //-----------------------------------------------------
    // size
    //
    // Return the number of items in the list.
    //-----------------------------------------------------
    int size()
    {
        return n;
    }
    
    //-----------------------------------------------------
    // sort
    //
    // Sort the values in ascending order based on the
    // result returned by the < operator applied to the
    // items in the list.
    //-----------------------------------------------------
    void sort()
    {
        nodePtr start; // pointer to 1st node in unsorted portion of list
        nodePtr min;   // pointer to node with minimum value
        nodePtr curr;  // pointer to current node
        
        itemType temp; // Temporary record used in swapping
        
        start = head;
        while (start != NIL)  // At least one item in unsorted portion
        {
            min = start;
            curr = data[start].next;
            while (curr != NIL)
            {
                if (data[curr].info < data[min].info)
                {
                    min = curr;
                }
                curr = data[curr].next;
            }
            if (min != start)
            {
                temp = data[start].info;
                data[start].info = data[min].info;
                data[min].info = temp;
            }
            start = data[start].next;
        }
    }
    
    //-----------------------------------------------------
    // find
    //
    // Return a pointer to the first element in the list
    // that is equal to the specified item based on the ==
    // operator applied to items in the list. If there is
    // no element equal to the item,
    // return NIL.
    //
    // In Parameter: item
    //-----------------------------------------------------
    itemType* find(const itemType& item)
    {
        nodePtr curr;  // Pointer to current node
        
        curr = head;
        while (curr != NIL && !(data[curr].info == item))
        {
            curr = data[curr].next;
        }
        return itemAt(curr);
    }
    
    //-----------------------------------------------------
    // begin
    //
    // Return a pointer to the first item in the list or
    // end() if the list is empty.
    //
    // The functions begin(), next(), and end() are meant
    // to be used to perform a linear traversal of the list.
    //-----------------------------------------------------
    itemType* begin()
    {        
        current = head;
        return itemAt(current);
    }
    
    //-----------------------------------------------------
    // next
    //
    // Return a pointer to the next item in the list or
    // end() if there is no next item.
    //
    // The functions begin(), next(), and end() are meant
    // to be used to perform a linear traversal of the list.
    //-----------------------------------------------------
    itemType* next()
    {
        if (current != NIL)
        {
            current = data[current].next;
        }
        return itemAt(current);
    }

    //-----------------------------------------------------
    // end
    //
    // Return a pointer just past the last element in the
    // list.
    //
    // The functions begin(), next(), and end() are meant
    // to be used to perform a linear traversal of the list.
    //-----------------------------------------------------
    itemType* end()
    {
        return NULL;
    }

private:

    //-----------------------------------------------------
    // itemAt
    //
    // Return a pointer to the information at the specified
    // location. If the location is not valid, return end().
    //
    // In Parameter: location
    //-----------------------------------------------------
    itemType* itemAt(nodePtr location)
    {
        itemType* itemPtr;
        
        if (location != NIL)
        {
            itemPtr = &(data[location].info);
        }
        else
        {
            itemPtr = end();
        }
        return itemPtr;
    }
};

#endif