How to Implement a linked list with all basic operations in C++

Welcome, future engineers and coding enthusiasts! If you are pursuing a computer science or IT engineering degree, you already know that Data Structures and Algorithms (DSA) form the backbone of your technical skills. Whether you are preparing for your university laboratory exams or gearing up for grueling technical placement interviews at top product and service-based companies, mastering linked lists is non-negotiable.

Today, we are going to demystify one of the most fundamental yet universally feared topics for beginners: the Linked List.

Many students get intimidated by pointers, dynamic memory allocation, and the dreaded “segmentation fault.” But don’t worry. As a senior developer and technical writer who has guided countless students through these concepts, I can assure you that once you visualize how a linked list works, the C++ code will flow naturally from your fingertips.

Grab a cup of chai, open up your favorite IDE (like VS Code or Code::Blocks), and let’s dive deep into building a Linked List in C++ from the ground up.

1. What Exactly is a Linked List?

Before we look at a single line of C++ code, let’s understand the concept in human terms.

Think of a linked list like a series of interconnected web pages on a well-structured engineering blog. The first article (the first node) contains some valuable information (the data), and at the very bottom, it has a hyperlink (the pointer) directing you to the next article. The next article links to the third, and so on, until you reach the final article, which has no further links (a null pointer). These web pages do not need to be stored in the exact same physical space on a server; as long as the hyperlinks are intact, the sequence is preserved.

In computer science terms, a Linked List is a linear data structure made up of interconnected blocks called Nodes. Unlike an array, where elements are stored in contiguous (side-by-side) memory locations, the nodes in a linked list are scattered randomly across the computer’s RAM. They maintain their linear sequence because each node holds the exact memory address of the next node.

Anatomy of a Node

Every single node in a basic Singly Linked List has two primary compartments:

1. Data Part: This holds the actual information. It could be an integer (like roll numbers), a string (like student names), or even complex objects.
2. Next Pointer Part: This is a reference variable (a pointer in C++) that holds the memory address of the very next node in the sequence.

The first node in the list is given a special name: the Head. The last node in the list points to nullptr (or NULL), signaling the end of the line.

2. Array vs. Linked List: Why Do We Need Them?

In almost every technical interview, before asking you to write the code, the interviewer will ask: “If we already have arrays, why do we need linked lists?” Here is the comprehensive engineering answer you should give:

The Problem with Arrays

• Static Size: In standard C++, when you declare an array like int marks[50];, the compiler strictly blocks out memory for exactly 50 integers. If you end up having 51 students, your program crashes or requires complex resizing. If you only have 10 students, you have wasted memory.
• Costly Insertions/Deletions: Imagine an array of 100 elements. If you want to insert a new element at the very beginning (index 0), you have to mathematically shift all 100 existing elements one step to the right to make room. This takes $O(n)$ time and is highly inefficient.

The Power of Linked Lists

• Dynamic Size: Linked lists grow and shrink at runtime. Memory is allocated dynamically using the new keyword in C++ only when a new node is explicitly created. You never waste memory, and you never run out of space (until your RAM is full).
• Efficient Insertions/Deletions: To insert a new node at the beginning of a linked list, you just create the node and change one pointer. No shifting of elements is required! This happens in $O(1)$ constant time.

3. Setting Up the Skeleton in C++

Let’s transition from theory to code. We will implement a Singly Linked List. “Singly” means navigation is a one-way street—you can only move forward from the Head to the Tail.

First, we need to define what a Node looks like. In C++, we can use either a struct or a class. We will use a class to keep our code modular and adhere to Object-Oriented Programming (OOP) principles.

C++

#include <iostream>
using namespace std;

// Defining the structure of a Node
class Node {
public:
    int data;       // The actual data being stored
    Node* next;     // A pointer to the next Node object

    // Constructor to easily initialize a new Node
    Node(int value) {
        data = value;
        next = nullptr; // Always initialize the next pointer to null!
    }
};

What is happening here?

We created a blueprint for a Node. The data stores our integer, and next is a pointer of type Node*. Why Node*? Because it needs to point to another object of the exact same type. We also included a constructor. When we create a new node by passing a value (e.g., new Node(10)), it automatically assigns 10 to data and safely sets next to nullptr to prevent wild, dangling pointers.

Next, we create the actual LinkedList class to manage these nodes.

C++

class LinkedList {
private:
    Node* head; // The starting point of our list

public:
    // Constructor for the Linked List
    LinkedList() {
        head = nullptr; // An empty list has no head
    }
    
    // We will declare our basic operations here shortly!
};

4. Operation 1: Insertion (Adding Data)

Insertion is the process of adding new elements to our list. Depending on the requirement, we can insert a node in three different places: at the beginning (Head), at the end (Tail), or at a specific position.

A. Inserting at the Beginning (Push Front)

This is the simplest and fastest operation.

Logic:

1. Create a brand new node.
2. Make this new node’s next pointer point to whatever the current head is pointing to.
3. Update the head to point to this newly created node.

C++

    void insertAtHead(int value) {
        Node* newNode = new Node(value); // Step 1: Create the node in dynamic memory
        
        newNode->next = head;            // Step 2: Connect new node to the current first node
        head = newNode;                  // Step 3: Shift the head label to the new node
        
        cout << "Inserted " << value << " at the head." << endl;
    }

Time Complexity: $O(1)$ – It takes the exact same amount of time regardless of whether the list has 10 elements or 10 million.

B. Inserting at the End (Append)

To add a node to the very end of the list, we have a challenge: we only know where the head is. We must walk (traverse) through the entire list until we find the last node, and then attach our new node to it.

Logic:

1. Create a new node.
2. If the list is completely empty (head == nullptr), simply make the new node the head.
3. Otherwise, create a temporary pointer (temp) to walk down the list.
4. Keep moving temp forward until temp->next is nullptr (which identifies the last node).
5. Attach the new node: temp->next = newNode.

C++

    void insertAtTail(int value) {
        Node* newNode = new Node(value);
        
        // Edge Case: If the list is completely empty
        if (head == nullptr) {
            head = newNode;
            cout << "List was empty. Inserted " << value << " as the first node." << endl;
            return;
        }
        
        // Step 3 & 4: Traverse to the last node
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next; // Move temp to the next node
        }
        
        // Step 5: Connect the last node to the new node
        temp->next = newNode;
        cout << "Inserted " << value << " at the tail." << endl;
    }

Time Complexity: $O(n)$ – Because we have to traverse $n$ nodes to find the end. (Note: You can optimize this to $O(1)$ if you maintain a separate tail pointer in your class, but for basic university-level understanding, standard traversal is preferred).

C. Inserting at a Specific Position

What if we want to insert data exactly at position 3?

Logic:

1. If the position is 1, just call insertAtHead.
2. Otherwise, traverse the list using a temp pointer until you reach the node just before the desired position (Position – 1).
3. If you reach the end of the list before finding the position, the position is invalid.
4. Connect the new node’s next to temp->next.
5. Connect temp->next to the new node.

C++

    void insertAtPosition(int position, int value) {
        if (position <= 0) {
            cout << "Invalid position!" << endl;
            return;
        }
        
        if (position == 1) {
            insertAtHead(value);
            return;
        }
        
        Node* newNode = new Node(value);
        Node* temp = head;
        
        // Traverse to the node just before the desired position
        // We use position - 2 because we start at 1, and want to stop 1 step prior.
        for (int i = 0; i < position - 2; i++) {
            if (temp == nullptr) {
                cout << "Position out of bounds." << endl;
                return;
            }
            temp = temp->next;
        }
        
        // Insert the new node
        newNode->next = temp->next;
        temp->next = newNode;
        cout << "Inserted " << value << " at position " << position << "." << endl;
    }

5. Operation 2: Traversal (Printing the List)

Building a list is useless if we cannot view the data inside it. Traversal is the act of visiting every single node from head to tail.

Golden Rule of Linked Lists: Never, ever move the head pointer to traverse the list! If you lose the head pointer, you lose your entire list in memory, causing a massive memory leak. Always use a temporary pointer.

C++

    void displayList() {
        if (head == nullptr) {
            cout << "The linked list is currently empty." << endl;
            return;
        }
        
        Node* temp = head; // Start at the head
        cout << "Linked List elements: ";
        
        // Walk through the list until we fall off the end (nullptr)
        while (temp != nullptr) {
            cout << temp->data << " -> ";
            temp = temp->next; // Move to the next node
        }
        cout << "NULL" << endl; // Visual representation of the end
    }

6. Operation 3: Deletion (Removing Data)

Deleting nodes is where C++ engineers must be cautious. Unlike languages with automatic garbage collection (like Java or Python), in C++, if you dynamically allocate memory using new, it is your absolute responsibility to free that memory using delete. Failing to do so causes memory leaks.

A. Deleting the First Node (Delete Head)

Logic:

1. Check if the list is empty. If so, nothing to delete.
2. Create a temporary pointer to hold the current head.
3. Move the head pointer forward to head->next.
4. Delete the old head using the temporary pointer to free the RAM.

C++

    void deleteFromHead() {
        if (head == nullptr) {
            cout << "Cannot delete. List is empty!" << endl;
            return;
        }
        
        Node* temp = head;       // Hold the current head
        head = head->next;       // Shift the head to the second node
        
        cout << "Deleted " << temp->data << " from the head." << endl;
        delete temp;             // CRITICAL: Free the allocated memory!
    }

B. Deleting the Last Node (Delete Tail)

To delete the last node, we must find the second-to-last node so we can sever its connection to the last node and set its next pointer to nullptr.

Logic:

1. If empty, do nothing.
2. If there is only one node, delete it and set head = nullptr.
3. Traverse using a temp pointer, checking temp->next->next. Stop when it is nullptr.
4. Now, temp is at the second-to-last node. Delete temp->next.
5. Set temp->next = nullptr.

C++

    void deleteFromTail() {
        if (head == nullptr) {
            cout << "Cannot delete. List is empty!" << endl;
            return;
        }
        
        // Edge Case: Only one node exists
        if (head->next == nullptr) {
            cout << "Deleted " << head->data << ". The list is now empty." << endl;
            delete head;
            head = nullptr;
            return;
        }
        
        Node* temp = head;
        // Traverse until temp is the second to last node
        while (temp->next->next != nullptr) {
            temp = temp->next;
        }
        
        Node* nodeToDelete = temp->next; // This is the last node
        cout << "Deleted " << nodeToDelete->data << " from the tail." << endl;
        
        temp->next = nullptr;            // Sever the tie
        delete nodeToDelete;             // Free the memory
    }

C. Deleting a Specific Value

If an interviewer asks you to delete a node containing a specific data value (e.g., “Delete the node containing 45”):

C++

    void deleteByValue(int value) {
        if (head == nullptr) {
            cout << "List is empty." << endl;
            return;
        }
        
        // Case 1: The value to delete is at the head
        if (head->data == value) {
            deleteFromHead();
            return;
        }
        
        Node* temp = head;
        Node* previous = nullptr;
        
        // Traverse to find the value
        while (temp != nullptr && temp->data != value) {
            previous = temp;     // Keep track of the node we just left
            temp = temp->next;   // Move forward
        }
        
        // Case 2: We reached the end and didn't find the value
        if (temp == nullptr) {
            cout << "Value " << value << " not found in the list." << endl;
            return;
        }
        
        // Case 3: We found the value. Bypass the temp node.
        previous->next = temp->next; 
        cout << "Deleted node with value " << value << "." << endl;
        delete temp; // Free the memory
    }

7. Operation 4: Searching for an Element

Searching is a basic query to check if a specific element exists within the list. Since elements are not indexed, we must use Linear Search.

C++

    bool search(int key) {
        Node* temp = head;
        int position = 1;
        
        while (temp != nullptr) {
            if (temp->data == key) {
                cout << "Success: Value " << key << " found at position " << position << "." << endl;
                return true;
            }
            temp = temp->next;
            position++;
        }
        
        cout << "Failure: Value " << key << " is not in the list." << endl;
        return false;
    }

8. Putting It All Together: The Complete C++ Program

Now that we have explained every individual piece of the puzzle, let’s assemble it into a single, cohesive, copy-pasteable program. You can run this directly in your local C++ environment.

C++

#include <iostream>
using namespace std;

// 1. Define the Node
class Node {
public:
    int data;
    Node* next;

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// 2. Define the LinkedList Class
class LinkedList {
private:
    Node* head;

public:
    LinkedList() {
        head = nullptr;
    }

    // --- INSERTION OPERATIONS ---
    void insertAtHead(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

    void insertAtTail(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    // --- DELETION OPERATIONS ---
    void deleteFromHead() {
        if (head == nullptr) return;
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    void deleteByValue(int value) {
        if (head == nullptr) return;
        
        if (head->data == value) {
            deleteFromHead();
            return;
        }
        
        Node* temp = head;
        Node* prev = nullptr;
        
        while (temp != nullptr && temp->data != value) {
            prev = temp;
            temp = temp->next;
        }
        
        if (temp == nullptr) return; // Value not found
        
        prev->next = temp->next;
        delete temp;
    }

    // --- TRAVERSAL ---
    void displayList() {
        if (head == nullptr) {
            cout << "List is empty." << endl;
            return;
        }
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "NULL" << endl;
    }
};

// 3. The Main Function to Test Our Code
int main() {
    LinkedList myList;

    cout << "--- Building the Linked List ---" << endl;
    myList.insertAtHead(10); // List: 10 -> NULL
    myList.insertAtHead(5);  // List: 5 -> 10 -> NULL
    myList.insertAtTail(20); // List: 5 -> 10 -> 20 -> NULL
    myList.insertAtTail(30); // List: 5 -> 10 -> 20 -> 30 -> NULL
    
    myList.displayList();    // Output: 5 -> 10 -> 20 -> 30 -> NULL

    cout << "\n--- Deleting Operations ---" << endl;
    myList.deleteFromHead(); // Removes 5
    myList.displayList();    // Output: 10 -> 20 -> 30 -> NULL

    myList.deleteByValue(20); // Removes 20
    myList.displayList();    // Output: 10 -> 30 -> NULL

    return 0;
}

9. Common Mistakes and “Segmentation Faults” (Pro-Tips)

As an engineering student, your compiler will throw errors at you. The most notorious error when working with linked lists is the Segmentation Fault (Core Dumped).

Why do Segmentation Faults happen?

A segmentation fault occurs when your code tries to read from or write to a memory location that it does not have access to. In linked lists, this almost always happens for two reasons:

1. Dereferencing a Null Pointer: If temp is nullptr, and you try to access temp->data or temp->next, the program will crash instantly. Always check if (temp != nullptr) before accessing its properties.
2. Infinite Loops: If you forget to update your traversing pointer (temp = temp->next), your while loop runs forever, eventually crashing your system.

Engineering Best Practice: The Destructor

In production-level C++, when an object is destroyed, it should clean up after itself. If our LinkedList goes out of scope, the nodes it created via new will remain stuck in the RAM as a memory leak. A good developer always writes a destructor ~LinkedList() to delete all remaining nodes automatically when the program finishes.

C++

    // Destructor to prevent memory leaks
    ~LinkedList() {
        Node* temp = head;
        while (temp != nullptr) {
            Node* nextNode = temp->next; // Save the next node
            delete temp;                 // Delete the current node
            temp = nextNode;             // Move to the saved next node
        }
        // All dynamically allocated RAM is now safely returned to the OS.
    }

10. Frequently Asked Questions (FAQs)

To make sure we cover everything you might be tested on, here are the most searched questions regarding C++ linked lists.

Q1: What is the main difference between a Singly Linked List and a Doubly Linked List?

Answer: In a singly linked list, each node only contains a pointer to the next node. You can only move forward. In a Doubly Linked List, every node contains two pointers: one pointing to the next node, and another pointing to the previous node. This allows backward traversal but consumes more memory.

Q2: Can I implement a linked list in C++ without using class or Object-Oriented Programming?

Answer: Absolutely. You can use a basic struct Node and write procedural functions (e.g., void insertNode(Node** head, int data)) using double pointers. However, using a class encapsulates the data and methods cleanly, which is the industry standard for modern C++ development.

Q3: What is a Circular Linked List?

Answer: A circular linked list is a variation where the next pointer of the very last node does not point to NULL or nullptr. Instead, it points back to the head (the first node), forming a continuous, infinite loop. This is heavily used in operating systems for tasks like CPU scheduling (Round Robin).

Q4: Is an array faster or a linked list?

Answer: It depends entirely on the operation. If you need to search for an element or access data frequently by its position (e.g., “Give me the 500th item”), Arrays are significantly faster because of $O(1)$ random access. If your application involves constant insertions and deletions at the beginning of the dataset, Linked Lists are vastly superior.

Q5: Why do we use new and delete in C++ linked lists instead of malloc and free?

Answer: While malloc and free (inherited from C) do allocate and deallocate memory, they do not call the constructors or destructors of C++ objects. Using new allocates memory and immediately calls the constructor to properly initialize the Node (like setting next to nullptr), making it much safer for object-oriented C++.

Also read,  What is Machine Learning?