Python Program to Remove Duplicates from a Linked List

Overview

This Python program removes duplicate elements from a singly linked list. The input linked list may or may not be sorted, and all duplicates are removed in place while maintaining the original order of unique elements.

Program Explanation

The structure of the program includes a Node class to represent a node in the linked list and a function to remove duplicate elements from the linked list.

Steps Involved:

1. Create a class Node to represent the elements of the linked list. Each node has two attributes: data (the value of the node) and next (pointer to the next node).
2. Create a function remove_duplicates that takes the head of a linked list and removes duplicate elements.
3. Use a set to keep track of the elements seen so far in the linked list.
4. Traverse the list and for each node, check if its value already exists in the set.
5. If a node is a duplicate, adjust the next pointer to skip the duplicate node.
6. If a node is unique, add its value to the set and continue traversing the list.

Python Code


class Node:
"""
Node class to represent a linked list node.
Each node contains the data and a pointer to the next node.
"""
def __init__(self, data):
self.data = data
self.next = None

def remove_duplicates(head):
“””
Remove duplicate elements from a linked list.

:param head: Head node of the linked list
:return: Head node of the linked list with duplicates removed
“””
if head is None:
return None

# Set to store unique elements
seen = set()
current = head
seen.add(current.data) # Add the first element to the set

# Traverse the linked list
while current.next is not None:
if current.next.data in seen:
# Duplicate found, skip the next node
current.next = current.next.next
else:
# Unique element, add to the set
seen.add(current.next.data)
current = current.next

return head

# Helper function to print a linked list
def print_linked_list(head):
“””
Print the elements of a linked list starting from the head node.

:param head: Head node of the linked list
“””
current = head
while current is not None:
print(current.data, end=” -> “)
current = current.next
print(“None”)

# Example usage:
# Create a linked list with duplicates
head = Node(1)
head.next = Node(2)
head.next.next = Node(2)
head.next.next.next = Node(3)
head.next.next.next.next = Node(4)
head.next.next.next.next.next = Node(4)
head.next.next.next.next.next.next = Node(5)

print(“Original Linked List:”)
print_linked_list(head)

# Remove duplicates
remove_duplicates(head)

print(“Linked List after Removing Duplicates:”)
print_linked_list(head)

Program Explanation

This Python program defines the following:

• Node class: Each node in the linked list contains a value (data) and a reference to the next node (next).
• remove_duplicates function: Removes duplicate elements from the linked list by using a set to track unique values. As the list is traversed, any node with a duplicate value is skipped, effectively removing it from the list.
• print_linked_list function: A utility function to display the linked list for clarity, before and after removing duplicates.

Example Output

Given the linked list:

• 1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 5 -> None

After removing duplicates, the linked list will be:

1 -> 2 -> 3 -> 4 -> 5 -> None