Understanding Linked Lists and Implementing them in C++

Linked List is a linear data structure. The major difference linked lists have from arrays is that the elements in a linked list are not stored in contiguous memory location. In this post, we will be understanding linked lists and also implementing various linked list related operations in C++.

If you are completely new to Data Structures, I will recommend you to first go through our introduction to arrays. That will help you grasp the concepts and differences to linked lists in a better way. However, if you already have a fair idea about arrays, then you can simply continue with this post.

So without wasting more time, let’s dive straight into Linked Lists.

1 – What are Linked Lists?

The defining feature of a Linked List is that each element in the list points to the next element. So even though the elements are not stored in contiguous memory locations, it becomes easy to traverse through the list using the link-structure.

We can visualize linked lists in the form of a chain.

In more of a computer science terminology, we can say that each element in the linked list is like a node. Typically, a node comprises of two things : the data itself and the reference to the next node.

The first element in the linked list is known as the Head of the linked list. The last element is known as the Tail. The tail basically points to the NULL denoting the end of the list.

2 – Implementing Linked Lists in C++

Unlike arrays, linked lists are not part of all programming languages. Often times, we have to implement linked lists. Also, implementing data structures provides us with a much deeper understanding as well.

Below is an implementation of the linked list in C++.

#include <iostream>

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

class linked_list
{
private:
    node *head;
    node *tail;

public:
    linked_list()
    {
        head = NULL;
        tail = NULL;
    }

    void add_node(int data)
    {
        node *tmp = new node;
        tmp->data = data;
        tmp->next = NULL;

        if (head == NULL)
        {
            head = tmp;
            tail = tmp;
        }
        else
        {
            tail->next = tmp;
            tail = tail->next;
        }
    }

    node *remove_node(int data)
    {
        if (head->data == data)
        {
            head = head->next;
            return head;
        }

        node *current;
        node *previous;
        current = head->next;
        previous = head;

        while (current != NULL)
        {
            if (current->data == data)
            {
                previous->next = current->next;
                return current;
            }
            previous = current;
            current = current->next;
        }

        return NULL;
    }

    node *find_node(int data)
    {
        node *tmp;
        tmp = head;

        while (tmp != NULL)
        {
            if (tmp->data == data)
            {
                return tmp;
            }
            tmp = tmp->next;
        }

        return NULL;
    }

    void traverse()
    {
        node *tmp;
        tmp = head;

        std::cout << "Traversing Linked List..." << std::endl;
        while (tmp != NULL)
        {
            std::cout << tmp->data << std::endl;
            tmp = tmp->next;
        }
    }
};

int main()
{
    linked_list ll;
    ll.add_node(5);
    ll.add_node(8);
    ll.add_node(10);
    ll.add_node(13);
    ll.traverse();

    node *search_node;
    search_node = ll.find_node(15);

    if (search_node != NULL)
    {
        std::cout << "Found Node: ";
        std::cout << search_node->data << std::endl;
    }

    node *remove_node;
    remove_node = ll.remove_node(5);
    if (remove_node != NULL)
    {
        std::cout << "Removed Node: ";
        std::cout << remove_node->data << std::endl;
    }
    ll.traverse();

    return 0;
}

Let’s understand each of the parts in more detail:

2.1 – The Node

The Node structure comprises of the data which is an int in this case. Also, we have the next variable which stores a reference to the next element.

This structure is basically the building block of our linked list implementation.

2.2 – Linked List Class

Next, we have the Linked List class. This class basically implements all the major operations that we support for a linked list.

As private variables, we have reference to the head and the tail of the linked list. These variables are private so that no one can access them directly from outside the class.

Then, we have the public methods that allow us to manipulate the data in the linked list. Basically, these comprise of various operations for a linked list such as adding a new element, removing an element, traversing the linked list and finding an element within the list.

2.3 – Adding a New Element

This is one of the most frequent operations we perform on a linked list after instantiating it.

We usually add elements to the end of the linked list. If the list is empty, that means adding the head of the list. However, if the list is not empty, we have to add the new element to the tail of the list.

Adding an element to the end of the linked list has a time complexity of O(1). This is because we have access to the head and tail of the linked list and therefore can easily update the next pointer to the new node.

2.4 – Traversing the List

Traversal is also a pretty frequent operation for a linked list. Basically, traversal comes into the picture when we want to process every element in the linked list for some purpose.

To traverse a list, we start from the head of the list. For every iteration, we process the current node and update the current node to the next node. Once we reach NULL, we can be sure that it is the end of the linked list.

The time complexity of traversal is linear in nature i.e. O(n).

2.5 – Finding An Element In the List

This is pretty similar to the traversal operation except for the fact that once we find the element we are looking for, we can simply return that element and stop the traversal.

If we don’t find the element, we return NULL.

This operation also has a worst-case time complexity of O(n). This is because if the element we are searching for is at the end of the linked list, we have to traverse the entire list.

2.6 – Removing an Element

If we remove an element from the head or the beginning of the linked list, we can do it very easily by simply updating the head of the list and returning the old head.

This operation can be done in constant time complexity or O(1). This is because unlike arrays, we don’t have to re-index other elements.

However, removal from anywhere else in the list(including the end) has a linear time complexity i.e. O(n). This is because we cannot directly reach the element and instead have to traverse to that element and then update the next pointer accordingly. We also have to keep track of the previous node at all times.

With this, we have completed our understanding linked lists topic. Also, we have looked at all the major operations on a linked list and implemented them using C++ structure and classes.

Linked List is one of the fundamental data structure that helps us build more complex data structures.

If you have any comments or queries about this, please feel free to write in the comments section below.