Posted on by Kalkicode

# 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.

## 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():
find = null
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.

## 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.

Categories
Relative Post