Understanding Linked Lists as Custom Data Structures in C++

Before we start learning about linked lists in C++, you may want to read my previous post explaining custom and built-in data structures in C++. That will help you understand what data structures are, especially in C++.

The Hydra Canyon (Hercules Action Game PS1 )

In the previous article, we discussed how using a struct in C++ can make code simpler because members are public by default. This is especially convenient for simple data containers like a Point or a Node in a linked list.

For example, a basic linked list node using a struct can look like this:

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

Creating and linking nodes is straightforward:

Node* head = new Node{10, nullptr};
Node* second = new Node{20, nullptr};
head->next = second;

Everything is simple, readable, and easy to follow.

So Why Does Hackerrank Use Classes and Look More Complex?

Hackerrank’s linked list template can look complicated at first, especially compared to a simple struct-based linked list:

class SinglyLinkedListNode {
public:
    int data;
    SinglyLinkedListNode* next;
    SinglyLinkedListNode(int node_data) {
        this->data = node_data;
        this->next = nullptr;
    }
};

class SinglyLinkedList {
public:
    SinglyLinkedListNode* head;
    SinglyLinkedListNode* tail;

    SinglyLinkedList() {
        this->head = nullptr;
        this->tail = nullptr;
    }

    void insert_node(int node_data) {
        SinglyLinkedListNode* node = new SinglyLinkedListNode(node_data);
        if (!this->head) this->head = node;
        else this->tail->next = node;
        this->tail = node;
    }
};

At first glance, it seems more complex than necessary. The design, however, has specific purposes.

Object-Oriented Style

Hackerrank uses classes to follow object-oriented programming principles. The SinglyLinkedList class encapsulates the logic of the list by automatically tracking the head and tail pointers. The insert_node method ensures nodes are inserted correctly without manually adjusting pointers. Even though the node’s data and next pointer are public, the class separates list operations from individual nodes. This approach makes the code more consistent and professional, especially for teaching and automated testing.

Constructors for Safe Node Initialization

The constructor in SinglyLinkedListNode guarantees that every node starts with its next pointer set to null:

SinglyLinkedListNode(int node_data) {
    this->data = node_data;
    this->next = nullptr;
}

Without a constructor, you would need to manually initialize the next pointer each time. Constructors reduce repetitive code and make node creation safer.

Automatic Tail Management

Storing a tail pointer in the SinglyLinkedList class allows insertion at the end of the list in constant time. Without the tail pointer, adding a node would require traversing the entire list, which is less efficient and more error-prone.

Using Structs Instead of Classes

Structs in C++ can have constructors, methods, and member functions just like classes. The main difference is that struct members are public by default. The same linked list can be implemented with structs:

#include <iostream>
using namespace std;

struct SinglyLinkedListNode {
    int data;
    SinglyLinkedListNode* next;

    // Constructor
    SinglyLinkedListNode(int node_data) {
        data = node_data;
        next = nullptr;
    }
};

struct SinglyLinkedList {
    SinglyLinkedListNode* head;
    SinglyLinkedListNode* tail;

    // Constructor
    SinglyLinkedList() {
        head = nullptr;
        tail = nullptr;
    }

    // Insert node at the end
    void insert_node(int node_data) {
        SinglyLinkedListNode* node = new SinglyLinkedListNode(node_data);
        if (!head) head = node;
        else tail->next = node;
        tail = node;
    }
}; 

int main() {
    SinglyLinkedList list;
    list.insert_node(10);
    list.insert_node(20);
    list.insert_node(30);

    SinglyLinkedListNode* current = list.head;
    while (current) {
        cout << current->data << endl;
        current = current->next;
    }

    // Free memory
    current = list.head;
    while (current) {
        SinglyLinkedListNode* temp = current;
        current = current->next;
        delete temp;
    }

    return 0;
}

This struct-based version behaves exactly the same as the class version, but it is simpler and easier to read.

Can We Print Data from the Simplest Linked List Version Like in HackerRank?

A question that comes to mind is: can we add data and print it using the simplest version of a linked list, like this?

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

Yes, we can, simply by using a function like this to add the data:

void insertNode(Node*& head, int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = nullptr;

    // If the list is empty
    if (head == nullptr) {
        head = newNode;
        return;
    }

    // Traverse to the end
    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }

    temp->next = newNode;
}

The *& combination is actually two things:

1. **** → This is part of `Node, meaning “pointer to Node.” SoNode* head` is a pointer to a node.
2. **& → This means we are passing the pointer by reference**.

Why do we need & here?

If we wrote it like this:

void insertNode(Node* head, int data)

• head is passed by value, which means a copy of the pointer is made.
• If the list is empty (head == nullptr) and we try to assign head = newNode;, it would only change the copy inside the function.
• The original head in main() would remain nullptr.

Example:

Node* head = nullptr;
insertNode(head, 10); // head stays nullptr if we don't use &!

By using Node*& head, we are passing the pointer itself by reference, so any changes to head inside the function affect the original pointer in main().

Quick analogy

• Node* head → You have a copy of the address of the first node.
• Node*& head → You have a reference to the original address variable, so you can change where it points.

Without &, you’d have to return the new head:

Node* insertNode(Node* head, int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = nullptr;

    if (!head) return newNode; // return new head

    Node* temp = head;    
    while (temp->next != nullptr) temp = temp->next;
    temp->next = newNode;

    return head;
}

// usage
head = insertNode(head, 10);

Using *& just avoids returning and lets you modify head directly.

What if we want to print the data?

We can use the same approach we used to solve the “Print the Elements of a Linked List” problem on HackerRank.

// Function to print the linked list
void printLinkedList(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << endl;
        temp = temp->next;
    }
}

Okay, Now What Is a Linked List and What Is It Used For?

A linked list is a way to store a group of data items in order. Instead of keeping everything next to each other in memory (like an array), each item in a linked list is stored in a separate piece called a node.

Each node contains two things:

1. The data (the value you want to store)
2. A reference (or link) to the next node in the list

Because of this, the nodes are connected like a chain.

How a Linked List Works

A linked list starts with a special node called the head. The head points to the first node in the list. Each node then points to the next one, and the last node points to null, which means the list ends there.

You move through a linked list by following these links, one node at a time.

Why Use a Linked List?

Linked lists are useful when:

• You need to add or remove data easily
• You don’t know the size of the data in advance
• You want to avoid shifting elements like you would in an array

For example, inserting a new element in the middle of an array can be slow because everything after it must move. In a linked list, you only change a few links.

Common Uses of Linked Lists

Linked lists are often used for:

• Implementing stacks and queues
• Managing dynamic memory
• Navigating items (like undo/redo actions)
• Handling large amounts of data where frequent changes are needed

Linked Lists vs Arrays (Simple View)

• Arrays are fast to access but hard to resize
• Linked lists are easy to resize but slower to access

Final Thoughts

A linked list is a simple but powerful data structure. It may not always be the fastest option, but it’s very flexible and great for situations where data changes often.

Once you understand linked lists, many other data structures become easier to learn.

Thank you for reading!

If you have any questions, feel free to ask — I’d be happy to explain more.