Doubly Linked List: Program to remove duplicates from a sorted doubly linked list

Write a program to remove duplicate nodes from a sorted doubly linked list

A doubly linked list is a type of linked list that consist of nodes and bi-directional edges

• There are 2 edges/links between any two nodes - lets call them 'next' & 'prev'
• 'next' pointer points to next node and 'prev' pointer points to the previous node
• These bi-directional edges help us to navigate forward and backward in a linked list

Approach

• To remove the duplicates we traverse the doubly linked list
• compare the current node with the next node
• if the data is same we remove the next element
• then move to next node for comparison

Algorithm

1. If head is NULL then return from function
2. Create pointer 'current' and point on head
3. While current.next is not eqaul to NULL, traverse the doubly linked list
4. While traversing, if current.data and current.next.data are equal then create pointer say temp and point on current.next
5. Using temp delete the current.next node as follows
   • If temp next is NULL, then make temp.prev.next = NULL, and temp.prev = NULL
   • Else make temp.prev.next = temp.next and temp.next.prev = temp.prev
6. Else make current = current.next

Complexity

Time Complexity : O(n) , where n is the size of doubly linked list
Space Complexity : O(1)

Java Code

import java.util.*;

 class RemoveDuplicateDLL{
        
        class Node {
            int data;
            Node next, prev;
         
            Node(int d) {
                this.data = d;
                this.next = null;
                this.prev = null;
            }
        }
     
        Node head;
     
        // creating a linked list using array
        public void buildLinkedlist(int A[], int noOfNodes) {
            Node temp, last;
            temp = new Node(A[0]);
            temp.next = temp.prev = null;
            head = temp;
            last = head;
     
            for (int i = 1; i < noOfNodes; i++) {
                temp = new Node(A[i]);
                temp.next = null;
                temp.prev = last;
                last.next = temp;
                last = temp;
            }
        }
     
        // printing of linkedList
        public void printLinkedlist() {
            List allNodesList = new ArrayList<>();
            Node temp = head;
            while (temp != null) {
                allNodesList.add(Integer.toString(temp.data));
                temp = temp.next;
            }
            System.out.println(String.join(" <-> ", allNodesList));
        }
     
        public void removeDuplicates() {
            if (head == null)
                return;
            Node current = head;
            while (current.next != null) {
                if (current.data == current.next.data) {
                    Node temp = current.next;
                    if (temp.next == null) {
                        temp.prev.next = null;
                        temp.prev = null;
                    } else {
                        temp.prev.next = temp.next;
                        temp.next.prev = temp.prev;
                    }
                } else {
                    current = current.next;
                }
     
            }
        }
     
        public static void main(String[] args) {
            int[] linkedlistElements = new int[] { 1, 2, 3, 3, 4, 4, 5};
            int numberOfNodes = linkedlistElements.length;
            // initialising object of linkedlist class
            RemoveDuplicateDLL dll = new RemoveDuplicateDLL();
            dll.buildLinkedlist(linkedlistElements, numberOfNodes);
            System.out.println("Given Doubly Linked List ");
            dll.printLinkedlist(); 
            dll.removeDuplicates();
            System.out.println("Doubly Linked List after removing duplicates ");
            dll.printLinkedlist();
     
        }
  }

Output

Given Doubly Linked List
1 <-> 2 <-> 3 <-> 3 <-> 4 <-> 4 <-> 5
Doubly Linked List after removing duplicates
1 <-> 2 <-> 3 <-> 4 <-> 5