C++ Linked List Implementation – Detailed Guide

We will be walking through the singly linked-list implementation in C++. Readers, be warned: this post is NOT on the theoretical aspects of the linked list. I am assuming that readers have a basic understanding of what the linked list is about. The post will be more focused on the implementation details. However, for those that don't fully understand linked list, a bit of theory will accompany some of the explanations.

For those that are interested in the the theory behind linked-lists, please check out my other post on linked lists in Java. In the future, I will write a language agnostic post on linked lists. 

As mentioned in my other post, the linked list is a fundamental data structure. Therefore, I believe every developer who is serious about data structures and algorithms should fully understand it.​

​In the real world, the linked list is not an ideal data structure to use in most cases. Its use cases are very situational. However, understanding how it works, what it does and when to use it train developers to write better code. It also equips the developers to become better problem solvers. Furthermore, the concepts involved in linked lists is used to create other useful data structures such as the stack data structure. 

Metaphorically, the linked list is one of the stepping blocks to greatness in the world of data structures and algorithms.​

More...

1. Pre-requisites

​The linked list is a simple data structure. Therefore, the requirements are not high. However, readers should have

  • A decent working knowledge of object-oriented programming
  • Good working knowledge of the C++ programming language.
  • Clear understanding of the linked list as a data structure. While this is not an absolute requirement, it is certainly recommended.

2. Warning: Memory Management

In contrast to Java and other high level programming languages, in C++, we need to manage our own memory. Therefore, we need to be careful when writing methods. When we are done with an object that is stored on the heap memory, we need to manually remove it from the heap.

Failure to do so will result in a memory leak. If I were to paraphrase, if memory is not freed up, that space in your computer will still be occupied, even after the program finishes running and exits. The only way to reclaim that memory would be to reboot the computer, which kind of sucks.

Memory leaks are often one of the most nastiest bugs to both the user and the developer. To the developer, it is not a bug that stands out in your face, especially in a language like C++. In the case of a large-scale application, it might take days or even weeks before a server runs out of memory thanks to that leak. ​To the users, must I even mention why a memory leak stinks? To prevent myself from going Godzilla on this post, I will just state that a program with a memory leak error will eat the user's memory gradually and slow down their PC. 

Okay, we have established that memory management is important. With that aside, let's dive into building a linked list.

3. Creating the Node Structure

In C++ structures are metadata​. In another words, structures are used to store other data or a collection of data. On the downside, structures cannot have built-in methods. In this implementation, I don't see the need for nodes to have built-in methods. 

If readers wish to add methods to their structure, please feel free to create the Node as a class.​ Implementing the Node as a struct is simply a single choice out of many options.

 typedef struct Node
{
int data;
Node *nextNode;
} * node_ptr;

In the code snippet above, we created a typedef and named it nodePtr. The aforementioned variable is a pointer to a Struct which contains the data itself and a pointer to the next node. This enables us to declare the struct by simply typing the following

node_ptr headNode;

If we did not define it as a typedef, we would have to type the following

Node *nodePtr;

If however, we were dealing with a doubly linked list, inside of the struct, we would declare another Node pointer, like below

Node * backPointer;

We would also change the existing node_ptr variable to something more meaningful like forwardPointer.

4. The Linked List Implementation Details

Lo and behold! This section will contain the meat, as well as a detailed analysis of the implementation details. Please do note however, that I will assume that readers know the basics of C++ programming, but is still well on their way to achieving mastery over the language. The implementation is designed to enable users to read, understand, and implement their own linked list on their own. Therefore, I have written the code in a manner that is relatively beginner-friendly. Feel free to take this implementation and refactor it. 

4.1 The Add() Method​

In this implementation, we will be adding data to the front of the linked list. Assuming that our linked list has a reference to the first node (known as the head), the operation can be done in O(1) constant time. Let us take a look at the steps required to add a new node.

  1. Create a new node with the newly inserted data.
  2. Check whether the list is empty. If it is empty, simply set the newly created node as the head.
  3. If the list is not empty, after setting the newly created node as the head, have the new head;s next pointer point to the previous head. 
  4. Finally, increment the size counter.

For example, lets take a look at the following example. Suppose that we are inserting node 2 as a new element into a list that already has element 1 as the head. Before the insertion the list would look like the following

1 –> NULL 

After inserting 2, assuming that the newly inserted element (I.E, 2) becomes the new head, the linked list will now look like this

2 –> 1 —> NULL.

Hopefully this makes sense. Please note that this implementation is purely for demonstration purposes. Users if they choose to can implement an add method that adds to any particular index / place. Depending on how this is implemented, the aforementioned operation can take O(1) or O (N) time. 

void List::Add(int data)
{
// Step 1.
node_ptr newNodePtr = new Node;
newNodePtr->data = data;
newNodePtr->nextNode = nullptr; // Initialize all the fields

// Step 2.
if (IsEmpty())
{
this->head = newNodePtr;
}
// Step 3.
// List already contains a node.
// Therefore, add the node to the front of the linked list.
else
{ // Get reference to current head.
node_ptr prevHeadPtr = this->head; // Set newly inserted node to be new head.
this->head = newNodePtr; // Set new head to point to previous head.
newNodePtr->nextNode = prevHeadPtr;
// Step 4.
IncrementSize();
}

 

4.2 The Remove() Method

As I mentioned earlier, when deleting nodes, it is important to be mindful of how data is linked and being stored. Failure to do so could result in orphaned nodes, which could potentially result in memory leaks. 

In our implementation, Remove(data) will return true if the data was successfully removed. Otherwise, if the item could not be found, the operation will return false.  The remove method works as follows.

  1. Check if the list is empty. Return false if the list is empty, since there is nothing to remove.
  2. Otherwise, traverse through the list until we find the element that is equal to the one that we want to remove.
  3. Once we have found the element, link the previous node to the next node of the element that is to be destroyed. For example, the result will look something like the following. In the example,we will be removing 2. 
    • Before removal: 1 –> 2 –> 3 –> NULL
    • After removal: 1 –> 3 –> NULL.
  4. Finally, delete the node using the delete keyword.
  5. Decrease the size of the list by one and return true.

Hopefully, the logic above makes sense. If not, please do take time to go through the logic again. I also highly recommend readers to try writing out the pseudo code. Writing pseudo code is a great way to organize your thoughts. After understanding the logic above, feel free to move onto the next section. We will be examining the code block for this particular piece of logic. 

4.2.1 Digging into the Source Code - Finding the node to remove

Okay, let us examine the code for the actual implementation details. Before proceeding, please download the singly linked list in C++ source code from GitHub. I will not be adding the entire source code into this sub-section. 

First of all, we need to search for the following node. We do so by iterating through the entire list from the start, using pointers.

 // Point to the previous node. Used when joining nodes
node_ptr prevNodePtr = nullptr;
node_ptr currentNodePtr = head;

if (IsEmpty())
{
return false;
}
while (currentNodePtr != nullptr)
{
// Found data to remove. Perform remove operation.
if (data == currentNodePtr->data)

But wait, we have a pointer to a previous node? Why do we need that? It is because we need to do the following operation. After finding the node we want to remove, we need to link the previous node with the next node of the node to be removed. If what I stated does not make sense, please refer to the diagram below. 

Diagram showing the removal process in singly linked list

Hopefully, it is now clear as to why we have the previous node pointer. Before proceeding onto examining the actual deletion process, let us also take a look at what deleting the head node looks like.

Visual illustration of removing head node from singly linked list

4.2.2 Digging into the Source Code - Deletion

Now that we found the node to remove, we now need to consider the following cases.

  1. The node we want to remove is the head node.
    • If so, we need to set the next node as the new head.
  2. If the node  we want to remove is not the head node, simply link the previous node to the next node.

Simple right? Let us examine the source.

 node_ptr nodeAfterCurrentPtr = currentNodePtr->nextNode;

// 1. Deleting the head
if (prevNodePtr == nullptr)
{
// Set the node after current Ptr as new head
this->head = nodeAfterCurrentPtr;
}
// 2. Deleting a node that is not the head.
else
{
// Set previous node to point at node after the one to delete
prevNodePtr->nextNode = nodeAfterCurrentPtr;
}

// Deallocate from heap memory.
delete currentNodePtr;

DecrementSize();

return true;

As you can see, after updating the pointers, the steps are the same regardless of whether the node we want to remove is a head node or not. We delete the node and afterwards, decrease the size property of the linked list by 1.

If we do NOT delete the node, there will be a memory leak inside of our linked list, which will spell disaster. It is imperative that readers do not forget to free up the memory.

4.3 Emptying the List after Use

In C++, we need to manually delete all the objects that were created with the new keyword. Ideally, we do this in the destructor, which is called when the linked-list object goes out of scope or is manually deleted using the delete keyword.

We need to iterate through the entire linked list and manually remove these objects from the heap. This process takes O(N) time.  

// Free memory
void List::EmptyList()
{
node_ptr currentNodePtr;
while (this->head != nullptr)
{
currentNodePtr = this->head;
this->head = this->head->nextNode; // Head points to next node
delete currentNodePtr; // afterwards, delete current node
}
this->sz = 0; // set Length to zero.
}

In the example above, we delete the currentNodePtr which points at the head. Before doing so, we also point the head to the next element and repeat these steps until we reach the null pointer. This way, all the memory is freed and there will be no memory leaks.

Ideally, we free up the memory, when the linked list object is destroyed. Therefore, we will call ​EmptyList() in our destructor like the following

List::~List()
{
std::cout << "Destroying linked list ... " << std::endl;
this->EmptyList();
}

5. Linked List Data Structure Quiz

For those that want to test their knowledge, feel free to take the quiz below. Note that the quiz is a work in progress and will continuously be updated as time allows. 

Feedback on what questions to add, and also on the quality of the questions would definitely help speed up the process as well. 

Enjoy!

6. Source Code and Final Words

As always, the source code can be found on GitHub. For more information, please stay in tune. I will be writing another post on a generic linked list implementation in the near future. 

If you want more practice on the linked list, try and work on the following exercises. They should give you a good workout. 

  • Create a doubly linked list with a pointer pointing forward and another one pointing backwards.
  • Enable users to add data to the back of the list in O(1) constant time.
  • Afterwards, try creating a copy constructor that is capable of cloning the linked list passed to the right hand side.

Once again, thank you for reading and please leave a comment if you wish to provide feedback. Encouragements are also highly welcome 🙂

 

About the Author Jay

I am a programmer currently living in Seoul, South Korea. I created this blog as an outlet to express what I know / have been learning in text form for retaining knowledge and also to hopefully help the wider community. I am passionate about data structures and algorithms. The back-end and databases is where my heart is at.

follow me on: