Game Programming III – the second week, linked lists part three (3)

Hello again!

Let’s try to finish up the linked list. Last time I put up a completely functional linked list for integer variables. We now need to remake it into a list that can story data any type, in other words we need to make it generic.

There are a few things different about this version. First off we will need to write it all in the header file and not use any source file at all because we are making use of template classes.

The start of the new header file looks like this:

template
class LinkedList
{
private:
struct Node
{
T data;
Node* next = nullptr;
};

Node* m_head;
Node* m_current;
Node* m_temporary;

note that the ”int” has been replaced with the template class ”T”. The same is done to all methods that had and ”int” in their argument.

For example the push_front method:

void List::push_front(int addData)
{
node* n = new node;
n->next = m_head;
n->data = addData;
m_head = n;

m_size++;
}

Now looks like this (note the parts marked with red):

void Push_front(T data)
{
Node* n = new Node;
n->next = m_head;
n->data = data;
m_head = n;
}

Also note that the variable m:size is no longer increased as the Size method has been rewritten (see below).

I have also done some general cleanup of the code:

void List::pop_front()
{
if (m_head == nullptr)
{
std::cout << ”No nodes in list, cannot pop front” << std::endl;
}
else
{
m_current = m_head;
m_temporary = m_head->next;

delete m_current;
m_head = m_temporary;
m_current = m_head;

m_size–;
}
}

After cleanup:

void Pop_front()
{
if (m_head == nullptr)
{
std::cout << ”No nodes in list, cannot pop front” << std::endl;
}
else
{
m_temporary = m_head->next;

delete m_head;
m_head = m_temporary;
}
}

As you can see, the new code does the same thing in fewer lines of code. I have also made some makor changes to the Size method. Instead of simply returning and integer the Size method now goes through the list and counts each node before returning the amount counted. This means I don’t have to make sure that the old m_size varible was properly changed every time a pop, push or erase method was called.

Size now looks like this:

unsigned long int Size()
{
unsigned long int count = 0;

if (m_head != nullptr)
{
count++;
m_current = m_head;

while (m_current->next != nullptr)
{
count++;
m_current = m_current->next;
}
}

return count;
}

As a final note, when a new list of the generic type is created, you will need to specify what kind of data that particular instance of the class will contain, so the syntax is changed from:

LinlkedList list;

To:

LinkedList list;

Note the red marking.

With this, the generic linked list should be finished. The next data structure I am going to work in will be a Binary Search Tree.

Until then, cheers!