Posted on by Kalkicode
Code Doubly linked list

Remove duplicates from an unsorted doubly linked list

The problem presented here involves removing duplicate values from an unsorted doubly linked list. A doubly linked list is a data structure where each node contains a value, a reference to the next node, and a reference to the previous node. The goal is to eliminate duplicate values so that each value appears only once in the list.

Remove duplicates from an unsorted doubly linked list After Removing of duplicate nodes in doubly linked list

Problem Statement

Given an unsorted doubly linked list, we need to remove all duplicate values from it, ensuring that each value remains unique.

Example

Let's consider an example to understand the problem. Suppose we have an unsorted doubly linked list with the following values: 1, 1, 4, 6, 6, 6, 7, 8, 1. After removing duplicates, the list should be: 1, 4, 6, 7, 8.

Idea to Solve

To remove duplicates from an unsorted doubly linked list, we will use two nested loops to compare each node with all subsequent nodes. The outer loop iterates through each node, and the inner loop checks if any subsequent nodes have the same value. If a duplicate is found, we will remove that node from the list. To do this, we will adjust the next and prev pointers of the neighboring nodes around the duplicate node.

Pseudocode

Here's the pseudocode that outlines the algorithm to remove duplicates from an unsorted doubly linked list:

function removeNode():
    if head is not null:
        current = head
        while current is not null:
            temp = current.next
            while temp is not null:
                if temp.data == current.data:
                    if temp.prev is not null:
                        temp.prev.next = temp.next
                    if temp.next is not null:
                        temp.next.prev = temp.prev
                    if temp == tail:
                        tail = temp.prev
                    temp.prev = null
                    temp.next = null
                temp = temp.next
            current = current.next

Algorithm Explanation

  • We start by initializing a current pointer with the head of the linked list.
  • The outer loop iterates through each node, and the inner loop starts from the current node's next node.
  • Inside the inner loop, we compare the value of the current node (temp) with the current node.
  • If a duplicate value is found, we update the next and prev pointers of neighboring nodes to bypass the duplicate node.
  • If the duplicate node is the tail, we update the tail to be the previous node.
  • After processing a duplicate node, we remove its next and prev references to disconnect it from the list.
  • We repeat this process for all nodes in the list.
  • At the end of the algorithm, the list will be free of duplicate values.

Code Solution

Time Complexity

  • The algorithm uses nested loops, iterating through each node and comparing it with subsequent nodes.
  • The time complexity of this algorithm is O(n^2), where n is the number of nodes in the linked list.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment