# Remove duplicates from an unsorted doubly linked list

Given an unsorted doubly linked list containing n nodes. The problem is to remove duplicate nodes from the given list.

Examples:

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Method 1 (Naive Approach):
This is the simplest way where two loops are used. Outer loop is used to pick the elements one by one and inner loop compares the picked element with rest of the elements.

Output:

8 4 4 6 4 8 4 10 12 12
Doubly linked list after removing duplicates:
8 4 6 10 12

Time Complexity: O(n2)
Auxiliary Space: O(1)

Method 2 (Sorting): Following are the steps:

1. Sort the elements of the doubly linked list using Merge Sort. Refer this post.
2. Remove duplicates in linear time using the algorithm to remove duplicates from a sorted doubly linked list.

Time Complexity: O(nLogn)
Auxiliary Space: O(1)

Note that this method doesn’t preserve the original order of elements.

Method 3 Efficient Approach(Hashing):
We traverse the doubly linked list from head to end. For every newly encountered element, we check whether it is in the hash table: if yes, we remove it; otherwise we put it in the hash table. Hash table is implemented using unordered_set in C++.

Output:

8 4 4 6 4 8 4 10 12 12
Doubly linked list after removing duplicates:
8 4 6 10 12

Time Complexity: O(n)
Auxiliary Space: O(n)