How to remove duplicate(s) from linked list in Java? Example Tutorial

Hello guys, if you are wondering how to find duplicates in a given linked list in Java then you have come to the right place. In the past, I have explained how to reverse a linked list in Java, find kth element from tail in linked list, find cycle on linked list, and in this article, I will show you how to find duplicate nodes in a given linked list. This is one of the classic linked list coding problem and I have also included this in my list of 30 common linked list problems for programmers. You can further check that list to practice more linked list programs and improve your understanding of linked lists and how to solve those problems. But, before we get into details of finding and printing duplicate nodes from the given linked list let's start with the basics. 

What is a Linked list data structure?

A linked list is a special kind of list data structure that holds a list of node, where each node not only contains value which you store in this data structure but also a reference to the next node (value). What do I mean? Imagine this scenario:

John and Lizzy are Husband and Wife, A visitor came looking for john, the husband. The visitor does not need to struggle with how to find john. All he /she needs to do is to see Lizzy because there is 100 percent assurance that Lizzy would definitely know where john, her husband is.

So, in Java or any other programming language that is how exactly it is. A linked list is a data structure in which each node(element) holds the reference to the next node. You don’t need to go through the struggle of searching the exact node in the link list, all you have to do is go through the previous node because it holds the reference to the next node, then you can easily access it.

This architecture offers several advantages compared to array, another primitive data structure which you can use to store values. Unlike array which needs contiguous memory location, In linked list, values can be stored across the memory location, which result in better memory utilization. 

In fact, linked list can use all the memory islands which are not usable by array because they are not big enough to create a big array. This kind of comparative knowledge and difference between linked list and array data structure is key for success in both Computer Science exams as well as during real world programming and during technical interview. 

Given in a list of numbers in a linked list:

Fig 1.0, Numbers in the linked list data structure.

In the figure above, you could see how the linked list was pictured, we have a list of numbers, the first node is 100 and as you would see it has access to the next node 200 likewise node 200 has access to the next node to it, and on, and on, and on.

Data can be stored and removed in the list link dynamically, if there is no next then the previous would be holding a null reference, meaning that, there is no data next to it, and that shows to us that data 400 is the last in the list

A linked list is appropriate to use when the number of data elements to be represented in the data structure is unpredictable.

So, since Linked lists are dynamic, their length can increase or decrease as necessary, unlike Array which is a fixed data structure. You must specify the length of the data it would take from the point you created it. I believe by now you have a good understanding of how linked list operates.

So, right now would be solving the task of removing duplicates from a linked list.

Java Program to remove duplicate nodes from a linked list - Example

Note: I used nested class here, You can have a separate Java file for the Node  class that was embedded here, just ensure they are in the same package where they can see themselves.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

public class DuplicateRemovalInLinkedList { //Represent a node of the singly linked list static class Node{ int data; Node next; public Node(int data) { this.data = data; this.next = null; } } //Represent the head and tail of the singly linked list static Node head = null; static Node tail = null; //addNode() will add a new node to the list public static void addNode(int data) { //Create a new node Node newNode = new Node(data); //Checks if the list is empty if(head == null) { //If list is empty, both head and tail will point to new node head = newNode; } else //If list is empty, both head and tail will point to new node tail.next = newNode; //newNode will become new tail of the list } tail = newNode; } //removeDuplicate() will remove duplicate nodes from the list public static void removeDuplicate() { //Node current will point to head Node current = head, index = null, temp = null; if(head == null) { return; } else { while(current != null){ //Node temp will point to previous node to index. temp = current; //Index will point to node next to current index = current.next; while(index != null) { //If current node's data is equal to index node's data if(current.data == index.data) { //Here, index node is pointing to the node which is duplicate of current node //Skips the duplicate node by pointing to next node temp.next = index.next; } else { //Temp will point to previous node of index. temp = index; } index = index.next; } current = current.next; } } } //display() will display all the nodes present in the list public static void display() { //Node current will point to head Node current = head; if(head == null) { System.out.println("List is empty"); return; } while(current != null) { //Prints each node by incrementing pointer System.out.print(current.data + " "); current = current.next; } System.out.println(); } public static void main(String[] args) { //Adds data to the list addNode(11); addNode(12); addNode(31); addNode(12); addNode(31); addNode(4); addNode(11); System.out.println("Originals list: "); display(); removeDuplicate(); System.out.println("List after removing duplicates: "); display(); } }

The class was declared in line 1 with the name "DuplicateRemovalInLinkedList". There is another class embedded in it of type node. The Node class has two instance variables, data and next. data is of type int and next is of type node. line 6 is the constructor all through line 9. 

The closing brace in line 10 closes the node class. Now in the other class node head and node tail were initialized to null in line 12 and line 13 respectively. In line 15, a method was created, it is a void method-"addNode()". 

This method enables us to add nodes to the linked list. it takes data as a parameter of type int. Line 17 creates a new node as an instance, that takes in data. line 19 means that if the head is null i.e if the list is empty, both head and tail should point to the new node that was just created. but, if the head has something inside already new node should become the new tail of the list. 

Anytime this method is called, it means you want to add data to the node regardless of how many times you called it. Now, let us move to the second method. Line 31 is the method that removes duplicates that return void. variables were created in line 33, which are current, index, and temp. 

They are all of the type "node". From line 34, if the head has nothing inside, it should return nothing. but if it does, and the current is not empty then Node temp should point to the previous node to the index which is the current node. 

And the index would point to the node next to the current. In line 43, while the index is not empty and if the current node's data is equal to the index node's data, that's a duplicate already so it skips it by pointing to the next node. 

But if that is not the case, line 50 runs downward. which means that temp would point to the previous node of the index. the index still points to its next in line 54 and the same thing with line 56. The display method happens in line 61. 

Node current points to the head and if the head is empty in line 64 it prints "List is empty" in the following line. In line 68 while the current is not empty, each node is printed as it increments the pointer. as it prints out the current data, the current is been assigned to the next data.

The main method was declared in line 75. data were been added from lines 77 to 83. The display method was called in line 85 to see what we have in the list first. then after that, the method that removes duplicates was called in line 86, the display method was called again in line 88 to see what we have in the list. by this time all the duplicates have been removed.

Here, is what we have below:

Original list:

11 12 31 12 31 4 11

List after removing duplicates:

11 12 31 4

That's all about how to find and remove a duplicate node from a given linked list in Java. This is one of the popular and difficult coding problems to solve hence you should practice it before going for interviews. Don't try to mug the solution, instead try to solve it on your own. You can also try to find the time and space complexity of this problem.  Interviewers often asked this as follow-up questions. I leave that to you find for exercise but if you get stuck, feel free to ask in the comments. 

Other Programming Articles you may like

• How to check if a given number is prime or not? (solution)
• How to print factorial of a given number in Java? (factorial)
• How to find if the given String is a palindrome in Java? (solution)
• 15 Recursion exercise for Java Programmers (recursion)
• How to reverse an int variable in Java? (solution)
• 10 Dynamic Programming problems for interviews (dynamic programming)
• How to find a missing number in a sorted array? (solution)
• 75 Programming Questions for Interviews (questions)
• 10 Free Courses to learn Java Programming (free courses)
• Write a program to check if a number is a power of two or not? (solution)
• How to reverse String in Java without using StringBuffer? (solution)
• 100+ Data Structure and Algorithms problems for interviews (questions)
• 10 Free Courses to learn Data Structure and Algorithms (free courses)
• How do you reverse the word of a sentence in Java? (solution)
• How do you swap two integers without using a temporary variable? (solution)

Thanks, for reading this article so far, if you like this linked list coding problem, solution, and my explanation then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note. 

P. S. - If you are new to Java Programming and looking for a free online course to learn Java from scratch then I highly recommend you to check out Java Tutorial for Complete Beginners(FREE) course on Udemy. It's completely free and more than 1 million students have already joined this course.