Java Program to Remove Duplicates from a Linked List

Introduction

Removing duplicates from a linked list is a common task that involves ensuring each element in the list appears only once. This operation is crucial for maintaining data integrity and optimizing storage. This guide will walk you through writing a Java program that removes duplicates from a singly linked list.

Problem Statement

Create a Java program that:

Implements a singly linked list.
Removes any duplicate elements from the linked list.
Displays the linked list before and after removing duplicates.

Example:

Input: 1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 5
Output: 1 -> 2 -> 3 -> 4 -> 5
Input: 1 -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
Output: 1 -> 2 -> 3 -> 4 -> 5

Solution Steps

Create the Linked List and Node Structure: Define a Node class to represent each element in the linked list and a LinkedList class to manage the list.
Add Nodes to the Linked List: Implement methods to add nodes to the linked list.
Remove Duplicates from the Linked List:

Use a HashSet to track elements that have already been seen.
Traverse the linked list and remove any node that contains a duplicate value.

Display the Result: Output the linked list before and after removing duplicates.

Java Program

// Java Program to Remove Duplicates from a Linked List
// Author: https://www.rameshfadatare.com/

import java.util.HashSet;

class Node {
    int data;
    Node next;

    // Constructor to initialize the node
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    // Method to add a new node at the end of the list
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            // Step 1: Initialize the head if the list is empty
            head = newNode;
        } else {
            // Step 2: Traverse to the end of the list and add the new node
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // Method to remove duplicates from the linked list
    public void removeDuplicates() {
        // Step 3: Use a HashSet to track seen elements
        HashSet<Integer> seen = new HashSet<>();
        Node current = head;
        Node prev = null;

        // Step 4: Traverse the list
        while (current != null) {
            if (seen.contains(current.data)) {
                // Step 5: If the element is a duplicate, remove the node
                prev.next = current.next;
            } else {
                // Step 6: If the element is not a duplicate, add it to the set
                seen.add(current.data);
                prev = current;
            }
            current = current.next;
        }
    }

    // Method to display the linked list
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

public class RemoveDuplicatesFromLinkedList {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Adding elements to the linked list
        list.add(1);
        list.add(2);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(4);
        list.add(5);

        System.out.println("Original Linked List:");
        list.display();

        // Removing duplicates from the linked list
        list.removeDuplicates();

        System.out.println("Linked List after removing duplicates:");
        list.display();
    }
}

Explanation

Step 1: Initialize the Node Class

The Node class represents a single node in the linked list. Each node contains data and a reference to the next node in the list.
The constructor initializes the node with data and sets the next pointer to null.

Step 2: Initialize the LinkedList Class

The LinkedList class manages the linked list. The class contains the head node that points to the first node in the list.
The add() method appends a new node to the end of the list. If the list is empty, the head node is set to the new node.

Step 3: Use a HashSet to Track Seen Elements

The removeDuplicates() method uses a HashSet to track elements that have already been seen in the linked list.
The HashSet allows for efficient lookups to check if an element is a duplicate.

Step 4: Traverse the Linked List

The linked list is traversed using a while loop. Two pointers, current and prev, are used to keep track of the current node and the previous node, respectively.

Step 5: Remove Duplicate Nodes

If the current node’s data is found in the HashSet, it means the node is a duplicate. The node is removed by adjusting the next pointer of the previous node to skip the current node.

Step 6: Add Non-Duplicate Elements to the HashSet

If the current node’s data is not found in the HashSet, it means the node is unique. The data is added to the HashSet, and the previous pointer is updated to the current node.

Output Example

Original Linked List:
1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 5 -> null
Linked List after removing duplicates:
1 -> 2 -> 3 -> 4 -> 5 -> null

Example with Different Input

If you modify the input list to:

list.add(1);
list.add(1);
list.add(2);
list.add(3);
list.add(3);
list.add(4);
list.add(4);
list.add(5);

The output will be:

Original Linked List:
1 -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 -> null
Linked List after removing duplicates:
1 -> 2 -> 3 -> 4 -> 5 -> null

Conclusion

This Java program demonstrates how to remove duplicates from a singly linked list using a HashSet to track seen elements. The program efficiently removes duplicate nodes, ensuring each element appears only once in the list. This exercise is valuable for understanding how to manage and manipulate data within linked lists in Java programming.