Remove Duplicates from an Unsorted Linked List

Problem Statement

Write a program to delete duplicate nodes present in an unsorted linked list. Print the original linked list, and the linked list obtained after the deletions.

Example

Consider the following linked list :

1->2->3->2->2->4->1

After you remove duplicates from the linked list :

1->2->3->4

Example Explanation

The given unsorted linked list is :

1->2->3->2->2->4->1

There are multiple occurrences of elements 1 and 2 in the above-linked list. This means that the linked list contains duplicates of 1 and 2 which need to be removed.

After you remove duplicates from an unsorted linked list, the output will be :

1->2->3->4

Input/Output

Input :
The first line will contain the size of the linked list. The second line will contain the values of the nodes in the Linked List.

Output :
A Linked List with no duplicate values.

Constraints

1<=1<= size of linked lists <=106<=106
0<=0<= numbers in list <=104<=104

Algorithm : 1 – Brute Force Approach – Using Two Loops

Algorithm :

• Step – 1 :
  At the initial step a linked list is created using the append() function. If the Linked List is empty, then make a new node in the head, else add a new node after the last node.
• Step – 2 :
  Create a function remove_duplicates() that accepts one parameter – the head pointer of the linked list.
• Step – 3 :
  Initialize two variables: ptr1 and ptr2.
  • ptr1 is used to keep track of the element whose duplicates are being checked, and
  • ptr2 is used to track the node being checked to find duplicates.
• Step – 4 :
  Set ptr1 = head and ptr2 to null value.
• Step – 5 :
  Use while loop, and terminate the iteration when the value of ptr1 or ptr1->next becomes equal to null.
• Step – 6 :
  Set ptr2= ptr1.
• Step – 7 :
  A nested while loop is used to make another iteration which terminates when the value of ptr2->next is equal to null.
• Step – 8 :
  If the values of ptr1 and ptr2 are equal delete that node and incrementptr2->next to ptr2->next->next. If not equal, then increment ptr2 to its next node.
• Step – 9 :
  Increment ptr1 to its next node.
• Step – 10 :
  Finally, use the printLinkedList() function to print the original linked list and the linked list obtained after removing the duplicates.

Code Implementation

C++ :

/*Program to remove duplicates in an unsorted linked list*/
#include <bits/stdc++.h>
using namespace std;
/* A linked list node has a value and a pointer to the next node*/
class Node {
    public:
        int val;
        Node* next;
};
/* Function to create a new Node*/
Node* newNode(int new_val) {
    Node* temp = new Node;
    temp->val = new_val;
    temp->next = NULL;
    return temp;
}
/* Function to append a new node at the end. - Given a reference (pointer to
 * pointer) to the head of a list and an int */
void append(Node** head_ref, int new_val) {
    /* Create a new node */
    Node* new_node = new Node();
    Node* last = *head_ref;
    /* Insert the data */
    new_node->val = new_val;
    /* Make the text of this node NULL*/
    new_node->next = NULL;
    /* If the Linked List is empty, then make a new node as head*/
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
    /*  else traverse till the last node */
    while (last->next != NULL) {
        last = last->next;
    }
    /*  Change the next of last node */
    last->next = new_node;
    return;
}
/* Function to remove duplicates from linked list */
void remove_duplicates(Node* head) {
    Node *ptr1, *ptr2, *dup;
    ptr1 = head;
    /* Pick elements one by one */
    while (ptr1 != NULL && ptr1->next != NULL) {
        ptr2 = ptr1;
        /* Compare the picked element with the rest of the elements in the inner
         * loop. */
        while (ptr2->next != NULL) {
            /* If duplicate then delete it */
            if (ptr1->val == ptr2->next->val) {
                dup = ptr2->next;
                ptr2->next = ptr2->next->next;
                delete (dup);
            } else /* if not duplicate move to next node */
                ptr2 = ptr2->next;
        }
        ptr1 = ptr1->next;
    }
}
/* Function to print nodes in a given linked list */
void printLinkedList(Node* node) {
    while (node->next) {
        printf("%d -> ", node->val);
        node = node->next;
    }
    printf("%d ", node->val);
}

/* Driver code */
int main() {
    /* Start with the empty list */
    Node* head = NULL;
    int size = 8;
    
    int arr[8] = {1, 5, 8, 6, 1, 7, 5, 4};
    
    for (int i = 0; i < size; i++) {
        append(&head, arr[i]);
    }
    
    printf("Original Linked List:\n");
    printLinkedList(head);
    remove_duplicates(head);
    printf("\nLinked list after removing duplicates:\n");
    printLinkedList(head);
    return 0;
}

Java :

// Program to remove duplicates from an unsorted linked list
import java.io.*;
import java.util.Scanner;

class LinkedList {
  static Node head;

  static class Node {
    /* A linked list node has a value and a pointer to the next node */
    int val;
    Node next;

    Node(int new_val) {
      val = new_val;
      next = null;
    }
  }

  /* Function to append a new node at the end. */
  public void append(int new_data) {
    /* Create a new node*/
    Node new_node = new Node(new_data);
    /* If the Linked List is empty, then make a new node as head*/
    if (head == null) {
      head = new Node(new_data);
      return;
    }
    new_node.next = null;

    /*  else traverse till the last node */
    Node last = head;
    while (last.next != null) last = last.next;

    /* Change the next of last node */
    last.next = new_node;
    return;
  }

  /* Function to remove duplicates from linked list */
  static void remove_duplicates(Node head) {
    Node ptr2 = null;
    Node ptr1 = head;
    /* Pick elements one by one */
    while (ptr1 != null && ptr1.next != null) {
      ptr2 = ptr1;
      /* Compare the picked element with the rest of the elements in the
       * inner loop */
      while (ptr2.next != null) {
        /* If duplicate then delete it */
        if (ptr1.val == ptr2.next.val) {
          ptr2.next = ptr2.next.next;
        } /* if not duplicate move to next node */else {
          ptr2 = ptr2.next;
        }
      }
      ptr1 = ptr1.next;
    }
  }

  void printLinkedList(Node node) {
    while (node.next != null) {
      System.out.print(node.val + " -> ");
      node = node.next;
    }
    System.out.print(node.val);
  }
}

public class Main{
  public static void main(String[] args) {
    int size = 8;
    int[] arr = {1, 5, 8, 6, 1, 7, 5, 4};

    LinkedList linked_list = new LinkedList();
    for (int i = 0; i < size; i++) {
      linked_list.append(arr[i]);
    }
    System.out.println("Original Linked List:");
    linked_list.printLinkedList(LinkedList.head);
    linked_list.remove_duplicates(LinkedList.head);
    System.out.println("\nLinked List after removing duplicates:");
    linked_list.printLinkedList(LinkedList.head);
  }
}

Python :

class Node():
    def __init__(self, val):
        """
        A linked list node has a value and a pointer to the next node
        :type val: int
        """
        self.val = val
        self.next = None

class LinkedList():
    def __init__(self):
        # Head of the list
        self.head = None
    # Function to append a new node at the end.
    def append(self, new_val):
        # Create a new node, insert data, and set next as none
        new_node = Node(new_val)
        # If the Linked List is empty, then make a new node as head
        if self.head is None:
            self.head = new_node
            return
        # else traverse till the last node
        last = self.head
        while (last.next):
            last = last.next
        # Change the next of the last node
        last.next = new_node

    # Function to remove duplicates from the linked list
    def remove_duplicates(self, head):
        ptr1 = self.head
        ptr2 = None
        duplicate = None
         # Pick elements one by one
        while (ptr1 and ptr1.next):
            ptr2 = ptr1
            # Compare the picked element with the rest of the elements in the inner loop
            while (ptr2.next):
                # If duplicate then delete it
                if (ptr1.val == ptr2.next.val):
                    duplicate = ptr2.next
                    ptr2.next = ptr2.next.next
                #if not duplicate move to the next node
                else:
                    ptr2 = ptr2.next
            ptr1 = ptr1.next

    # Function to print nodes in a  given linked list
    def printLinkedList(self):
        temp = self.head
        while(temp.next):
            print(temp.val, end=" -> ")
            temp = temp.next
        print(temp.val)

# Driver code
if __name__ == '__main__':
    size= 8
    arr = [1, 5, 8, 6, 1, 7, 5, 4]
    linked_list = LinkedList()
    for i in range(size):
        linked_list.append(arr[i])
    print("Original Linked List:")
    linked_list.printLinkedList()
    linked_list.remove_duplicates(linked_list.head)
    print("Linked List after removing duplicates:")
    linked_list.printLinkedList()

Output :

Original Linked List:
1 -> 5 -> 8 -> 6 -> 1 -> 7 -> 5 -> 4
Linked List after removing duplicates:
1 -> 5 -> 8 -> 6 -> 7 -> 4

Complexity Analysis

Time Complexity :
In this approach to check and remove duplicates from an unsorted linked list a nested loop is used. Hence, the time complexity for this approach is O(n²).

Space complexity :
Since constant space is being used the space complexity for this approach will be O(1).

Algorithm : 2 – Optimized Approach – Using Hashing

Algorithm :

• Step – 1 :
  At the initial step a linked list is created using the append() function. If the Linked List is empty, then make a new node in the head, else add a new node after the last node.
• Step – 2 :
  Create a function remove_duplicates() that accepts one parameter – the head pointer of the linked list.
• Step – 3 :
  Create an unordered HashSet hash.
• Step – 4 :
  Initialize two variables: current and prev.
  • current is used to keep track of the element whose duplicates are being checked, and
  • prev is used to keep track of the previous node of the current.
• Step – 5 :
  Set current = head and prev = null.
• Step – 6 :
  Using the while loop makes an iteration that terminates when the value of current becomes null.
• Step – 7 :
  If the value assigned to the data of current is already in the hash map then assign the value of the next pointer of current to the next pointer of prev, else add the value of data in current to the map and make prev equal to current.
• Step – 9 :
  Assign the value of the next pointer of current to current.
• Step – 10 :
  In the final step using the printLinkedList() function print the original linked list and the linked list without duplicates.

Code Implementation

C++ :

/* Program to remove duplicates in an unsorted linked list */
#include <bits/stdc++.h>
using namespace std;
/* A linked list node has a value and a pointer to the next node*/
class Node {
    public:
	int val;
	Node* next;
};
/* Function to create a new Node*/
Node* newNode(int new_val){
    Node* temp = new Node;
    temp->val = new_val;
    temp->next = NULL;
    return temp;
}

/* Function to append a new node at the end. - Given a reference (pointer to pointer) to the head of a list and an int */
void append(Node** head_ref, int new_val){
    /* Create a new node */
    Node* new_node = new Node();
    Node *last = *head_ref;
    /* Insert the data */
    new_node->val = new_val;
    /* Make the text of this node NULL*/
    new_node->next = NULL;
    /* If the Linked List is empty, then make a new node as head*/
    if (*head_ref == NULL){
        *head_ref = new_node;
        return;
    }
    /*  else traverse till the last node */
    while (last->next != NULL){
        last = last->next;
    }
    /*  Change the next of last node */
    last->next = new_node;
    return;
}

/* Function to remove duplicates from linked list */
void remove_duplicates(Node* head){
    /* Hash to store visited values */
    unordered_set<int> hash;
    /* Pick elements one by one */
    struct Node* current = head;
    struct Node* prev = NULL;
    while (current != NULL) {
    	// If the current value is already visited
        if (hash.find(current->val) != hash.end()) {
            prev->next = current->next;
            delete (current);
        }
        // If the value is not present in hash
        else {
            hash.insert(current->val);
            prev = current;
        }
        current = prev->next;
    }
}

/* Function to print nodes in a given linked list */
void printLinkedList(Node* node){
    while (node->next) {
        printf("%d -> ", node->val);
        node = node->next;
    }
    printf("%d ", node->val);
}

/* Driver program*/
int main()
{
    Node* head = NULL;
    int size = 8;
    
    int arr[8] = {1, 5, 8, 6, 1, 7, 5, 4};
    
    for (int i = 0; i < size; i++) {
        append(&head, arr[i]);
    }
    printf("Original Linked List:\n");
    printLinkedList(head);
    remove_duplicates(head);
    printf("\nLinked list after removing duplicates:\n");
    printLinkedList(head);
    return 0;
}

Java :

// Program to remove duplicates from unsorted LinkedList
import java.io.*;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
  static Node head;

  static class Node {
    /* A linked list node has a value and a pointer to the next node */
    int val;
    Node next;

    Node(int new_val) {
      val = new_val;
      next = null;
    }
  }

  /* Function to append a new node at the end. */
  public void append(int new_data) {
    /* Create a new node*/
    Node new_node = new Node(new_data);
    /* If the Linked List is empty, then make a new node as head*/
    if (head == null) {
      head = new Node(new_data);
      return;
    }
    new_node.next = null;
    /*  else traverse till the last node */
    Node last = head;
    while (last.next != null) last = last.next;
    /* Change the next of last node */
    last.next = new_node;
    return;
  }

  /* Function to remove duplicates from unsorted linked list */
  static void remove_duplicates(Node head) {
    // Hash to store seen values
    HashSet<Integer> hash = new HashSet<>();
    /* Pick elements one by one */
    Node current = head;
    Node prev = null;
    while (current != null) {
      int curval = current.val;
      // If the current value is already visited
      if (hash.contains(curval)) {
        prev.next = current.next;
      }
      //If the current is absent in hash
      else {
        hash.add(curval);
        prev = current;
      }
      current = current.next;
    }
  }

  /* Function to print nodes in a given linked list */
  static void printLinkedList(Node node) {
    while (node.next != null) {
      System.out.print(node.val + " -> ");
      node = node.next;
    }
    System.out.print(node.val);
  }

  public static void main(String[] args) {
    int size = 8;
    int[] arr = {1, 5, 8, 6, 1, 7, 5, 4};
    Main linked_list = new Main();
    for (int i = 0; i < size; i++) {
      linked_list.append(arr[i]);
    }
    System.out.println("Original Linked List:");
    printLinkedList(head);
    remove_duplicates(head);
    System.out.println("\nLinked list after removing duplicates:");
    printLinkedList(head);
  }
}

Python :

class Node():
    def __init__(self, val):
        """
        A linked list node has a value and a pointer to the next node
        :type val: int
        """
        self.val = val
        self.next = None

class LinkedList():
    def __init__(self):
        # Head of the list
        self.head = None
    # Function to append a new node at the end.
    def append(self, new_val):
        # Create a new node, insert data, and set next as none
        new_node = Node(new_val)
        # If the Linked List is empty, then make a new node as head
        if self.head is None:
            self.head = new_node
            return
        # else traverse till the last node
        last = self.head
        while (last.next):
            last = last.next
        # Change the next of the last node
        last.next = new_node

    # Function to remove duplicates from the linked list
    def remove_duplicates(self, head):
        ptr1 = self.head
        ptr2 = None
        duplicate = None
         # Pick elements one by one
        while (ptr1 and ptr1.next):
            ptr2 = ptr1
            # Compare the picked element with the rest of the elements in the inner loop
            while (ptr2.next):
                # If duplicate then delete it
                if (ptr1.val == ptr2.next.val):
                    duplicate = ptr2.next
                    ptr2.next = ptr2.next.next
                #if not duplicate move to the next node
                else:
                    ptr2 = ptr2.next
            ptr1 = ptr1.next

    # Function to print nodes in a  given linked list
    def printLinkedList(self):
        temp = self.head
        while(temp.next):
            print(temp.val, end=" -> ")
            temp = temp.next
        print(temp.val)

# Driver code
if __name__ == '__main__':
    size= 8
    arr = [1, 5, 8, 6, 1, 7, 5, 4]
    linked_list = LinkedList()
    for i in range(size):
        linked_list.append(arr[i])
    print("Original Linked List:")
    linked_list.printLinkedList()
    linked_list.remove_duplicates(linked_list.head)
    print("Linked List after removing duplicates:")
    linked_list.printLinkedList()

Output :

Original Linked List:
1 -> 5 -> 8 -> 6 -> 1 -> 7 -> 5 -> 4
Linked List after removing duplicates:
1 -> 5 -> 8 -> 6 -> 7 -> 4

Complexity Analysis

Time Complexity :
To traverse the whole linked list of length ‘n’ and check for each node in the map the average time complexity is $O(n)$.
To access the hash table the time complexity is $O(1)$.
Taking both the above conditions into consideration, the overall time complexity is $O(n)$.

Space complexity :
Since a hash table is being used, whose size will be ‘n’ in the worst case (no duplicates), the overall space complexity is $O(n)$.

Conclusion

• A linked list is a linear data structure, which stores the elements at contiguous memory locations. The elements in a linked list are linked using pointers.
• Approach – 1 :
  Two loops are used to remove the duplicate elements, where the outer loop traverses through the linked list and picks an element and the inner loop checks for duplicates of the element picked. The duplicate elements found are removed from the list.
• Time Complexity : $O(n^2)$
• Space Complexity : $O(1)$
• Approach – 2 :
  To remove duplicates from an unsorted linked list the time complexity can be optimized using the concept of hashing. Here, if the node is already present in the hashmap, it indicates a duplicate of the already present node, and the duplicate node needs to be removed. The absence of a node refers to a newly encountered node that needs to be added to the map.
• Time Complexity : $O(n)$
• Space Complexity : $O(n)$

FAQ

Q. What is a Linked list ?

A. A linked list is a data structure which stores the elements at contiguous memory locations. The elements in a linked list are linked using pointers.

Q. What are the types of the Linked list ?

A. A linked list is of three types :

• Singly Linked List
• Doubly Linked List
• Circular Linked List.