# 5 Best Ways to Remove Duplicate Entries in a Linked List in Python

Rate this post

π‘ Problem Formulation: When working with linked lists in Python, a common problem is the presence of duplicate nodes containing the same data value. This can be problematic in applications that require uniqueness of elements. For example, given a linked list `1 -> 3 -> 3 -> 2 -> 1`, the goal is to transform it into `1 -> 3 -> 2` by removing duplicated entries.

## Method 1: Using Hashtable Tracking

This method involves iterating through the linked list while keeping track of seen values in a hashtable (e.g., a Python dictionary). If a node with a value already seen is encountered, it’s removed from the list. It guarantees that each element will remain in the linked list only once, thus removing duplicates.

Here’s an example:

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

seen = set()
previous = None
while current:
if current.data in seen:
previous.next = current.next
else:
previous = current
current = current.next

Output of this code will be the linked list without duplicates.

This code snippet defines a `Node` class for our linked list and a `remove_duplicates` function. The function uses a `set` to keep track of unique elements and removes nodes with duplicate data. The `previous` pointer is critical for bypassing the unwanted nodes.

## Method 2: Nested Iteration Comparison

Without using additional space, this method utilizes two pointers. The first pointer iterates through the list, while the second pointer checks all subsequent nodes for duplicates, removing any it finds. It’s less efficient but does not use extra memory beyond the two pointers.

Here’s an example:

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

Output of this code will be the linked list without duplicates.

This code snippet uses a two-pointer approach. The `current` pointer goes through each node, while `runner` checks for duplicates ahead in the list. When duplicates are found, they are skipped over, effectively removing them from the list.

## Method 3: Sort and Remove

If the list can be sorted, duplicates will be adjacent and easy to remove in a single pass. This method sorts the list first and then simply compares each node to its successor, removing any duplicates detected.

Here’s an example:

```# Note: This assumes that the linked list has a sorting method implemented.
return None
while current.next:
if current.data == current.next.data:
current.next = current.next.next
else:
current = current.next

Output of this code would result in a sorted linked list without duplicates.

After sorting the list, the `remove_duplicates_sorted` function iterates through it. Since duplicates are now adjacent, the function can easily remove them by setting the `next` pointer of a node to skip the duplicate.

## Method 4: Recursive Deduplication

This approach uses recursion to remove duplicates from a linked list. Starting from the head, it removes all nodes of the same value as the head, then applies the same logic recursively to the remaining list.

Here’s an example:

```def remove_duplicates(head):

Output of this code would be a linked list with duplicates removed.

The recursive function works by removing duplicates immediately following the head node and then proceeding to do the same for the rest of the list recursively. This is a succinct solution but may lead to a stack overflow for large lists.

## Bonus One-Liner Method 5: Using Collections Counter (Not recommended for actual linked lists)

This method is not practical for linked list data structures but can demonstrate how Python’s built-in libraries can be utilized to remove duplicates from a collection. It uses the `collections.Counter` to count occurrences, then reconstructs the list with only unique elements.

Here’s an example:

```from collections import Counter

def remove_duplicates(lst):
return list(Counter(lst).keys())```

Output of this code will be `[1, 3, 2]` for the example list.

This one-liner approach simplifies the process drastically. The `Counter` creates a hashtable of all list elements, and converting the keys back into a list removes duplicates. This, however, assumes a regular Python `list` and not a true linked list structure.

## Summary/Discussion

• Method 1: Hashtable Tracking. Strengths: Efficient and simple. Weaknesses: Requires extra space for the hashtable.
• Method 2: Nested Iteration Comparison. Strengths: No extra space needed. Weaknesses: Time complexity of O(n^2) makes it less efficient for large lists.
• Method 3: Sort and Remove. Strengths: Simple approach if list can be sorted. Weaknesses: Sorting can be inefficient and alters the original list order.
• Method 4: Recursive Deduplication. Strengths: Conceptually simple and elegant. Weaknesses: Potentially high stack memory usage and risk of stack overflow.
• Bonus Method 5: Using Collections Counter. Strengths: Very concise. Weaknesses: Not applicable to actual linked list data structures and misrepresents the algorithm’s scalability and applicability.