Trouble modifing my program from templates to link lists

I have to modify this program which uses templates to use only linked lists and I am having a world of trouble trying to figure out how to start. I am quite horrible with linked lists and would appreciate any kind of help. It is n implementation file that recieves any kind of data and then sorts it. And I can't figure out how I would make a linked list do that. Or what kind of code I would write to make it do that. I have read a couple of chapters in my C++ book and they are anything but helpful. I have spent a couple of days working on it and this is my last resort. Thanks.

Code:

#include <iostream>

using namespace std;

template<class ItemType>
GLista<ItemType>::GList()  //Constructor
{
 length = 0;
 sorted = false;
}

template<class ItemType>
bool GLista<ItemType>::IsEmpty() const
{
 return(length == 0);
}

template<class ItemType>
bool GLista<ItemType>::IsFull() const
{
 return(length == MAX_LENGTH);
}

template<class ItemType>
int GLista<ItemType>::Length() const
{
 return length;
}

template<class ItemType>
void GLista<ItemType>::Insert(/* in */ ItemType item)
{
 data[length] = item;
 length++;
 sorted = true;
}

template<class ItemType>
void GLista<ItemType>::Delete(/* in */ ItemType item)
{
 int index = 0;

 while(index < length && item != data[index])
  index++;

 if(index < length)
 {
  if(sorted)
  {
   while(index <= length - 2)
   {
    data[index] = data[index + 1];
    index++;
   }
  }
  else
   data[index] = data[length - 1];

  length--;
 }
}

template<class ItemType>
bool GLista<ItemType>::IsPresent(/* in */ ItemType item) const
{
 int index = 0;

 while(index < length && item != data[index])
 index++;

 return(index < length);
}

template<class ItemType>
void GLista<ItemType>::SelSort()
{
 ItemType temp;
 int passCount;
 int searchIndex;
 int minIndex;

 for(passCount = 0; passCount < length - 1; passCount++)
 {
  minIndex = passCount;
  for(searchIndex = passCount + 1; searchIndex < length; searchIndex++)
   if(data[searchIndex] < data[minIndex])
    minIndex = searchIndex;

  temp = data[minIndex];
  data[minIndex] = data[passCount];
  data[passCount]= temp;
 }
 sorted = true;
}

template<class ItemType>
void GLista<ItemType>::Print() const
{
 int index;

 for(index = 0; index < length; index++)
  cout << data[index] << endl;
}

Code:

template<class ItemType>
GLista<ItemType>::GList()  //Constructor
{
 length = 0;
 sorted = false;
}

Constructors must have the same name as the class. So, either the name of the class must be GList or the constructor must be GLista.

Well, it looks like you started off with an array based container implementation and now wish to move to a list based container correct? Well, for starters, lists and arrays are two very different things. You can't just slap a "list" label on an array implementation and have it work like a list should work. You are going to need to start from scratch. It would also be helpful to have a complete class declaration to look at and not just the function themselves, one for a basic double-linked list might look something like:

Code:

template <class T> struct node
{
    T data;
    node *next;
    node *previous;
    node(const T& item)
    {
        next = previous = NULL;
        data = item;
    }
    node()
    {
        next = previous = NULL;
    }
};

template <class T>
class GList
{
    node<T> *head;
    node<T> *tail;
public:
    GList()
    {
        head = tail = NULL;
    }
    ~GList()
    {
        node<T> *current = head;
        node<T> *temp;
        while( current != NULL )
        {
            temp = current;
            current = current->next;
            delete temp;
        }
    }
    void push_back(const T& data)
    {
        node<T> *pNew = new node<T>(data);
        if( pNew )
        {
            if( head == NULL )
            {
                // This is the first node added to list, set head/tail pointers
                head = tail = pNew;
            }
            else
            {
                // Previous nodes have been added, add this node to end of list
                tail->next = pNew;
                pNew->previous = tail;
                tail = pNew;
            }
        }
        else
        {
            // There was an error allocating memory, display error message
            cerr << "GList::push_back - Memory allocation error!" << endl;
        }
    }
};

You'll need to convert all your necessary functions from array based implementations into a linked list implementation. I was nice and demonstrated a "push_back" function that adds a new node to the end of the list, you'll need to do the rest. Since you are using templates, all that probably needs to go in a header file of some kind. You'll need to decide what to keep from your old array implementation and what to throw out. Obviously, a list can keep growing (until no more memory is available) so a function like IsFull really doesn't make sense with a list unless you wish to place an arbitrary restriction on its size. When it comes time to use your GList class, you can start out using it like this:

Code:

GList<int> intList;

intList.push_back(10);  // Add element to linked list
intList.push_back(20);  // Add element to linked list
intList.push_back(30);  // Add element to linked list
intList.push_back(40);  // Add element to linked list