Posted on by Kalkicode
Code Doubly linked list

Remove duplicates from a sorted doubly linked list

The problem discussed in this article is about removing duplicates from a sorted doubly linked list. A doubly linked list is a data structure consisting of nodes where each node has a value, a reference to the next node, and a reference to the previous node. The problem requires removing duplicate values while keeping the list sorted.

Remove duplicates of this linked list Remove duplicates of this linked list

Problem Statement

Given a sorted doubly linked list, we need to remove duplicate values so that each value appears only once in the list.

Example

Consider an example to illustrate the problem. We have a sorted doubly linked list with the following values: 5, 5, 7, 9, 9, 9, 11, 45, 45. After removing duplicates, the list should be: 5, 7, 9, 11, 45.

Idea to Solve

Since the given list is sorted, we can remove duplicates by iterating through the list once and comparing each node's value with the value of the next node. If a duplicate value is found, we remove that node from the list by adjusting the next and prev pointers of the neighboring nodes.

Pseudocode

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

function removeNode():
    if head is not null:
        find = null
        node = head.next
        while node is not null:
            if node.prev.data == node.data:
                find = node
            node = node.next
            if find is not null:
                if find.prev is not null:
                    find.prev.next = node
                if node is not null:
                    node.prev = find.prev
                find.prev = null
                find.next = null
                find = null

Algorithm Explanation

  • We start by initializing a find pointer as null. This pointer will help us identify duplicate nodes.
  • We initialize a node pointer with the second node in the list (head.next).
  • We iterate through the list, comparing each node's value with the value of its previous node (node.prev).
  • If a duplicate value is found, we set the find pointer to the duplicate node.
  • We continue iterating through the list using the node pointer.
  • If the find pointer is not null (indicating a duplicate node), we adjust the next and prev pointers of neighboring nodes to remove the duplicate node 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.

Program List

Time Complexity

  • The algorithm iterates through the entire linked list once.
  • The time complexity of this algorithm is O(n), 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