Game Programming III – the second week, linked lists part two (2)

Hello again.

Let’s continue with our linked list shall we? This post will (hopefully) go through the remaining methods for our linked list and in part three (3) I will make a variant that is generic, so that it can store all types of data, not just integer values. I’ve added a clear method to the class as well as deallocations in the destructor to prevent memory leaks. I should also point out that the methods are not always showing the most elegant of solutions, they are mostly here to provide an example for you to go after.

The next method we look at is the pop_front method as defined in the source file:

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–;
}
}

First I check to see if the m_head pointer is pointing at NULL. If it does, that means the list has no nodes and so we’ll just print a message to the console telling us that it’s empty. Then we’ll delete the node that m_head is pointing to, as that is the first node in the list, and set m_head to point to the next node in line, as that is now the new first node in the list. Lastly we decrease the m_size variable by one, as we have removed a node from the list.

Next we look at the pop_back method:

void List::pop_back()
{
if (m_head == nullptr)
{
std::cout << ”No nodes in list, cannot pop back” << std::endl;
}
else
{
m_current = m_head;
m_temporary = m_head;

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

if (m_current == m_head)
{
delete m_head;
m_head = nullptr;
}
else
{
delete m_current;
m_current = m_temporary;
m_current->next = nullptr;
}

m_size–;
}
}

Once again we start by checking if the m_head pointer is pointing to NULL, which will tell us if the list actually has any nodes or not. We then go through the list with the use of a while loop that loops as long as the next reference is not pointing to NULL, if it does the last node in the list has been reached. We also make sure that the m_temporary pointer is always one step behind the m_current as we go through the list. That way, when we delete the last element, the next reference can easily be change to point to NULL since it is the new last node in the list. Lastly we decrease the m_size variable by one, as we have removed a node from the list.

Now we are going to take a look at the clear method:

void List::clear()
{
if (m_head != nullptr)
{
m_current = m_head;
while (m_current->next != nullptr)
{
m_temporary = m_current->next;
delete m_current;
m_current = m_temporary;
m_size–;
}
delete m_current;
m_current = nullptr;
m_size–;
m_temporary = nullptr;
m_head = nullptr;
}
}

This method goes through the entire list and deletes every node. I’m not going to go as much into detail about each method from now on as I believe you have a firm grasp on the linked list structure by now. Note how the m_current and m_temporary pointers are used to go through the entire list.

Next method, Erase:

void List::erase(int delData)
{
node* deletionPtr = nullptr;
m_temporary = m_head; // <- !
m_current = m_head; // <- !

while (m_current != nullptr && m_current->data != delData)
{
m_temporary = m_current;
m_current = m_current->next;
}

if (m_current == nullptr)
{
std::cout << delData << ” was not found!” << std::endl;
}
else
{
deletionPtr = m_current;
m_current = m_current->next;
m_temporary->next = m_current;

if (deletionPtr == m_head)
{
m_head = m_head->next;
m_temporary = nullptr;
}

delete deletionPtr;
std::cout << delData << ” was deleted!” << std::endl;
m_size–;
}
deletionPtr = nullptr;
}

This method deletes the first node in the list that contains the entered value.

The print method:

void List::print()
{
if (m_head == nullptr)
{
std::cout << ”No nodes in list, cannot print” << std::endl;
}
else
{
m_current = m_head;
while (m_current != nullptr)
{
std::cout <data << std::endl;
m_current = m_current->next;
}
}

std::cout << std::endl;
}

This method outputs the data for all the nodes in the list. It is very usefull for checking to see if your other methods are behaving as expected.

The search method:

void List::search(int value)
{
if (m_head == nullptr)
{
std::cout << ”No nodes in list, cannot search” << std::endl;
}
else
{
unsigned long int count = 0;
m_current = m_head;

while (m_current != nullptr)
{
if (m_current->data == value)
count++;

m_current = m_current->next;
}

std::cout << count << ” nodes contain ” << value << std::endl << std::endl;
}
}

This method counts how many nodes contain the entered value.

The size method:

int List::size()
{
return m_size;
}

This returns the number of nodes present in the linked list.

Lastly I put a call to the clear method in the destructor in order to prevent memory leakage.

This is all for now as the linked list for integer varibles is done. In the next part I will remake the class as a generic linked list and also polish some of the code.

To be contiued…