Remove Duplicate Nodes from a Linked List using Python

Introduction

A linked list is a data structure consisting of a sequence of elements called nodes, where each node points to the next node in the sequence. Sometimes, linked lists may contain duplicate nodes, which can be problematic in certain scenarios, especially when dealing with large datasets or when performing operations that require unique elements.

In this article, we will explore how to remove duplicate nodes from a linked list using Python, regardless of whether the list is sorted or unsorted. We’ll go through step-by-step implementation and provide code examples to demonstrate the process.

1. Linked List Node Definition

First, let’s define a basic linked list node in Python. Each node should have two attributes: the data it holds and a reference to the next node in the list.

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

2. Create the Linked List

Before we can remove duplicates, we need a linked list to work with. Let’s create a sample linked list to demonstrate the process.

def create_linked_list(data_list):
    head = None
    tail = None
    for data in data_list:
        new_node = Node(data)
        if not head:
            head = new_node
            tail = head
        else:
            tail.next = new_node
            tail = tail.next
    return head

Now, let’s create an example linked list and print its contents:

data_list = [1, 2, 3, 2, 4, 5, 1, 6, 3, 7]
linked_list = create_linked_list(data_list)

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

print("Original Linked List:")
print_linked_list(linked_list)

The program will output like the following:

Original Linked List:
1 -> 2 -> 3 -> 2 -> 4 -> 5 -> 1 -> 6 -> 3 -> 7 -> None

3. Remove Duplicate Nodes

To remove duplicate nodes from the linked list, we’ll use a Python dictionary to keep track of the elements we have seen so far. We will iterate through the list, and for each node, check if its data exists in the dictionary. If it does, we’ll bypass the node and link the previous node directly to the next non-duplicate node. If it doesn’t, we’ll add it to the dictionary for future reference.

Here’s the implementation of the removal process:

def remove_duplicates(head):
    if not head:
        return head

    seen_data = set()
    current = head
    previous = None

    while current:
        if current.data in seen_data:
            previous.next = current.next
        else:
            seen_data.add(current.data)
            previous = current

        current = current.next

    return head

Now, let’s apply the `remove_duplicates` function to our example linked list:

linked_list = remove_duplicates(linked_list)
print("Linked List after removing duplicates:")
print_linked_list(linked_list)

Now the program will output like the following:

Original Linked List:
1 -> 2 -> 3 -> 2 -> 4 -> 5 -> 1 -> 6 -> 3 -> 7 -> None
Linked List after removing duplicates:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> None

Conclusion

Congratulations! You now know how to remove duplicate nodes from a linked list in Python, regardless of whether the list is sorted or unsorted. By utilizing a Python Dictionary to keep track of elements, we efficiently identify and remove duplicates while maintaining the original order of the list.

Remember that the time complexity of this approach is O(N) since we need to traverse the entire linked list once, and the space complexity is also O(N) due to the additional space used by the dictionary to store unique elements.

Linked lists are powerful data structures, and understanding how to manipulate them can be beneficial in various programming scenarios. Happy coding!