Game Programming III – the first week, linked lists part one (1)

Hello!

A new course in game programming has started and its first week is coming to an end. In this course we’ve been given an assignment divided into three (3) parts. I decided to start working on the first part this week. The first part requires me to create two elementary data structures, a custom linked list and a binary search tree. These must be created from scratch using my own C++ code. These structures must also be generic, meaning they must be able to contain any type of object specified when they are created or initiated rather than being specialized for a single type of object.

I decided to start by making a linked list. I decided to make one that can only handle integers first in order to get a grasp on linked lists and their structures. After that I’ll focus on learning about template classes in order to make a generic version of the linked list I’ve created.

So what is a linked list then? It is a series of nodes. Each node is composed of data and a reference or link to the next node in the sequence. Reference is a node pointer while the data could be of any type. In this case the data will be of the integer type since I’m not making this linked list generic.

The linked list needs to have a set of methods:

push_back – which adds a node at the end of the sequence

push_front – which adds a node at the start of the sequence

pop_back – which removes the last node from the sequence

pop_front – which removes the first node from the sequence

size – which returns the number of nodes in the sequence

erase – which was left somewhat open for interpretation, I choose to make erase remove the first node that cointained a certain value, as this seemed easy to implement. The value is entered into the arguments of the erase method.

search – also left open for interpretation. I choose to make search return how many nodes contained a certain value, once again because I thougt it would be easy to implement. The value is entered into the arguments of the search method.

I also added a print method that prints out the entire node in the console window. I added this as a way to check if the methods I implemented functioned the way I intended them to.

The header for the linked list class looks like this:

class List
{
public:
List();
~List();

void push_front(int addData);
void push_back(int addData);

void pop_front();
void pop_back();

void erase(int delData); //delete node with delData
void print();
void search(int value); //how many nodes have value?

int size();

private:
struct node
{
int data;
node* next;
};

node* m_head;
node* m_current;
node* m_temporary;

unsigned long int m_size;
};

Aside from the methods you’ll notice that I have three node pointers called m_head, m_current and m_temporary, as well as an unsigned long int called m_size. The m_size variable is, unsurprisingly, created in order to keep track on how many nodes are in the sequence. The m_head pointer is the starting point of the sequence and so must be present when the list is created as a pointer to NULL before any nodes are added. The m_current pointer is used for going through the sequence of nodes whenever a method requires it. The m_temporary pointer is present as a reserve for when a separate reference needs to be stored temporarily. All three pointers are set as pointers to NULL and the m_size is set to zero (0) in the constructor to avoid any potential access violations.

The push_front method as defined in the source file:

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

m_size++;
}

This should be pretty straightforward. A new node is created and its reference pointer is set to m_head, which is the first node in the sequence. If the sequence is empty, the new node will instead get a pointer to NULL as reference. This means the new node is effectively placed in the front of the sequence. The data entered into the push_front arguments is then added to the new node. The m_head pointer is then changed to point at the new node, as it is now the first in the sequence. Lastly the value of m_size is increased by one as the sequence now has one more node in it.

The push_back method as defined in the source file:

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

if (m_head != nullptr)
{
m_current = m_head; // <- !

while (m_current->next != nullptr)
{
m_current = m_current->next;
}
m_current->next = n;
}
else
{
m_head = n;
}

m_size++;
}

A new node is created. It is immediatly given a pointer to NULL as reference, since this node is to be placed at the end of the sequence, meaning there is no node after it to be referenced. The data entered into the push_back arguments are then added to the new node. Then the method checks to see if the m_head is a pointer to NULL. If it is, that means the node just added is the first one in the sequence, so all that’s left to do is changing m_head to reference the new node. If that is not the case, the m_current is used to go through the sequence of nodes until it reaches a node with a pointer to NULL as reference. The pointer is then changed to point to the new node, making it the new last element in the sequence as it is the only with a pointer to NULL as reference. Lastly the value of m_size is increased by one as the sequence now has one more node in it.

With this, we have two methods for adding nodes to the sequence, one for adding them at the start of the sequence and one for adding them at the end. The class is not done yet however as there are other methods that need to be defined in order to make it a complete linked list.

To be continued…