Remove Duplicates from a Singly Linked List

Removing Duplicates from a Singly Linked List

Removing duplicates from a singly linked list involves traversing the list and eliminating nodes with duplicate values. This operation ensures that each value appears only once in the list.

---

Step-by-Step Process

Consider a singly linked list with the following structure before removing duplicates:

Head -> 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> None

To remove duplicates from this list, follow these steps:

1. Initialize a Set: Create an empty set to keep track of seen values.
2. Initialize a Pointer: Start with a pointer set to the head of the list.
3. Traverse the List: For each node, check if its value is already in the set.
4. Remove Duplicates: If the value is in the set, remove the node by updating the next pointer of the previous node. Otherwise, add the value to the set and move to the next node.

After performing these steps, the linked list will have no duplicate values.

Head -> 1 -> 2 -> 3 -> 4 -> None

---

Python Program to Remove Duplicates from a Singly Linked List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def remove_duplicates(self):
        if self.head is None:
            return
        seen = set()
        current = self.head
        prev = None
        while current:
            if current.data in seen:
                prev.next = current.next
            else:
                seen.add(current.data)
                prev = current
            current = current.next

    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Example usage:
linked_list = SinglyLinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(2)
linked_list.append(3)
linked_list.append(3)
linked_list.append(4)
print("Linked list before removing duplicates:")
linked_list.traverse()  # Output: 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> None
linked_list.remove_duplicates()
print("Linked list after removing duplicates:")
linked_list.traverse()  # Output: 1 -> 2 -> 3 -> 4 -> None

This Python program defines a singly linked list with methods for appending nodes, removing duplicates, and traversing the list. The remove_duplicates method uses a set to keep track of seen values and removes nodes with duplicate values.