# Remove duplicates from a sorted doubly linked list

Given a sorted 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.

Algorithm:

```removeDuplicates(head_ref, x)
return
while current->next != NULL
if current->data == current->next->data
else
current = current->next
```

The algorithm for deleteNode(head_ref, current) (which deletes the node using the pointer to the node) is discussed in this post.

## C++

 `/* C++ implementation to remove duplicates from a  ` `   ``sorted doubly linked list */` `#include ` ` `  `using` `namespace` `std; ` ` `  `/* a node of the doubly linked list */` `struct` `Node { ` `    ``int` `data; ` `    ``struct` `Node* next; ` `    ``struct` `Node* prev; ` `}; ` ` `  `/* Function to delete a node in a Doubly Linked List. ` `   ``head_ref --> pointer to head node pointer. ` `   ``del  -->  pointer to node to be deleted. */` `void` `deleteNode(``struct` `Node** head_ref, ``struct` `Node* del) ` `{ ` `    ``/* base case */` `    ``if` `(*head_ref == NULL || del == NULL) ` `        ``return``; ` ` `  `    ``/* If node to be deleted is head node */` `    ``if` `(*head_ref == del) ` `        ``*head_ref = del->next; ` ` `  `    ``/* Change next only if node to be deleted  ` `        ``is NOT the last node */` `    ``if` `(del->next != NULL) ` `        ``del->next->prev = del->prev; ` ` `  `    ``/* Change prev only if node to be deleted  ` `       ``is NOT the first node */` `    ``if` `(del->prev != NULL) ` `        ``del->prev->next = del->next; ` ` `  `    ``/* Finally, free the memory occupied by del*/` `    ``free``(del); ` `} ` ` `  `/* function to remove duplicates from a  ` `   ``sorted doubly linked list */` `void` `removeDuplicates(``struct` `Node** head_ref) ` `{ ` `    ``/* if list is empty */` `    ``if` `((*head_ref) == NULL) ` `        ``return``; ` ` `  `    ``struct` `Node* current = *head_ref; ` `    ``struct` `Node* next; ` ` `  `    ``/* traverse the list till the last node */` `    ``while` `(current->next != NULL) { ` ` `  `        ``/* Compare current node with next node */` `        ``if` `(current->data == current->next->data) ` ` `  `            ``/* delete the node pointed to by ` `              ``'current->next' */` `            ``deleteNode(head_ref, current->next); ` ` `  `        ``/* else simply move to the next node */` `        ``else` `            ``current = current->next; ` `    ``} ` `} ` ` `  `/* Function to insert a node at the beginning  ` `   ``of the Doubly Linked List */` `void` `push(``struct` `Node** head_ref, ``int` `new_data) ` `{ ` `    ``/* allocate node */` `    ``struct` `Node* new_node =  ` `           ``(``struct` `Node*)``malloc``(``sizeof``(``struct` `Node)); ` ` `  `    ``/* put in the data  */` `    ``new_node->data = new_data; ` ` `  `    ``/* since we are adding at the begining, ` `    ``prev is always NULL */` `    ``new_node->prev = NULL; ` ` `  `    ``/* link the old list off the new node */` `    ``new_node->next = (*head_ref); ` ` `  `    ``/* change prev of head node to new node */` `    ``if` `((*head_ref) != NULL) ` `        ``(*head_ref)->prev = new_node; ` ` `  `    ``/* move the head to point to the new node */` `    ``(*head_ref) = new_node; ` `} ` ` `  `/* Function to print nodes in a given doubly linked list */` `void` `printList(``struct` `Node* head) ` `{ ` `    ``/* if list is empty */` `    ``if` `(head == NULL) ` `        ``cout << ``"Doubly Linked list empty"``; ` ` `  `    ``while` `(head != NULL) { ` `        ``cout << head->data << ``" "``; ` `        ``head = head->next; ` `    ``} ` `} ` ` `  `/* Driver program to test above functions*/` `int` `main() ` `{ ` `    ``/* Start with the empty list */` `    ``struct` `Node* head = NULL; ` ` `  `    ``/* Create the doubly linked list: ` `     ``4<->4<->4<->4<->6<->8<->8<->10<->12<->12 */` `    ``push(&head, 12); ` `    ``push(&head, 12); ` `    ``push(&head, 10); ` `    ``push(&head, 8); ` `    ``push(&head, 8); ` `    ``push(&head, 6); ` `    ``push(&head, 4); ` `    ``push(&head, 4); ` `    ``push(&head, 4); ` `    ``push(&head, 4); ` ` `  `    ``cout << ``"Original Doubly linked list:n"``; ` `    ``printList(head); ` ` `  `    ``/* remove duplicate nodes */` `    ``removeDuplicates(&head); ` ` `  `    ``cout << ````" Doubly linked list after"``` `             ``" removing duplicates:n"``; ` `    ``printList(head); ` ` `  `    ``return` `0; ` `} `

## Java

 `/* Java implementation to remove duplicates from a   ` `   ``sorted doubly linked list */` `public` `class` `removeDuplicatesFromSortedList { ` ` `  `    ``/* function to remove duplicates from a   ` `   ``sorted doubly linked list */` `    ``public` `static` `void` `removeDuplicates(Node head)  ` `    ``{  ` `        ``/* if list is empty */` `        ``if` `(head== ``null``)  ` `            ``return``;  ` `   `  `        ``Node current = head;  ` `        ``while` `(current.next != ``null``)  ` `        ``{  ` `            ``/* Compare current node with next node */` `            ``if` `(current.data == current.next.data)  ` `                ``/* delete the node pointed to by  ` `              ``' current->next' */` `                ``deleteNode(head, current.next);  ` `   `  `            ``/* else simply move to the next node */` `            ``else` `                ``current = current.next;  ` `        ``}   ` `   `  `        ``/* traverse the list till the last node */` `        ``while` `(current.next != ``null``)  ` `        ``{  ` `   `  `            ``/* Compare current node with next node */` `            ``if` `(current.data == current.next.data)  ` `            ``/* delete the node pointed to by  ` `              ``'current->next' */` `                ``deleteNode(head, current.next);  ` `   `  `            ``/* else simply move to the next node */` `            ``else` `                ``current = current.next;  ` `        ``}  ` `    ``}  ` ` `  ` `  `    ``/* Function to delete a node in a Doubly Linked List.  ` `    ``head_ref --> pointer to head node pointer.  ` `    ``del  -->  pointer to node to be deleted. */` `    ``public` `static` `void` `deleteNode(Node head, Node del) ` `    ``{ ` `         ``/* base case */` `        ``if``(head==``null` `|| del==``null``) ` `        ``{ ` `            ``return` `; ` `        ``} ` `        ``/* If node to be deleted is head node */` `        ``if``(head==del) ` `        ``{ ` `            ``head=del.next; ` `        ``} ` `        ``/* Change next only if node to be deleted   ` `        ``is NOT the last node */` `        ``if``(del.next!=``null``) ` `        ``{ ` `            ``del.next.prev=del.prev; ` `        ``} ` `        ``/* Change prev only if node to be deleted   ` `       ``is NOT the first node */` `        ``if` `(del.prev != ``null``)  ` `            ``del.prev.next = del.next;  ` ` `  `    ``} ` ` `  ` `  `    ``/* Function to insert a node at the beginning   ` `    ``of the Doubly Linked List */` `    ``public` `static` `Node push(Node head, ``int` `data) ` `    ``{ ` `        ``/* allocate node */` `        ``Node newNode=``new` `Node(data); ` `        ``/* since we are adding at the begining,  ` `        ``prev is always NULL */` `        ``newNode.prev=``null``; ` `        ``/* link the old list off the new node */` `        ``newNode.next =head;  ` `        ``/* change prev of head node to new node */` `        ``if``(head!=``null``) ` `        ``{ ` `            ``head.prev=newNode; ` `        ``} ` `        ``head=newNode; ` `        ``return` `head; ` `    ``} ` ` `  `    ``/* Function to print nodes in a given doubly linked list */` `    ``public` `static` `void` `printList(Node head) ` `    ``{ ` `        ``if` `(head == ``null``)  ` `            ``System.out.println(``"Doubly Linked list empty"``); ` `         `  `        ``while` `(head != ``null``)  ` `        ``{  ` `            ``System.out.print(head.data+``" "``) ; ` `            ``head = head.next;  ` `        ``} ` `    ``} ` ` `  `    ``public` `static` `void` `main(String args[]) { ` `        ``Node head=``null``; ` `        ``head=push(head, ``12``);  ` `        ``head=push(head, ``12``);  ` `        ``head=push(head, ``10``);  ` `        ``head=push(head, ``8``);  ` `        ``head=push(head, ``8``);  ` `        ``head=push(head, ``6``);  ` `        ``head=push(head, ``4``);  ` `        ``head=push(head, ``4``);  ` `        ``head=push(head, ``4``);  ` `        ``head=push(head, ``4``); ` ` `  `        ``System.out.println(``"Original Doubly LinkedList"``); ` `        ``printList(head);  ` ` `  `        ``/* remove duplicate nodes */` `        ``removeDuplicates(head);  ` `        ``System.out.println(````" Doubly linked list after removing duplicates:"````); ` `        ``printList(head); ` `    ``} ` `} ` `class` `Node ` `{ ` `    ``int` `data; ` `    ``Node next,prev; ` ` `  `    ``Node(``int` `data) ` `    ``{ ` `        ``this``.data=data; ` `        ``next=``null``; ` `        ``prev=``null``; ` `    ``} ` `} ` `//This code is contributed by Gaurav Tiwari `

## C#

 `/* C# implementation to remove duplicates from a  ` `sorted doubly linked list */` `using` `System;  ` ` `  `public` `class` `removeDuplicatesFromSortedList  ` `{  ` ` `  `    ``/* function to remove duplicates from a  ` `    ``sorted doubly linked list */` `    ``public` `static` `void` `removeDuplicates(Node head)  ` `    ``{  ` `        ``/* if list is empty */` `        ``if` `(head == ``null``)  ` `            ``return``;  ` `     `  `        ``Node current = head;  ` `        ``while` `(current.next != ``null``)  ` `        ``{  ` `            ``/* Compare current node with next node */` `            ``if` `(current.data == current.next.data)  ` `             `  `                ``/* delete the node pointed to by  ` `            ``' current->next' */` `                ``deleteNode(head, current.next);  ` `     `  `            ``/* else simply move to the next node */` `            ``else` `                ``current = current.next;  ` `        ``}  ` `     `  `        ``/* traverse the list till the last node */` `        ``while` `(current.next != ``null``)  ` `        ``{  ` `     `  `            ``/* Compare current node with next node */` `            ``if` `(current.data == current.next.data)  ` `             `  `            ``/* delete the node pointed to by  ` `            ``'current->next' */` `                ``deleteNode(head, current.next);  ` `     `  `            ``/* else simply move to the next node */` `            ``else` `                ``current = current.next;  ` `        ``}  ` `    ``}  ` ` `  ` `  `    ``/* Function to delete a node in a Doubly Linked List.  ` `    ``head_ref --> pointer to head node pointer.  ` `    ``del --> pointer to node to be deleted. */` `    ``public` `static` `void` `deleteNode(Node head, Node del)  ` `    ``{  ` `        ``/* base case */` `        ``if``(head == ``null` `|| del == ``null``)  ` `        ``{  ` `            ``return` `;  ` `        ``}  ` `         `  `        ``/* If node to be deleted is head node */` `        ``if``(head == del)  ` `        ``{  ` `            ``head = del.next;  ` `        ``}  ` `         `  `        ``/* Change next only if node to be deleted  ` `        ``is NOT the last node */` `        ``if``(del.next != ``null``)  ` `        ``{  ` `            ``del.next.prev = del.prev;  ` `        ``}  ` `         `  `        ``/* Change prev only if node to be deleted  ` `        ``is NOT the first node */` `        ``if` `(del.prev != ``null``)  ` `            ``del.prev.next = del.next;  ` ` `  `    ``}  ` ` `  ` `  `    ``/* Function to insert a node at the beginning  ` `    ``of the Doubly Linked List */` `    ``public` `static` `Node push(Node head, ``int` `data)  ` `    ``{  ` `        ``/* allocate node */` `        ``Node newNode = ``new` `Node(data);  ` `         `  `        ``/* since we are adding at the begining,  ` `        ``prev is always NULL */` `        ``newNode.prev = ``null``;  ` `         `  `        ``/* link the old list off the new node */` `        ``newNode.next = head;  ` `         `  `        ``/* change prev of head node to new node */` `        ``if``(head != ``null``)  ` `        ``{  ` `            ``head.prev = newNode;  ` `        ``}  ` `        ``head = newNode;  ` `        ``return` `head;  ` `    ``}  ` ` `  `    ``/* Function to print nodes in a given doubly linked list */` `    ``public` `static` `void` `printList(Node head)  ` `    ``{  ` `        ``if` `(head == ``null``)  ` `            ``Console.WriteLine(``"Doubly Linked list empty"``);  ` `         `  `        ``while` `(head != ``null``)  ` `        ``{  ` `            ``Console.Write(head.data + ``" "``) ;  ` `            ``head = head.next;  ` `        ``}  ` `    ``}  ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main(String []args)  ` `    ``{  ` `        ``Node head = ``null``;  ` `        ``head = push(head, 12);  ` `        ``head = push(head, 12);  ` `        ``head = push(head, 10);  ` `        ``head = push(head, 8);  ` `        ``head = push(head, 8);  ` `        ``head = push(head, 6);  ` `        ``head = push(head, 4);  ` `        ``head = push(head, 4);  ` `        ``head = push(head, 4);  ` `        ``head = push(head, 4);  ` ` `  `        ``Console.WriteLine(``"Original Doubly LinkedList"``);  ` `        ``printList(head);  ` ` `  `        ``/* remove duplicate nodes */` `        ``removeDuplicates(head);  ` `        ``Console.WriteLine(````" Doubly linked list after"``` `+  ` `                            ``"removing duplicates:"``);  ` `        ``printList(head);  ` `    ``}  ` `}  ` ` `  `public` `class` `Node  ` `{  ` `    ``public` `int` `data;  ` `    ``public` `Node next,prev;  ` ` `  `    ``public` `Node(``int` `data)  ` `    ``{  ` `        ``this``.data = data;  ` `        ``next = ``null``;  ` `        ``prev = ``null``;  ` `    ``}  ` `}  ` ` `  `// This code is contributed by 29AjayKumar. `

Output:

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

Time Complexity: O(n)