Removing duplicates from an unsorted linked lis

Table of content

• Introduction
• Out Of Scope
• Removing Duplicates
• Project structure
• Technologies Used
• Prerequisities
• Commands
• Contribution
• References
• Contact Information

Introduction

In this project, we write a method to remove duplicates from an unsorted linked list.

For Example;

linkedList = 1->2->1->3
deleteDups(linkedList)
//Output
1->2->3

Out Of Scope

Since this is an beginner project in which the focus is just to learn some basic usages of an array, testing is out of scope of this project.

Removing Duplicates

We write a service called DuplicateNumberRemovalService which, when given an unsorted linked list, removes duplicate numbers from the input. For example:

removeDuplicates({1, 1, 2, 2, 3, 4, 5}) ---> Output : [1, 2, 3, 4, 5]

Let's have a look at this is done, shall we?

Initially, we call deleteDuplicates() which takes a linked list as input. Here,we define a HashSet and we start with the head of the linked list as the currentNode, previous node is set to null and we iterate through the linked list as long as current != null.

Inside the while loop, we get the value of the currentNode and check if the hashset contains the value already.

If yes, we set prev.next = current.next; and proceed further.

If the value does not exist in the hashset, we add it to the hashset and we set prev = current;

After both conditions, current node is always set to current.next.

The java code is as follows:

public void deleteDuplicates(LinkedList linkedList) {
	HashSet<Integer> hs = new HashSet<Integer>();
	Node current = linkedList.head;
	Node prev = null;
	while (current != null) {
		int currentValue = current.value;
		if (hs.contains(currentValue)) {
			// delete this node from the linked list
			prev.next = current.next;
			linkedList.size--;
		} else {
			hs.add(currentValue);
			prev = current;
		}
		current = current.next;
	}
}

Visual description of pseudo code

Project structure

There are in total three packages: one of which is the service which contain the solution inside a Service class. The other one is the base package which contains the infrastructure for creating a linked list, in this case a singly linked list. These service classes are instantiated and called from main() inside the Execute class which can be found inside com.umer.main package.

Technologies Used

• Java 11.

Prerequisities

None.

Commands

In order to run the program, one needs to open the project in a suitable IDE(such as Eclipse, STS, VSCode or IntelliJ), navigate to the Execute class inside com.umer.main package. Once there, right click---> Run As ---> Java Application.

The program is written in such a way that the service currently uses hard-coded values and it does not take any input from the user. However, one can go inside the main() inside Execute class and change the input parameters as one sees fit.

Contribution

Feature requests, issues, pull requests and questions are welcome.

References

• 1: Data Structures and Algorithms from Zero to Hero and Crack Top Companies 100+ Interview questions (Java Coding) (Udemy) (Primary resource)

Contact Information

How to reach me? At github specific gmail account.