Category: linked lists

  • 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

  • Master Circular Linked List Tutorials with Examples 2026

    Complete guide to mastering Circular Linked Lists in 2025 with this beginner-to-advanced tutorial! Learn how circular linked lists work, their types, operations, and real-life applications through clear explanations, code examples in C, C++, Java, Python, and JavaScript, and step-by-step implementations. This post also covers time and space complexity, interview FAQs, help you crack coding interviews and academic exams. Perfect for students, developers, and data structure enthusiasts!

    What is a Circular Linked List?

    A Circular Linked List is a variation of the linked list in which the last node points back to the first node instead of pointing to NULL. This creates a looped structure where you can traverse endlessly through the list starting from any node.

    🔁 In a circular linked list, you can go from tail to head seamlessly — it’s like a roundabout with no end!

    Why Learn Circular Linked Lists?

    Learning about Circular Linked Lists is crucial for understanding how dynamic data structures work in memory. They are especially useful for:

    • Circular buffers (ring buffers)
    • Multiplayer game round-robin scheduling
    • Task scheduling algorithms
    • Data streaming

    Types of Circular Linked List

    1. Singly Circular Linked List
      Each node has a data and a next pointer, and the next of the last node points to the first node.
    2. Doubly Circular Linked List
      Each node has data, next, and prev pointers. The next of the last node connects to the first node and the prev of the first node connects to the last.

    Circular Linked List Operations

    1. Insertion

    • At the beginning
    • At the end
    • After a specific node

    2. Deletion

    • From the beginning
    • From the end
    • A specific node

    3. Traversal

    • Start from any node and keep moving until you’re back to the same node.
    // Example: Circular Linked List Traversal in C
    void traverse(struct Node* head) {
        struct Node* temp = head;
        if (head != NULL) {
            do {
                printf("%d ", temp->data);
                temp = temp->next;
            } while (temp != head);
        }
    }
    

    C Implementation CLL

    #include <stdio.h>
    #include <stdlib.h>
    
    struct Node {
        int data;
        struct Node* next;
    };
    
    void traverse(struct Node* head) {
        if (head == NULL) return;
        struct Node* temp = head;
        do {
            printf("%d ", temp->data);
            temp = temp->next;
        } while (temp != head);
    }
    
    struct Node* insertEnd(struct Node* head, int data) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = data;
        if (!head) {
            newNode->next = newNode;
            return newNode;
        }
        struct Node* temp = head;
        while (temp->next != head) temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
        return head;
    }
    

    ✅ C++ Implementation CLL

    #include <iostream>
    using namespace std;
    
    class Node {
    public:
        int data;
        Node* next;
        Node(int val) {
            data = val;
            next = nullptr;
        }
    };
    
    void traverse(Node* head) {
        if (!head) return;
        Node* temp = head;
        do {
            cout << temp->data << " ";
            temp = temp->next;
        } while (temp != head);
    }
    
    Node* insertEnd(Node* head, int val) {
        Node* newNode = new Node(val);
        if (!head) {
            newNode->next = newNode;
            return newNode;
        }
        Node* temp = head;
        while (temp->next != head) temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
        return head;
    }
    

    ✅ Java Implementation CLL

    class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    
    public class CircularLinkedList {
        Node head;
    
        void traverse() {
            if (head == null) return;
            Node temp = head;
            do {
                System.out.print(temp.data + " ");
                temp = temp.next;
            } while (temp != head);
        }
    
        void insertEnd(int data) {
            Node newNode = new Node(data);
            if (head == null) {
                newNode.next = newNode;
                head = newNode;
                return;
            }
            Node temp = head;
            while (temp.next != head) temp = temp.next;
            temp.next = newNode;
            newNode.next = head;
        }
    }
    

    ✅ Python Implementation CLL

    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
    
    class CircularLinkedList:
        def __init__(self):
            self.head = None
    
        def traverse(self):
            if not self.head:
                return
            temp = self.head
            while True:
                print(temp.data, end=' ')
                temp = temp.next
                if temp == self.head:
                    break
    
        def insert_end(self, data):
            new_node = Node(data)
            if not self.head:
                new_node.next = new_node
                self.head = new_node
                return
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_node
            new_node.next = self.head
    

    ✅ JavaScript Implementation CLL

    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    }
    
    class CircularLinkedList {
        constructor() {
            this.head = null;
        }
    
        traverse() {
            if (!this.head) return;
            let temp = this.head;
            do {
                console.log(temp.data);
                temp = temp.next;
            } while (temp !== this.head);
        }
    
        insertEnd(data) {
            const newNode = new Node(data);
            if (!this.head) {
                newNode.next = newNode;
                this.head = newNode;
                return;
            }
            let temp = this.head;
            while (temp.next !== this.head) {
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.next = this.head;
        }
    }
    

    Time & Space Complexity of Circular Linked List

    OperationTime ComplexitySpace Complexity
    Insert at EndO(n)O(1)
    TraverseO(n)O(1)
    Delete NodeO(n)O(1)
    SearchO(n)O(1)

    ⚠️ Note: You can make insertion O(1) by maintaining a tail pointer.

    Advantages of Circular Linked List

    • No NULL value at the end
    • Ideal for implementing circular queues
    • Efficient for round-robin scheduling
    • Can traverse from any node

    Disadvantages of Circular Linked List

    • Slightly more complex insertion/deletion logic
    • Risk of infinite loops if not handled properly

    Circular Linked List vs Singly Linked List

    FeatureSingly Linked ListCircular Linked List
    End PointerPoints to NULLPoints to head node
    TraversalEnds at NULLLoops back to start
    Use CaseLinear dataCircular scheduling

    Real-world Use Cases of Circular Linked List

    • Music playlist apps (loop through songs)
    • Task scheduling in OS
    • Live data streams
    • Circular queues

    1.What is the use of circular linked list?

    It is mainly used in applications that require a continuous traversal like CPU scheduling, music players, or multiplayer games.

    2.What is the time complexity of circular linked list operations?

    Insertion: O(1) (beginning), O(n) (end/after a node)
    Deletion: O(1) (beginning), O(n) (specific node)
    Traversal: O(n)

    3.Can we implement a stack or queue using a circular linked list?

    Yes! Circular linked lists are great for queues, especially when a circular buffer is needed.

    4.How to detect a circular linked list?

    Use Floyd’s Cycle Detection Algorithm (Tortoise and Hare method).

    5.What is a Circular Linked List in Data Structures?

    A Circular Linked List is a type of linked list where the last node is connected back to the first node, forming a closed loop. Unlike a singly linked list where the last node points to NULL, a circular linked list enables continuous traversal from any point in the list. This structure is highly useful in circular queues, CPU scheduling, and real-time applications.

    6.What are the types of Circular Linked Lists?

    There are two main types of Circular Linked Lists:
    Singly Circular Linked List: Each node has one pointer pointing to the next node, and the last node points to the head.
    Doubly Circular Linked List: Each node has two pointers (prev and next), and both the first and last nodes are connected circularly in both directions.
    Both types are used based on the complexity of operations needed and memory constraints.

    7.What are the real-life applications of Circular Linked List?

    Circular Linked Lists are widely used in:
    Round-robin CPU scheduling
    Music or video playlists that auto-repeat
    Circular buffers in embedded systems
    Real-time data stream processing
    Traffic light simulation systems
    Multiplayer games for turn rotation
    These applications benefit from the list’s looping behavior, which avoids end-condition checks.

    8.What is the time complexity of Circular Linked List operations?

    Insertion at end/head: O(n) / O(1) (if tail maintained)
    Deletion at head: O(n)
    Search: O(n)
    Traversal: O(n)
    Maintaining a tail pointer can reduce insertion time at the end to O(1).

    9.How do you detect a circular linked list in a program?

    To detect a circular linked list, you can use Floyd’s Cycle Detection Algorithm (Tortoise and Hare Algorithm):
    Use two pointers moving at different speeds.
    If they ever meet, a cycle exists.
    If the fast pointer reaches NULL, it’s not circular.
    This is the most efficient method with O(n) time and O(1) space.

    10.Can a Circular Linked List be used to implement a queue?

    Yes, Circular Linked Lists are perfect for circular queues, especially when:
    Memory usage is fixed (as in embedded systems).
    You need constant-time insertion and deletion.
    It avoids shifting elements (like in arrays) and supports continuous enqueuing and dequeuing.

    A Circular Linked List offers flexibility, especially when your use case involves continuous looping or round-based tasks. While it can be a bit more complex than a regular linked list, it brings efficiency and circular logic into dynamic data structures.

    If you’re preparing for coding interviews, learning circular linked lists will give you an edge!

    Circular Linked List
    Master Circular Linked List Tutorials with Examples 2025