Doubly Linked List: Program to remove duplicates from an unsorted DLL

Write a program to remove duplicate nodes from an unsorted 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 duplicates from an unsorted doubly linked list:

• Using two loops we check for duplicate nodes
• The outer loop pick one node and the inner loop traverses linked list starting from node after the node picked by outer loop and compares them
• If a matching node is found then delete it and move forward for checking other nodes

Algorithm

1. If head is NULL or head.next is NULL, then return
2. Create two pointer say current1 and current2.set current1 on head and current2 on current1.next
3. Using for loop traverse linked list with condition that current1 is not NULL
4. While traversing check whether duplicate of current1 is present using while loop till current2 is not NULL
5. If current1.data is eqaul to current2.data, then delete node pointed by current2
6. Create pointer next and point on current2.next
   • If current2.next is null then make, current2.prev.next = NULL, and current2.prev = NULL
   • Else make current2.prev.next = current2.next and current.next.prev = current.prev
7. Else make current2 = current2.next

Complexity

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

Java Code

import java.util.*;

class RemoveDuplicateDLLUnsorted{
     
        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 || head.next == null)
                return;
            Node current1, current2;
            for (current1 = head; current1 != null; current1 = current1.next) {
                current2 = current1.next;
     
                while (current2 != null) {
                    if (current1.data == current2.data) {
                        Node next = current2.next;
                        if (current2.next == null) {
                            current2.prev.next = null;
                            current2.prev = null;
                        } else {
                            current2.prev.next = current2.next;
                            current2.next.prev = current2.prev;
                        }
     
                        current2 = next;
                    } else
                        current2 = current2.next;
                }
            }
        }
     
        public static void main(String[] args) {
            int[] linkedlistElements = new int[] { 1, 8, 5, 3, 5, 8, 4, 3 };
            int numberOfNodes = linkedlistElements.length;
            // initialising object of linkedlist class
            RemoveDuplicateDLLUnsorted dll = new RemoveDuplicateDLLUnsorted();
            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 <-> 8 <-> 5 <-> 3 <-> 5 <-> 8 <-> 4 <-> 3
Doubly Linked List after removing duplicates
1 <-> 8 <-> 5 <-> 3 <-> 4