Given a doubly linked list. The problem is to remove all adjacent duplicate nodes from the list such that the final modified doubly linked list does not contain any adjacent duplicate nodes. Examples: 
Approach: The approach uses stack to keep track of the adjacent nodes at any point in the modified Doubly Linked List. Algorithm:
delAdjacentDuplicates(head_ref)
Create an empty stack st
Declare current, next, top
current = head_ref
while current != NULL
if isEmpty(st) or current->data != peek(st)->data
push current on to the stack st
current = current->next
else
next = current->next
top = peek(st)
pop element from st
delete node 'current'
delete node 'top'
current = next
peek(st) operation returns the value at the top of the stack. The algorithm to delete a node n from the doubly linked list using pointer to the node n is discussed in this post.
C++
/* C++ implementation to delete adjacent duplicate nodesfrom the Doubly Linked List */#include <bits/stdc++.h>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 delete adjacent duplicate nodes fromthe Doubly Linked List */void delAdjacentDupNodes(struct Node** head_ref){ // an empty stack 'st' stack<Node*> st; struct Node* current = *head_ref; /* traverse the doubly linked list */ while (current != NULL) { /* if stack 'st' is empty or if current->data != st.top()->data push 'current' on to the stack 'st' */ if (st.empty() || current->data != st.top()->data) { st.push(current); /* move to the next node */ current = current->next; } // else current->data == st.top()->data else { /* pointer to the node next to the 'current' node */ struct Node* next = current->next; /* pointer to the node at the top of 'st' */ struct Node* top = st.top(); /* remove top element from 'st' */ st.pop(); /* delete 'current' node from the list */ deleteNode(head_ref, current); /* delete 'top' node from the list */ deleteNode(head_ref, top); /* update 'current' */ current = next; } }}/* Function to insert a node at the beginningof 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 beginning, prev is always NULL */ new_node->prev = NULL; /* link the old list of 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 (head == NULL) cout << "Empty Doubly Linked List"; 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 10<->8<->4<->4<->8<->5 */ push(&head, 5); push(&head, 8); push(&head, 4); push(&head, 4); push(&head, 8); push(&head, 10); cout << "Doubly linked list before deletion:n"; printList(head); /* delete adjacent duplicate nodes */ delAdjacentDupNodes(&head); cout << "nDoubly linked list after deletion:n"; printList(head); return 0;} |
Java
import java.util.*;class Node { int data; Node next; Node prev;}class Main { static void deleteNode(Node head_ref[], Node del) { if (head_ref[0] == null || del == null) { return; } if (head_ref[0] == del) { head_ref[0] = del.next; } if (del.next != null) { del.next.prev = del.prev; } if (del.prev != null) { del.prev.next = del.next; } del = null; } static void delAdjacentDupNodes(Node head_ref[]) { Stack<Node> st = new Stack<>(); Node current = head_ref[0]; while (current != null) { if (st.empty() || current.data != st.peek().data) { st.push(current); current = current.next; } else { Node next = current.next; Node top = st.peek(); st.pop(); deleteNode(head_ref, current); deleteNode(head_ref, top); current = next; } } } static void push(Node head_ref[], int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.prev = null; new_node.next = head_ref[0]; if (head_ref[0] != null) { head_ref[0].prev = new_node; } head_ref[0] = new_node; } static void printList(Node head) { if (head == null) { System.out.println("Empty Doubly Linked List"); } while (head != null) { System.out.print(head.data + " "); head = head.next; } } public static void main(String args[]) { Node[] head = new Node[1]; head[0] = null; push(head, 5); push(head, 8); push(head, 4); push(head, 4); push(head, 8); push(head, 10); System.out.println("Doubly linked list before deletion:"); printList(head[0]); delAdjacentDupNodes(head); System.out.println("\nDoubly linked list after deletion:"); printList(head[0]); }} |
C#
/* C# implementation to delete adjacent duplicate nodesfrom the Doubly Linked List */using System;/* a node of the doubly linked list */public class Node{ public int data; public Node next; public Node prev;};public class Program{ /* Function to delete a node in a Doubly Linked List. head_ref --> pointer to head node pointer. del --> pointer to node to be deleted. */ static void deleteNode(ref Node head_ref, 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*/ del = null; } /* function to delete adjacent duplicate nodes from the Doubly Linked List */ static void delAdjacentDupNodes(ref Node head_ref) { // an empty stack 'st' var st = new System.Collections.Generic.Stack<Node>(); Node current = head_ref; /* traverse the doubly linked list */ while (current != null) { /* if stack 'st' is empty or if current->data != st.top()->data push 'current' on to the stack 'st' */ if (st.Count == 0 || current.data != st.Peek().data) { st.Push(current); /* move to the next node */ current = current.next; } // else current->data == st.top()->data else { /* pointer to the node next to the 'current' node */ Node next = current.next; /* pointer to the node at the top of 'st' */ /* remove top element from 'st' */ Node top = st.Pop(); /* delete 'current' node from the list */ deleteNode(ref head_ref, current); /* delete 'top' node from the list */ deleteNode(ref head_ref, top); /* update 'current' */ current = next; } } } /* Function to insert a node at the beginning of the Doubly Linked List */ static void push(ref Node head_ref, int new_data) { /* allocate node */ Node new_node = new Node(); /* put in the data */ new_node.data = new_data; /* since we are adding at the beginning, prev is always NULL */ new_node.prev = null; /* link the old list of 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 */ static void printList(Node head) { if (head == null) Console.WriteLine("Empty Doubly Linked List"); while (head != null) { Console.Write(head.data + " "); head = head.next; } } /* Driver program to test above functions*/ static void Main(string[] args) { /* Start with the empty list */ Node head = null; /* Create the doubly linked list 10<->8<->4<->4<->8<->5 */ push(ref head, 5); push(ref head, 8); push(ref head, 4); push(ref head, 4); push(ref head, 8); push(ref head, 10); Console.WriteLine("Doubly linked list before deletion:"); printList(head); /* delete adjacent duplicate nodes */ delAdjacentDupNodes(ref head); Console.WriteLine("\nDoubly linked list after deletion:"); printList(head); }} |
Python3
class Node: def __init__(self): self.data = 0 self.next = None self.prev = Nonedef deleteNode(head_ref, del_node): if not head_ref or not del_node: return if head_ref[0] == del_node: head_ref[0] = del_node.next if del_node.next: del_node.next.prev = del_node.prev if del_node.prev: del_node.prev.next = del_node.next del_node = Nonedef delAdjacentDupNodes(head_ref): st = [] current = head_ref[0] while current: if not st or current.data != st[-1].data: st.append(current) current = current.next else: nxt = current.next top = st.pop() deleteNode(head_ref, current) deleteNode(head_ref, top) current = nxtdef push(head_ref, new_data): new_node = Node() new_node.data = new_data new_node.prev = None new_node.next = head_ref[0] if head_ref[0]: head_ref[0].prev = new_node head_ref[0] = new_nodedef printList(head): if not head: print("Empty Doubly Linked List") else: while head: print(head.data, end=" ") head = head.next print()if __name__ == '__main__': head = [None] push(head, 5) push(head, 8) push(head, 4) push(head, 4) push(head, 8) push(head, 10) print("Doubly linked list before deletion:") printList(head[0]) delAdjacentDupNodes(head) print("Doubly linked list after deletion:") printList(head[0]) |
Javascript
// Javascript code addition /* a node of the doubly linked list */class Node { constructor(data) { this.data = data; this.next = null; this.prev = null; }} /* Function to delete a node in a Doubly Linked List.head_ref --> pointer to head node pointer.del --> pointer to node to be deleted. */function deleteNode(head_ref, 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*/ del = null;} /* function to delete adjacent duplicate nodes from the Doubly Linked List */function delAdjacentDupNodes(head_ref) { // an empty stack 'st' let st = []; let current = head_ref; /* traverse the doubly linked list */ while (current != null) { /* if stack 'st' is empty or if current.data != st.top().data push 'current' on to the stack 'st' */ if (st.length == 0 || current.data != st[st.length - 1].data) { st.push(current); /* move to the next node */ current = current.next; } // else current.data == st.top().data else { /* pointer to the node next to the 'current' node */ let next = current.next; /* pointer to the node at the top of 'st' */ /* remove top element from 'st' */ let top = st.pop(); /* delete 'current' node from the list */ deleteNode(head_ref, current); /* delete 'top' node from the list */ deleteNode(head_ref, top); /* update 'current' */ current = next; } }} /* Function to insert a node at the beginning of the Doubly Linked List */function push(head_ref, new_data) { /* allocate node */ let new_node = new Node(new_data); /* link the old list of 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; return head_ref;} /* Function to print nodes in a given doubly linked list */function printList(head) { if (head == null) { console.log("Empty Doubly Linked List"); return; } let output = ""; while (head != null) { output += head.data + " "; head = head.next; } console.log(output);} /* Driver program to test above functions*//* Start with the empty list */let head = null;/* Create the doubly linked list 10<->8<->4<->4<->8<->5 */head = push(head, 5);head = push(head, 8);head = push(head, 4);head = push(head, 4);head = push(head, 8);head = push(head, 10);console.log("Doubly linked list before deletion:");printList(head); /* delete adjacent duplicate nodes */delAdjacentDupNodes(head);console.log("\nDoubly linked list after deletion:");printList(head);// The code is contributed by Nidhi goel. |
Output:
Doubly linked list before deletion: 10 8 4 4 8 5 Doubly linked list after deletion: 10 5
Time Complexity: O(n) Auxiliary Space: O(n), in worst case when there are no adjacent duplicate nodes. If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.uk or mail your article to review-team@neveropen.co.uk. See your article appearing on the neveropen main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
