by Bar Zohan
5. April 2010 23:20
Not a production quality code, but can be useful to understand how data structures are written in c++. A basic linked list example which is capable of doing sorting and find operations over the list.
Here is the code for that:
#include <vector>
using std::vector;
template <typename T> class List;
template <typename T>
class ListNode
{
friend class List<T>;
public:
ListNode(T newData):data(newData) ,NextPtr(0)
{
}
T getData() const {return data;}
private:
T data;
ListNode<T>* NextPtr;
};
template <typename T>
class List
{
public:
List():firstNode(0),lastNode(0),size(0){}
~List()
{
if (!isEmpty())
{
ListNode<T> *currentPtr = firstNode;
ListNode<T> *tempPtr;
while (currentPtr != 0)
{
tempPtr = currentPtr;
currentPtr = currentPtr->NextPtr;
delete tempPtr;
}
}
}
void insertToFront(T newData)
{
size++;
ListNode<T> *newPtr = new ListNode<T>(newData);
if (isEmpty())
{
firstNode = lastNode = newPtr;
}
else
{
newPtr->NextPtr = firstNode;
firstNode = newPtr;
}
}
void insertToBack(T newData)
{
size++;
ListNode<T> *newPtr = new ListNode<T>(newData);
if (isEmpty())
{
firstNode = lastNode = newPtr;
}
else
{
nodes[size-1] = newPtr;
lastNode->NextPtr = newPtr;
lastNode = newPtr;
}
}
template <class CompareClass>
void sort(CompareClass c)
{
partialSort(0,GetSize() - 1,c);
}
bool removeFromFront()
{
if (isEmpty())
{
return false;
}
else
{
size--;
ListNode<T> *tempPtr = firstNode;
if (firstNode == lastNode)
{
firstNode = lastNode = 0;
}
else
{
firstNode = firstNode->NextPtr;
}
delete tempPtr;
return true;
}
}
bool removeFromBack()
{
ListNode<T> *ptrToDel = lastNode;
if (isEmpty())
{
return false;
}
else
{
size--;
ListNode<T> *currentPtr = firstNode;
while(currentPtr->NextPtr != lastNode)
{
currentPtr = currentPtr->NextPtr;
}
lastNode = currentPtr;
currentPtr->NextPtr = 0;
delete ptrToDel;
return true;
}
}
int indexOf(T item)
{
int i = 0;
ListNode<T> *currentNode = firstNode;
while(currentNode->data != item)
{
i++;
currentNode = currentNode->NextPtr;
}
return i;
}
int GetSize() const
{
return size;
}
void Print()
{
if (isEmpty())
{
cout << "Empty List" << endl;
}
else
{
ListNode<T> *currentPtr = firstNode;
while (currentPtr != 0)
{
cout << currentPtr->data << endl;
currentPtr = currentPtr->NextPtr;
}
}
}
T &operator[](int index)
{
return nodes[index]->data;
}
bool isEmpty() const
{
return firstNode == 0;
}
bool compare(T a, T b)
{
return true;
}
private:
int size;
template <class CompareClass>
void partialSort(int begin, int end, CompareClass c)
{
if ((end - begin) >= 1)
{
int mid1 = (end + begin) / 2;
int mid2 = mid1 + 1;
partialSort(begin,mid1,c);
partialSort(mid2,end,c);
Merge(begin, mid1, mid2, end,c);
}
}
template <class CompareClass>
void Merge(int left, int mid1, int mid2, int right, CompareClass c)
{
int leftIndex = left;
int rightIndex = mid2;
int totalIndex = left;
vector<T> combined(GetSize());
while (leftIndex <=mid1 && rightIndex <= right)
{
if( c((*this)[leftIndex] , (*this)[rightIndex]))
{
combined[totalIndex++] = (*this)[leftIndex++];
}
else
{
combined[totalIndex++] = (*this)[rightIndex++];
}
}
if (leftIndex == mid2)
{
while (rightIndex <= right)
combined[ totalIndex++ ] = (*this)[ rightIndex++ ];
}
else
{
while (leftIndex <= mid1)
combined[ totalIndex++ ] = (*this)[ leftIndex++ ];
}
for(int i = left; i<= right; i++)
{
(*this)[i] = combined[i];
}
}
ListNode<T> *firstNode;
ListNode<T> *lastNode;
ListNode<T>* nodes[20000];
};
class IntComparer
{
public:
bool operator()(int a, int b)
{
return a <= b;
}
};
Subscribe