Need help implementing an ordered-list:storage structure is linked-list using 2arrays

[rllioacvuher]

I need help with a program. I have implemented that following header file with an unordered list using one array, but i need to be able to use an ordered list and 2 arrays (one for the links and one to use as an index to the freearray cells).
Here is the exact problem specifications:
Create an ordered list template class named OLType to implement an ordered list with operations of insert, remove, print, empty, full, size. The storage structure is to be a linked-list emulation using dynamic arrays. It will require a minimum of two arrays, one for the data and one for the 'next' links. The 'free' list can be incorporated into the 'next' links array if done correctly. The 'public' portion of your class file must be as follows:
public:
OLType(size_t n=100);
~OLType();
void insert(const T& item);
void remove(const T& item);
void print() const;
size_t size() const;
bool empty() const;
bool full() const;

Here is the code I have so far:

#ifndef OLType_H
#define OLType_H

#include <iostream>

using namespace std;

template <class T>
class OLType {
public:
OLType(size_t n=100);
~OLType();
void insert(const T& item);
void remove(const T& item);
void print() const;
size_t size() const;
bool empty() const;
bool full() const;
private:
size_t MAX_LENGTH;
size_t n; // max number that can be stored in the list
int count; // number of elements in the list
T *data; // pointer to the array that holds the list elements
};

template <class T>
OLType<T>::OLType(size_t n) {
MAX_LENGTH = n;
count = 0;
data = new T[MAX_LENGTH];
}

template <class T>
OLType<T>::~OLType() {
delete [] data;
}

template <class T>
void OLType<T>::insert(const T& item) {
data[count] = item;
count++;
}

template <class T>
void OLType<T>::remove(const T& item) {
int i = 0;
while (i<count && item != data[i])
i++;
if (i<count) {
data[i] = data[count-1];
count--;
}
}

template <class T>
void OLType<T>::print() const {
int i;
for(i=0; i<count; ++i)
cout << data[i] << " ";
}

template <class T>
size_t OLType<T>::size() const {
return count;
}

template <class T>
bool OLType<T>::empty() const {
return (count == 0);
}

template <class T>
bool OLType<T>::full() const {
return (count == MAX_LENGTH);
}

#endif

Any help with solving this problem would be greatly appreciated. I am not that strong of a programmer and just cannot seem to find the correct way to do this problem. Thank you.

[Banfa]

Well I personally would not normally implement a linked list as 2 arrays, I would use a single array of structures.

However it is possible.

You next step is to set up the array of "next" pointers. However rather than pointers I think these will need to be an integer type. This array will need the same number of entries as data. Assuming that this array of ints is called nextIndex then for any given current index IX

data[IX] = the value at this index
nextIndex[IX] = the next index in the list

You will need 3 other things

1. A special value (#defined or static const) indicating the end of the list

2. A data member recording the first index in the list

3. A data member recording the first index in the free list

Since any given index can only be used (exclusive) or not used (i.e. can't be used and not used then the same array of indexes can be used to hold the list of free entries. As I have stated in 3 above all you need is a new starting point.