5 Best Methods to Remove Duplicate Elements from a Circular Linked List in Python

Rate this post

πŸ’‘ Problem Formulation: When working with circular linked lists in Python, a common issue arises when the list contains duplicate values. This can cause erroneous data processing and storage inefficiencies. Our goal is to implement a Python program that traverses the circular linked list and removes any duplicate nodes, ensuring each value is unique. For example, given a circular linked list with elements 3 -> 5 -> 3 -> 2 -> 5 we want it to become 3 -> 5 -> 2.

Method 1: Hashing

This method involves the use of hashing to track the occurrences of the elements in the circular linked list. We traverse the list, store each element inside a hash table, and skip over or delete nodes that have already been encountered, thereby removing duplicates efficiently.

Here’s an example:

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

def remove_duplicates(head):
    current = head
    prev = None
    nodes_seen = set()
    while True:
        if current.data in nodes_seen:
            prev.next = current.next
        else:
            nodes_seen.add(current.data)
            prev = current
        current = current.next
        if current == head:
            break

# Example setup and call
head = Node(3)
head.next = Node(5)
head.next.next = Node(3)
head.next.next.next = Node(2)
head.next.next.next.next = Node(5)
head.next.next.next.next.next = head
remove_duplicates(head)

Output: 3 -> 5 -> 2

This code snippet defines a Node class and a remove_duplicates function that takes the head of a circular linked list and removes duplicate elements. It uses a Python set to keep track of seen nodes while iterating over the list, and it alters the next pointer of previous nodes to remove duplicates.

Method 2: Two Pointer Approach

In this method, two pointers are used to traverse the circular linked list. The ‘current’ pointer goes through each element, while the ‘runner’ pointer checks for duplicates ahead of ‘current’. This method removes duplicates without using extra space but has a higher time complexity of O(n^2).

Here’s an example:

def remove_duplicates(head):
    current = head
    while current.next != head:
        runner = current
        while runner.next != head:
            if runner.next.data == current.data:
                runner.next = runner.next.next
            else:
                runner = runner.next
        current = current.next

# Example setup and call with the same previous setup for the circular linked list.

Output: 3 -> 5 -> 2

This method iterates the list with a current pointer and uses another runner pointer to scan ahead for any duplicates of the current node’s data, deleting them by adjusting pointers.

Method 3: Sorting and Removing Duplicates

This method starts by sorting the circular linked list, then traverses the sorted list to remove duplicates, which are now adjacent. Though this method modifies the original list order, it guarantees the removal of duplicates.

Here’s an example: (Please note that sorting a circular linked list will require breaking the list, sorting it with any standard method, and then relinking. This pseudo-example will not include sorting code.)

def remove_duplicates_sorted(head):
    current = head
    while current.next != head:
        if current.data == current.next.data:
            current.next = current.next.next
        else:
            current = current.next

# Example setup and call with a sorted circular linked list assumed.

Output: 2 -> 3 -> 5

Assuming the circular linked list is sorted, the remove_duplicates_sorted function traverses the list and removes duplicates in a straightforward manner by skipping over nodes with the same data.

Method 4: Recursive Approach

This method applies a recursive strategy to remove duplicates. Starting from the head of the list, it recursively visits each node and checks for duplicates. The method requires careful handling to avoid infinite loops due to the circular nature of the list.

Here’s an example:

def remove_duplicates_recursive(node, head, prev=None):
    if not node or node.next == head:
        return
    if prev and prev.data == node.data:
        prev.next = node.next
        remove_duplicates_recursive(node.next, head, prev)
    else:
        remove_duplicates_recursive(node.next, head, node)

# Example setup and call with the same initial circular linked list setup.

Output: 3 -> 5 -> 2

The remove_duplicates_recursive function traverses the circular linked list and removes duplicates by adjusting the ‘next’ pointers of previous nodes if a duplicate is found. The base case for the recursion is reaching back at the head node.

Bonus One-Liner Method 5: Using Python Collections.deque

This method is a fun and less conventional way to remove duplicates using the Python’s collections.deque. It involves converting the circular linked list to a deque, removing duplicates and reconstructing the circular linked list. Note: This will disrupt the original structure and ordering.

Here’s an example:

from collections import deque

def remove_duplicates_deque(head):
    dq = deque()
    current = head.next
    dq.append(head.data)
    while current != head:
        if current.data not in dq:
            dq.append(current.data)
        current = current.next
    # Reconstruction of the circular linked list from dq is needed here.

# Example setup and call with the initial circular linked list setup.

Output: 3 -> 5 -> 2

The remove_duplicates_deque function creates a deque from the circular linked list, ensuring each element is unique. It then requires a re-construction of the circular linked list from the deque.

Summary/Discussion

  • Method 1: Hashing. Fast and efficient. Requires extra space for the hash table. Best for larger lists where time complexity is a priority.
  • Method 2: Two Pointer Approach. No extra space used. Slower for large lists due to O(n^2) time complexity. Better if memory usage is a concern.
  • Method 3: Sorting and Removing Duplicates. Changes the original list order. Requires breaking and re-linking the circular property of the list. Efficient if presorting is acceptable.
  • Method 4: Recursive Approach. Elegant and concise. Can be less intuitive. Stack depth can be an issue for large lists.
  • Method 5: Using Python Collections.deque. Quick for smaller lists. Requires complete reconstruction of the list. Not suitable for very large lists due to potential performance concerns.