Tag: linked list example

  • Master How to Count Duplicates in a Linked List (2026)

    Learn how to count duplicates in a linked list in C++ with this beginner-friendly guide. Step-by-step explanation, easy-to-understand code, and tips for detecting duplicate nodes efficiently.

    Linked lists are one of the fundamental data structures in programming. While they are simple to understand, performing operations like counting duplicates can be tricky for beginners. In this guide, we will explain how to count duplicates in a linked list in an easy-to-understand, step-by-step way.

    What is a Linked List?

    A linked list is a collection of nodes where each node contains two things:

    1. Data – The value stored in the node.
    2. Pointer (Next) – A reference to the next node in the list.

    For example, a linked list can look like this:

    1 → 2 → 2 → 3 → 3 → 3 → 4
    

    What Are Duplicates in a Linked List?

    Duplicates are values that appear more than once in the linked list.

    In the example above:

    • 2 appears twice → 1 duplicate
    • 3 appears three times → 2 duplicates

    Total duplicates = 3

    Step-By-Step Approach to Count Duplicates

    Here’s a simple way to count duplicates, perfect for beginners:

    1. Start with the first node (curr).
    2. Compare it with all nodes that come after it (temp).
    3. If a node has the same value as curr, it’s a duplicate.
    4. Move to the next node and repeat until the end.

    Understanding the Key Line: Node* temp = curr->next;

    One line often confuses beginners:

    Node* temp = curr->next;

    Here’s what it means:

    • Node* temp → temp is a pointer that can point to a node.
    • curr->next → the next node after the current node.
    • Together → temp starts checking from the node after curr, not from the beginning. This avoids counting the same value multiple times.

    Count Duplicates in a Linked List : C++ Code

    #include <iostream>
    using namespace std;
    
    class Node {
    public:
        int data;
        Node* next;
    
        Node(int data) {
            this->data = data;
            this->next = NULL;
        }
    };
    
    // Function to count duplicates
    int countDuplicates(Node* head) {
        int count = 0;
        Node* curr = head;
    
        while (curr != NULL) {
            Node* temp = curr->next; // Start checking from next node
    
            while (temp != NULL) {
                if (curr->data == temp->data) {
                    count++;
                    break; // Count only once per value
                }
                temp = temp->next;
            }
            curr = curr->next;
        }
    
        return count;
    }
    
    // Main function
    int main() {
        Node* head = new Node(1);
        head->next = new Node(2);
        head->next->next = new Node(2);
        head->next->next->next = new Node(3);
        head->next->next->next->next = new Node(3);
        head->next->next->next->next->next = new Node(3);
        head->next->next->next->next->next->next = new Node(4);
    
        cout << "Total duplicate nodes: " << countDuplicates(head) << endl;
        return 0;
    }
    

    How This Works

    1. curr pointer moves node by node.
    2. temp pointer checks all nodes after curr.
    3. If curr->data == temp->data, we found a duplicate.
    4. Count is updated once per duplicate value.

    Time and Space Complexity

    • Time Complexity: O(n²) – two nested loops
    • Space Complexity: O(1) – no extra memory used

    Note: For beginners, this approach is easy to understand. Advanced methods (like using a hash map) can reduce time complexity.

    Time Complexity

    Answer:

    Time Complexity = O(n²)

    Why O(n²)? (How we calculate it)

    Look at this part of the code:

    while (curr != NULL) {          // Outer loop
        Node* temp = curr->next;
    
        while (temp != NULL) {      // Inner loop
            if (curr->data == temp->data) {
                count++;
                break;
            }
            temp = temp->next;
        }
        curr = curr->next;
    }
    

    Step-by-step thinking

    • Let total number of nodes = n

    Outer loop (curr)

    • Runs for every node
    • So it runs n times

    Inner loop (temp)

    • For each curr, it checks the remaining nodes
    • In worst case:
      • First time → checks ~ (n-1) nodes
      • Second time → checks ~ (n-2) nodes
      • …
      • Last time → checks 1 node

    Total comparisons (worst case)

    (n-1) + (n-2) + (n-3) + ... + 1
    

    This adds up to:

    n² (approximately)
    

    That’s why Time Complexity = O(n²)

    Simple line to remember (for exams/interviews)

    Since there are two nested loops, the time complexity is O(n²).

    Space Complexity

    Answer:

    Space Complexity = O(1)

    Why O(1)? (How we calculate it)

    Let’s see what extra memory we use:

    int count;
    Node* curr;
    Node* temp;
    
    • These are just variables and pointers
    • They do not grow with input size
    • No arrays, maps, or extra lists are used

    What we are NOT using

    • No extra linked list
    • No hash map
    • No array

    So memory usage stays constant, no matter how big the linked list is.

    Therefore, Space Complexity = O(1)

    Final Summary (Perfect for Notes)

    TypeComplexity
    Time ComplexityO(n²)
    Space ComplexityO(1)

    Tips for Beginners

    • Use two loops to make your logic clear.
    • Always check from the next node, not from the head again.
    • Use visual examples to understand how curr and temp work.

    Frequently Asked Questions (FAQ)

    1. What is a duplicate in a linked list?

    A duplicate is a node whose value appears more than once in a linked list. For example, in the list 1 → 2 → 2 → 3, the value 2 is a duplicate because it appears twice.

    2. Why do we use Node* temp = curr->next?

    This line ensures that we start checking for duplicates from the node after the current one (curr). It avoids re-checking nodes and makes counting accurate.

    3. Can we count duplicates in a sorted linked list faster?

    Yes! In a sorted linked list, duplicates are always next to each other. So, we can use a single loop to compare each node with the next, which reduces time complexity from O(n²) to O(n).

    4. What is the time complexity of this method?

    The beginner-friendly method using two nested loops has O(n²) time complexity, where n is the number of nodes in the list.

    5. Can we count duplicates without using extra space?

    Yes, the method shown in this guide uses O(1) extra space, meaning no additional memory is required apart from the linked list itself.

    6. How is this different from using a hash map?

    Using a hash map can reduce the time complexity to O(n), but it uses extra memory to store counts. The method in this guide is memory-efficient and easier for beginners to understand.

    7. Can this method handle strings or other data types?

    Yes, as long as the linked list stores comparable data (like integers, characters, or strings), you can modify the comparison curr->data == temp->data accordingly.

    Read More : Master Most Asked Stack Coding Questions in Interviews

  • Linked List Explained: Master Complete Guide for Beginners 2026

    Introduction to Linked List

    If you’re learning Linked List data structures, you’ve probably come across the term Linked List. But what exactly is it? How does it work, and why do we even need it when we already have arrays?

    In this blog post, we’ll dive deep into linked list in data structure, understand how it differs from other data structures, explore the types of linked list, and learn about their practical advantages and use cases.

    What is a Linked List?

    A Linked List is a linear data structure where elements are stored in nodes, and each node points to the next one in the sequence. Unlike arrays, which store elements in contiguous memory locations, linked lists store data non-contiguously and use pointers to connect elements.

    Each node in a linked list contains:

    • Data (the value stored in the node)
    • Pointer (or reference) to the next node

    This unique structure makes linked lists highly flexible and efficient in certain scenarios.

    Why Use Linked List Instead of Arrays?

    Before diving into the types of linked list, let’s quickly understand why we’d choose a linked list over an array:

    ✅ Dynamic Size: Unlike arrays, linked lists don’t require specifying size in advance. Nodes can be added or removed without reallocating memory.

    ✅ Efficient Insertions/Deletions: Adding or removing elements doesn’t involve shifting elements, as in arrays.

    ✅ Memory Utilization: Useful when memory is fragmented or when the size of the dataset changes frequently.

    However, linked lists also have some disadvantages, like higher memory usage due to storing pointers and slower random access.

    Types of Linked List

    There are several types of linked list, each serving different use cases:

    1. Singly Linked List

    • Each node has a reference to the next node only.
    • Traversal is possible only in one direction.
    • Simple and widely used in basic implementations.

    Example:

    [10] → [20] → [30] → NULL
    

    2. Doubly Linked List

    • Each node has references to both next and previous nodes.
    • Allows traversal in both directions (forward and backward).
    • Slightly higher memory usage due to the extra pointer.

    Example:

    NULL ← [10] ↔ [20] ↔ [30] → NULL
    

    3. Circular Linked List

    • Last node points back to the first node, creating a circle.
    • Can be singly or doubly linked.
    • Useful in applications like round-robin scheduling.

    Example:

    [10] → [20] → [30] → [10] …
    

    Common Linked List Operations

    Understanding basic linked list operations is crucial. Let’s look at the most common:

    Insertion

    • Insert a new node at the beginning, middle, or end of the list.

    Deletion

    • Remove a node based on value or position.

    Traversal

    • Visit each node and perform an action (like printing values).

    Searching

    • Find whether a particular value exists in the linked list.

    Advantages of Linked List

    Let’s recap some advantages of linked list:

    • Dynamic memory allocation
    • No wasted memory (no predefined size)
    • Easier insertion/deletion
    • Useful for implementing stacks, queues, graphs, and more

    Applications of Linked List

    Here are some practical uses of linked list in data structure:

    • Implementing stacks and queues
    • Dynamic memory management
    • Browser history (back and forward functionality)
    • Undo/redo features in software
    • Hash table chaining

    Linked List vs Array: Quick Comparison

    FeatureArrayLinked List
    SizeFixedDynamic
    Memory AllocationContiguousNon-contiguous
    Insertion/DeletionCostly (shifting)Efficient
    Random AccessO(1)O(n)

    Conclusion

    A Linked List is a powerful and flexible data structure essential for any programmer’s toolkit. While it might seem complex initially, it offers significant advantages, especially when dealing with dynamic data and frequent insertions or deletions.

    Whether you’re preparing for coding interviews or simply expanding your programming knowledge, mastering linked list in data structure will give you a strong foundation for solving complex problems efficiently.

    Frequently Asked Questions (FAQ)

    Q1. What is a linked list in simple words?
    A linked list is a sequence of nodes where each node points to the next, making it easy to add or remove elements without shifting other data.

    Q2. Is linked list better than array?
    It depends. Linked lists are better for frequent insertions/deletions, but arrays are better for fast random access.

    Q3. What are the types of linked list?
    The main types include singly linked list, doubly linked list, and circular linked list.

    Q4. Where is linked list used in real life?
    Linked lists are used in browser history, memory management, music playlists, and many other applications.