Manas Ranjan

Posted on Oct 29

C++ Linked List Tutorial for Beginners: Concepts, Examples & Logic Explained

#cpp #programming #datastructures #beginners

🧭 Table of Contents

🧠 Introduction: Mastering Linked Lists From Scratch
🔍 What is a Linked List?
🧩 Structure of a Node
⚙️ Basic Operations on Singly Linked List
💻 Complete Code with Example Output
🧠 Key Takeaways
💡 Things to Keep in Mind
🧩 Singly Linked List Practice Questions
✨ Wrapping Up
✍️ About the Author

🧠 Introduction: Mastering Linked Lists From Scratch, Like a Human

If you’ve just started learning Data Structures, you’ve probably heard the term Linked List thrown around a lot.

It sounds complicated like something only pros understand but in reality, a linked list is just a chain of connected boxes, each holding some data and a link to the next box.

Think of it like this:

You’re standing in a line of friends. Each person remembers only one thing who’s next in line.

That’s your linked list. You know your neighbor, and that’s enough to keep the chain connected.

Unlike arrays, where everything sits together in one continuous block of memory, linked lists are scattered each node living wherever it finds space, linked by pointers.

This makes them flexible, dynamic, and incredibly useful for problems where the size of data keeps changing.

In this post, we’ll learn Linked Lists the human way step by step, visually, and logically.

Instead of memorizing code, you’ll understand what’s happening in memory, why pointers are used, and how to think through every operation (insertion, deletion, searching, etc.).

By the end, you’ll not only be able to write linked list programs in C++, but also explain how they work something every good developer should be able to do.

What is a Linked List?

A Linked List is a linear data structure in which elements (called nodes) are connected using pointers.

Each node contains:

data → stores the value
next → pointer to the next node

Unlike arrays, linked lists are dynamic (memory is allocated at runtime).

Structure of a Node

// Definition of a Node class used in a Linked List
class Node {
public:
    int data;      // Stores the value or data part of the node
    Node* next;    // Pointer to the next node in the linked list

    // Constructor to initialize a new node with a given value
    Node(int val) {
        data = val;   // Assign the passed value to the data field
        next = NULL;  // Initially, the next pointer is set to NULL (no next node yet)
    }
};

Basic Operations on Singly Linked List

1️⃣ Create and Print a Linked List

📘 Concept:

Create n nodes dynamically and connect them using next pointers.

🔍 What’s Happening

Think of creating a linked list as building a chain of connected boxes.

Each box (Node) has:

a value (data)
an arrow pointing to the next box

When you create a linked list, you’re essentially:

Creating a first node → this becomes your head (starting point)
Then, each time you create a new node, you connect it to the previous node’s next pointer

When printing, you start from the head and follow the arrows until you hit NULL.

At each step, print the data.

💡 Real World Analogy

It’s like walking along train compartments each one has a door to the next, until you reach the end.

💻 Code:

#include <iostream>
using namespace std;

// Definition of the Node class (represents a single element in the linked list)
class Node {
public:
    int data;       // Stores the data/value of the node
    Node* next;     // Pointer to the next node in the linked list

    // Constructor to initialize a node with a given value
    Node(int val) {
        data = val;   // Assign the input value to the data part
        next = NULL;  // Initially, there is no next node (so next is NULL)
    }
};

// Function to print all elements of the linked list
void printList(Node* head) {
    Node* temp = head;  // Temporary pointer to traverse the list
    while (temp != NULL) {  // Loop until we reach the end of the list
        cout << temp->data << " ";  // Print the data of the current node
        temp = temp->next;          // Move to the next node
    }
    cout << endl;  // Print a newline after the entire list is displayed
}

int main() {
    Node* head = NULL;  // Pointer to the first node (head) of the linked list
    Node* tail = NULL;  // Pointer to the last node (tail) to easily add new nodes
    int n;              // Number of nodes the user wants to create

    cout << "Enter number of nodes: ";
    cin >> n;  // Input how many nodes to create

    // Loop to create 'n' nodes
    for (int i = 0; i < n; i++) {
        int val;
        cout << "Enter value: ";
        cin >> val;  // Input the data value for each node

        Node* newNode = new Node(val);  // Dynamically create a new node

        // If the list is empty, the new node becomes both head and tail
        if (head == NULL) {
            head = tail = newNode;
        } 
        // Otherwise, link the new node to the end of the list
        else {
            tail->next = newNode;  // Connect the last node to the new one
            tail = newNode;        // Update tail to point to the new last node
        }
    }

🧪 Example:

Input:
Enter number of nodes: 3
Enter values: 10 20 30
Output:
Linked List: 10 20 30

2️⃣ Count Nodes

📘 Problem Statement

Given the head of a linked list, count how many nodes are present in it.

🔍 Logic Explanation

Start from the head node.
Initialize a counter to 0.
Move through each node, increasing the counter by 1.
Stop when next becomes NULL.
The counter will represent the total number of nodes.

💡 Like counting train compartments while walking from the first to the last.

💻 Code:

// Function to count the total number of nodes in a linked list
int countNodes(Node* head) {
    int count = 0;        // Variable to keep track of the number of nodes
    Node* temp = head;    // Temporary pointer to traverse the list (starting from head)

    // Traverse the entire linked list until we reach the end (NULL)
    while (temp != NULL) {
        count++;          // Increment count for each node visited
        temp = temp->next; // Move to the next node
    }

    // Return the total count after traversal
    return count;
}

3️⃣ Insert a Node at the Beginning

🔍 What’s Happening

You want to add a new node before the current head.

💡 Logic:

Create a new node
Set newNode->next = head
Move head = newNode

💻 Code:

// Function to insert a new node at the beginning of the linked list
void insertAtBeginning(Node* &head, int value) {
    // Step 1: Create a new node with the given value
    Node* newNode = new Node(value);

    // Step 2: Point the new node's 'next' to the current head of the list
    // (This makes the new node link to the previous first node)
    newNode->next = head;

    // Step 3: Move the head pointer to point to the new node
    // (Now the new node becomes the first node in the list)
    head = newNode;
}

4️⃣ Insert a Node at the End

🔍 What’s Happening

You need to attach a new node after the last one

💡 Logic:

Start at head and keep moving until next == NULL
That’s your last node
Create a new node and set the last node’s next to it
The new node’s next is NULL

💻 Code:

// Function to insert a new node at the end of the linked list
void insertAtEnd(Node* &head, int value) {
    // Step 1: Create a new node with the given value
    Node* newNode = new Node(value);

    // Step 2: If the list is empty, make the new node the head
    if (head == NULL) {
        head = newNode;  // The new node becomes the first and only node
        return;          // Exit the function since insertion is done
    }

    // Step 3: Otherwise, traverse to the last node
    Node* temp = head;
    while (temp->next != NULL)  // Move forward until we find the last node
        temp = temp->next;

    // Step 4: Link the last node to the new node
    temp->next = newNode;
}

5️⃣ Insert at Specific Position

🔍 What’s Happening

Say you want to add a node in between not at the start or end.

Example: Insert 25 between 20 and 30.

Steps:

Start at head and move till you reach the (position - 1) node
Create a new node
Make the new node’s next point to the current node’s next
Change current node’s next to point to the new node

// Function to insert a new node at a specific position in the linked list
void insertAtPosition(Node* &head, int value, int pos) {
    // Step 1: If position is 1, insert the new node at the beginning
    if (pos == 1) {
        insertAtBeginning(head, value);  // Reuse the function you already created
        return;  // Exit after insertion
    }

    // Step 2: Create a new node with the given value
    Node* newNode = new Node(value);

    // Step 3: Traverse the list to find the (pos-1)th node
    Node* temp = head;
    for (int i = 1; i < pos - 1 && temp != NULL; i++)
        temp = temp->next;

    // Step 4: If temp becomes NULL, it means the position is invalid
    if (temp == NULL)
        return;

    // Step 5: Adjust the links to insert the new node at the desired position
    newNode->next = temp->next;  // Link new node to the next node
    temp->next = newNode;        // Link previous node to the new node
}

6️⃣ Delete First Node

📘 Problem Statement

Delete the first node (head) from a linked list.

🔍 Logic Explanation

Check if the list is empty (head == NULL). If yes, nothing to delete.
Store the address of the current head in a temporary pointer (so we can free it later).
Move head to the next node (head = head->next).
Delete the old head node using delete temp.

💡 We just skip over the first node and make the second one the new head.

// Function to delete the first node (head) of the linked list
void deleteFirst(Node* &head) {
    // Step 1: Check if the list is empty
    if (head == NULL)
        return;  // Nothing to delete if the list is already empty

    // Step 2: Store the current head node in a temporary pointer
    Node* temp = head;

    // Step 3: Move the head pointer to the next node
    head = head->next;

    // Step 4: Delete the old head node to free memory
    delete temp;
}

7️⃣ Delete Last Node

📘 Problem Statement

Delete the last node of a linked list.

🔍 Logic Explanation

If the list is empty, return.
If it has only one node, delete it and make head = NULL.
Otherwise:
- Traverse until the second-last node (temp->next->next == NULL).
- Delete the last node using delete temp->next.
- Set temp->next = NULL.

💡 You stop one step before the tail so you can safely cut it off.

// Function to delete the last node of the linked list
void deleteLast(Node* &head) {
    // Step 1: If the list is empty, nothing to delete
    if (head == NULL)
        return;

    // Step 2: If there is only one node, delete it and make head NULL
    if (head->next == NULL) {
        delete head;   // Free memory of the single node
        head = NULL;   // Set head to NULL (list becomes empty)
        return;
    }

    // Step 3: Traverse the list to find the second last node
    Node* temp = head;
    while (temp->next->next != NULL)  // Stop one node before the last
        temp = temp->next;

    // Step 4: Delete the last node and set the second last node’s next to NULL
    delete temp->next;   // Free memory of the last node
    temp->next = NULL;   // Mark the new end of the list
}

8️⃣ Find Maximum and Minimum Value

📘 Problem Statement

Find and print the smallest and largest data values present in a linked list.

🔍 Logic Explanation

If the list is empty, there’s nothing to find.
Initialize two variables minVal and maxVal with the value of the first node.
Traverse through the list:
- If node->data < minVal, update minVal.
- If node->data > maxVal, update maxVal.
Print both after traversal.

💡 You scan through the chain comparing each box’s number to track the smallest and largest.

// Function to find and print the minimum and maximum values in a linked list
void findMinMax(Node* head) {
    // Step 1: Check if the list is empty
    if (head == NULL)
        return;  // No nodes to process

    // Step 2: Initialize min and max with the first node’s data
    int minVal = head->data;
    int maxVal = head->data;

    // Step 3: Create a temporary pointer to traverse the list
    Node* temp = head;

    // Step 4: Traverse the entire linked list
    while (temp != NULL) {
        // Update min and max values if current node’s data is smaller/larger
        minVal = min(minVal, temp->data);
        maxVal = max(maxVal, temp->data);

        // Move to the next node
        temp = temp->next;
    }

    // Step 5: Print the final results
    cout << "Min = " << minVal << ", Max = " << maxVal << endl;
}

9️⃣ Find Middle Node (Fast & Slow Pointer)

📘 Problem Statement

Find the middle node of a linked list in a single traversal.

🔍 Logic Explanation

Use two pointers:

slow moves 1 step at a time.
fast moves 2 steps at a time.

Steps:

Start both at the head.
Move slow = slow->next and fast = fast->next->next simultaneously.
When fast reaches the end (or becomes NULL), slow will be at the middle.

💡 Because fast moves twice as fast, it’ll reach the end while slow is halfway.

// Function to find and print the middle node of a linked list
void findMiddle(Node* head) {
    // Step 1: Initialize two pointers - slow and fast
    Node* slow = head;  // Moves one step at a time
    Node* fast = head;  // Moves two steps at a time

    // Step 2: Traverse the list
    // When 'fast' reaches the end, 'slow' will be at the middle
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;         // Move slow pointer by one node
        fast = fast->next->next;   // Move fast pointer by two nodes
    }

    // Step 3: Print the middle node's data
    cout << "Middle Node: " << slow->data << endl;
}

🔟 Reverse a Linked List (Iterative)

📘 Problem Statement

Reverse a singly linked list so that the head becomes the tail and all next pointers are reversed.

🔍 Logic Explanation

You need to reverse the direction of every pointer.

Maintain three pointers:
- prev (starts as NULL)
- curr (starts as head)
- next (used to store next node)
For each node:
- Store next = curr->next
- Reverse the link: curr->next = prev
- Move prev to curr
- Move curr to next
When curr becomes NULL, make head = prev.

💡 You are literally flipping all the arrows so the chain runs backward.

// Function to reverse a linked list
void reverseList(Node* &head) {
    // Step 1: Initialize three pointers
    Node* prev = NULL;   // Points to the previous node (initially none)
    Node* curr = head;   // Points to the current node (starts at head)
    Node* next = NULL;   // Temporarily stores the next node

    // Step 2: Traverse the list and reverse the links
    while (curr != NULL) {
        next = curr->next;   // Store the next node
        curr->next = prev;   // Reverse the link
        prev = curr;         // Move prev one step forward
        curr = next;         // Move curr one step forward
    }

    // Step 3: Update the head to point to the new first node
    head = prev;
}

🧩 Complete Linked List Program (with All Functions + Example Outputs)

#include <iostream>
#include <algorithm>  // for min() and max()
using namespace std;

// -------------------- NODE STRUCTURE --------------------
class Node {
public:
    int data;      // To store data of the node
    Node* next;    // Pointer to next node

    // Constructor to initialize node with a value
    Node(int val) {
        data = val;
        next = NULL;
    }
};

// -------------------- PRINT LINKED LIST --------------------
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

// -------------------- COUNT NODES --------------------
int countNodes(Node* head) {
    int count = 0;
    Node* temp = head;
    while (temp != NULL) {
        count++;
        temp = temp->next;
    }
    return count;
}

// -------------------- INSERT AT BEGINNING --------------------
void insertAtBeginning(Node* &head, int value) {
    Node* newNode = new Node(value);
    newNode->next = head;
    head = newNode;
}

// -------------------- INSERT AT END --------------------
void insertAtEnd(Node* &head, int value) {
    Node* newNode = new Node(value);
    if (head == NULL) { head = newNode; return; }

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

// -------------------- INSERT AT POSITION --------------------
void insertAtPosition(Node* &head, int value, int pos) {
    if (pos == 1) {
        insertAtBeginning(head, value);
        return;
    }
    Node* newNode = new Node(value);
    Node* temp = head;
    for (int i = 1; i < pos - 1 && temp != NULL; i++)
        temp = temp->next;
    if (temp == NULL) return;
    newNode->next = temp->next;
    temp->next = newNode;
}

// -------------------- DELETE FIRST NODE --------------------
void deleteFirst(Node* &head) {
    if (head == NULL) return;
    Node* temp = head;
    head = head->next;
    delete temp;
}

// -------------------- DELETE LAST NODE --------------------
void deleteLast(Node* &head) {
    if (head == NULL) return;
    if (head->next == NULL) { delete head; head = NULL; return; }

    Node* temp = head;
    while (temp->next->next != NULL)
        temp = temp->next;
    delete temp->next;
    temp->next = NULL;
}

// -------------------- FIND MIN & MAX --------------------
void findMinMax(Node* head) {
    if (head == NULL) return;
    int minVal = head->data, maxVal = head->data;
    Node* temp = head;
    while (temp != NULL) {
        minVal = min(minVal, temp->data);
        maxVal = max(maxVal, temp->data);
        temp = temp->next;
    }
    cout << "Min = " << minVal << ", Max = " << maxVal << endl;
}

// -------------------- FIND MIDDLE NODE --------------------
void findMiddle(Node* head) {
    if (head == NULL) return;
    Node* slow = head;
    Node* fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    cout << "Middle Node: " << slow->data << endl;
}

// -------------------- REVERSE LINKED LIST --------------------
void reverseList(Node* &head) {
    Node* prev = NULL;
    Node* curr = head;
    Node* next = NULL;
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
}

// -------------------- MAIN FUNCTION --------------------
int main() {
    Node* head = NULL;

    cout << "Creating Linked List: 10 -> 20 -> 30 -> 40 -> 50\n";
    insertAtEnd(head, 10);
    insertAtEnd(head, 20);
    insertAtEnd(head, 30);
    insertAtEnd(head, 40);
    insertAtEnd(head, 50);

    cout << "Initial List: ";
    printList(head);

    cout << "\n[1] Insert at Beginning (5): ";
    insertAtBeginning(head, 5);
    printList(head);

    cout << "\n[2] Insert at End (60): ";
    insertAtEnd(head, 60);
    printList(head);

    cout << "\n[3] Insert at Position (25 at pos 4): ";
    insertAtPosition(head, 25, 4);
    printList(head);

    cout << "\n[4] Delete First Node: ";
    deleteFirst(head);
    printList(head);

    cout << "\n[5] Delete Last Node: ";
    deleteLast(head);
    printList(head);

    cout << "\n[6] Count of Nodes: " << countNodes(head) << endl;

    cout << "\n[7] Find Min & Max: ";
    findMinMax(head);

    cout << "\n[8] Find Middle: ";
    findMiddle(head);

    cout << "\n[9] Reverse Linked List: ";
    reverseList(head);
    printList(head);

    return 0;
}

🧠 Key Takeaways

🔹 1. Linked Lists = Connections

Unlike arrays, nodes in a linked list are stored separately and connected using pointers. Mastering them means understanding how links form, change, and break.

🔹 2. The Head Is Everything

The head is your entry point. Lose it, and you lose the entire list so always handle it carefully when inserting or deleting.

🔹 3. Focus on Pointers, Step by Step

Every operation (insert, delete, reverse) is just about rearranging pointers. Move one step at a time and visualize each link to avoid confusion.

🔹 4. Visualization Beats Memorization

Draw the list on paper, trace changes, and understand the logic. Don’t memorize understand how data flows between nodes.

🔹 5. Handle Edge Cases

Always check:

Is the list empty?
Are we dealing with the first or last node?
Are all pointers (next, prev) updated correctly?

🔹 6. Two-Pointer Technique Is Gold

Many problems finding the middle, reversing, detecting loops become easy once you understand slow and fast pointers.

🔹 7. Clean Up Memory

Every new should have a matching delete. Avoid dangling pointers and leaks.

💡 Things to Keep in Mind

⚙️ 1. Initialize Pointers

Always start new pointers (next, prev) as NULL. It prevents runtime crashes.

🧩 2. Don’t Lose Track

Before deleting or reversing, store the next node temporarily:

🔄 3. Traverse Safely

Stop traversal when temp == NULL. Going beyond it leads to invalid access.

🧹 4. Debug Smartly

If output looks wrong:

Print nodes step-by-step
Check pointer updates
Ensure no node still points to a deleted one

🎯 5. Understand Before You Solve

Once you can visualize insertion, deletion, and reversal you’re ready for real interview-style problems.

🧩 Singly Linked List Practice Questions

🔹 Part 1: Basics

Create a singly linked list with n nodes, take input for each node, and print the list.
Count the number of nodes in a linked list.
Find the sum of all node values in a linked list.
Display the linked list in reverse order (without actually reversing it).

🔹 Part 2: Insertion

Insert a node at the beginning of a linked list.
Insert a node at the end of a linked list.
Insert a node at a specific position in the linked list.
Insert a node after a given value in the linked list.

🔹 Part 3: Deletion

Delete the first node of a linked list.
Delete the last node of a linked list.
Delete a node at a specific position.
Delete a node by its value.

🔹 Part 4: Searching & Traversal

Search for a given value in the linked list and return its position.
Find the maximum and minimum value in the linked list.
Find the middle element of a linked list using the fast and slow pointer approach.
Count how many times a given value occurs in the linked list.

🔹 Part 5: Reversal & Modifications

Reverse a linked list iteratively.
Reverse a linked list recursively.
Remove duplicate elements from a sorted linked list.
Remove duplicate elements from an unsorted linked list.

🔹 Part 6: Special Operations

Merge two sorted linked lists into one sorted list.
Find the Nth node from the end of a linked list.
Check whether a linked list is palindromic (reads the same forward and backward).
Detect a cycle/loop in a linked list using Floyd’s Cycle Detection Algorithm.
Remove a cycle from a linked list if it exists.

🔹 Part 7: Advanced Practice

Split a linked list into two halves.
Find the intersection point of two linked lists.
Sort a linked list using merge sort.
Add two numbers represented by linked lists.
Clone a linked list with random pointers (advanced concept).

✨ Wrapping Up

Congratulations you’ve just built the foundation of one of the most important data structures in computer science: the Singly Linked List.

At first, pointers may feel tricky, but with practice, you’ll start seeing how every operation is just a dance of links connecting, moving, and breaking nodes in the right order.

From here, the journey gets more exciting.

Next, we’ll explore Doubly Linked Lists, where nodes can move both ways unlocking faster traversals, cleaner deletions, and even more flexibility.

So grab a notebook, trace those pointers, and get ready to level up your understanding of linked lists.

See you in the next part 👋 where we double the links and double the learning!