Brahma Valley College of Engineering and Research Institute
Mini Project
Title: Design a mini project using JAVA which will use the different data
structure with or without Java collection library and show the use of
specific data structure on the efficiency (performance) of the code.
Objective:
• Understand and implement different data structures in Java.
• Use both custom implementations (e.g., linked list) and Java's built-in
collections (HashMap, TreeMap).
• Measure and compare performance in terms of insertion, search, and
deletion.
• Determine the most efficient data structure for managing contact
information.
Project Overview:
This mini project implements a Contact Management System that allows users
to add, search, delete, and view contacts. The primary objective of this project
is to explore and compare different data structures (Array, Linked List,
HashMap, and TreeMap) to observe how the choice of data structure affects
performance
Problem Statement:
In software systems where large volumes of data are managed, the efficiency of
core operations such as insertion, searching, and deletion greatly depends on
the choice of data structure. A common example is a Contact Management
Parik Yash Sachin
Brahma Valley College of Engineering and Research Institute
System, where quick access and management of user contact information is
essential.
This project aims to design and implement a Contact Management System
using various data structures—both from the Java Collections Framework
(e.g., HashMap, TreeMap) and custom-built structures (e.g., array, linked list)—
to evaluate how different structures affect performance.
By conducting a comparative analysis on the time complexity and actual
execution time of operations across these data structures, the project will help
in identifying the most suitable structure based on application needs, data size,
and performance requirements.
Functional Requirements:
• Add a contact (Name, Phone Number, Email)
• Search contact by name
• Delete contact by name
• Display all contacts
• Measure execution time for different operations
Theory:
The theory behind this project revolves around understanding and utilizing
different data structures to efficiently manage and access data. Below is an
explanation of the key concepts and principles relevant to the project:
1. Data Structures
Data structures are fundamental concepts in computer science used to
organize, manage, and store data efficiently for various operations such as
insertion, searching, deletion, and modification. Each data structure has
Parik Yash Sachin
Brahma Valley College of Engineering and Research Institute
different performance characteristics, and their efficiency varies based on the
use case. In this project, we focus on four primary data structures:
a. Array
An Array is a basic data structure that stores elements in a contiguous block of
memory. The elements are accessed using an index. Arrays are particularly
useful for storing a fixed collection of elements of the same type. However,
insertion and deletion operations can be slow, especially if the array size is
large, as elements may need to be shifted.
• Insertion: O(1) at the end, O(n) in the middle.
• Search: O(n) (linear search).
• Deletion: O(n) (linear deletion).
b. Linked List
A Linked List is a linear collection of elements, called nodes, where each node
contains data and a reference (or link) to the next node. Linked lists allow
efficient insertions and deletions at the beginning or middle of the list, but
searching for an element requires traversing through each node in sequence.
• Insertion: O(1) at the head/tail.
• Search: O(n) (linear search).
• Deletion: O(1) when the node is known.
c. HashMap
A HashMap is an implementation of a hash table where data is stored as key-
value pairs. This structure allows for fast access to values through keys by
computing a hash of the key. The average time complexity for insertion,
deletion, and search operations is O(1) due to direct indexing via hash
functions. However, in cases of hash collisions, the worst-case time complexity
can degrade to O(n).
• Insertion: O(1) on average.
• Search: O(1) on average.
• Deletion: O(1) on average.
Parik Yash Sachin
Brahma Valley College of Engineering and Research Institute
d. TreeMap
A TreeMap is a sorted map implementation based on a red-black tree (a type
of self-balancing binary search tree). TreeMap ensures that the keys are stored
in sorted order, making it efficient for operations that require ordering (e.g.,
range queries). Search, insertion, and deletion operations have a logarithmic
time complexity (O(log n)) due to the tree structure.
• Insertion: O(log n).
• Search: O(log n).
• Deletion: O(log n).
2. Time Complexity Analysis
Time complexity is a crucial concept in determining the efficiency of an
algorithm or data structure. It provides an estimate of the resources (time or
space) required for performing operations like insertion, searching, and
deletion based on the size of the data set (denoted as n). Below is a
comparison of time complexities for the key operations in different data
structures:
Operation Array Linked List HashMap TreeMap
Insertion O(n) O(1) O(1) O(log n)
Search O(n) O(n) O(1) O(log n)
Deletion O(n) O(1) O(1) O(log n)
• Array: Simple to implement but inefficient for large data sets, especially
for search and delete operations.
• Linked List: More dynamic than arrays, but searching is slower.
• HashMap: Highly efficient for lookups but does not maintain order.
• TreeMap: Provides efficient sorting and range queries but has a higher
overhead compared to HashMap for basic operations.
Parik Yash Sachin
Brahma Valley College of Engineering and Research Institute
3. Performance Evaluation
The efficiency of a data structure can be evaluated not just based on
theoretical time complexities, but also based on actual performance under
real-world conditions. In this project, we will implement the Contact
Management System using the four data structures and measure:
• Insertion Time: How long it takes to add new contacts.
• Search Time: How long it takes to find a contact by name.
• Deletion Time: How long it takes to remove a contact.
This practical performance evaluation will help demonstrate the difference
between theoretical expectations and real-world behavior.
4. Trade-offs Between Data Structures
• Array vs Linked List: Arrays are better for random access (direct
indexing) but inefficient for frequent insertions and deletions. Linked
lists are more flexible for insertions and deletions but slower for
searching.
• HashMap vs TreeMap: HashMap provides constant time lookup and
insertion, but it does not maintain any order. TreeMap, on the other
hand, maintains elements in sorted order at the cost of slightly slower
operations due to its tree structure.
5. Why Use Java Collections Framework?
The Java Collections Framework provides a set of interfaces, classes, and
algorithms that simplify the implementation and usage of common data
structures. The HashMap and TreeMap from the Collections Framework are
optimized and have been extensively tested in real-world applications.
Choosing them over custom implementations ensures more reliable
performance, especially for complex applications.
Parik Yash Sachin
Brahma Valley College of Engineering and Research Institute
Algorithm:
Array Implementation
a. Insertion Algorithm (Array)
1. Check if the array is full:
o If full, resize the array (double its size).
2. Add the new contact at the next available index (end of the array).
3. Update the size of the array to reflect the new insertion.
b. Search Algorithm (Array)
1. Start from the first element of the array (index 0).
2. Iterate through the array:
o Compare each element's contact name with the target name.
3. If a match is found, return the contact.
4. If no match is found, return null.
c. Deletion Algorithm (Array)
1. Find the contact to delete by searching for the name.
2. Shift all elements to the left from the deleted contact’s position to fill
the gap.
3. Decrease the array size and set the last element to null.
2. Linked List Implementation
a. Insertion Algorithm (Linked List)
1. Create a new node for the contact.
Parik Yash Sachin
Brahma Valley College of Engineering and Research Institute
2. Set the new node’s next pointer to point to the current head node (for
insertion at the head).
3. Update the head pointer to the new node.
4. If inserting at the end, traverse the list and update the last node's next
pointer.
b. Search Algorithm (Linked List)
1. Start from the head node of the linked list.
2. Traverse the list, comparing each node’s contact name with the target
name.
3. If a match is found, return the contact.
4. If no match is found, return null.
c. Deletion Algorithm (Linked List)
1. Start from the head node and traverse the list to find the contact.
2. Update the pointers:
o If the contact is the head, update the head pointer to the next
node.
o If the contact is in the middle or end, update the previous node’s
next pointer to bypass the current node.
3. Remove the node by properly updating the list structure.
3. HashMap Implementation
a. Insertion Algorithm (HashMap)
1. Create a key-value pair using the contact's name as the key and the
contact object as the value.
2. Insert the pair into the HashMap using the put() method.
Parik Yash Sachin
Brahma Valley College of Engineering and Research Institute
b. Search Algorithm (HashMap)
1. Use the contact’s name as the key.
2. Check if the key exists in the HashMap.
3. If the key exists, return the corresponding contact.
4. If the key does not exist, return null.
c. Deletion Algorithm (HashMap)
1. Identify the contact's name as the key.
2. Remove the contact from the HashMap using the remove() method.
4. TreeMap Implementation
a. Insertion Algorithm (TreeMap)
1. Create a key-value pair using the contact's name as the key and the
contact object as the value.
2. Insert the pair into the TreeMap using the put() method, which
maintains the order of keys.
b. Search Algorithm (TreeMap)
1. Use the contact’s name as the key to search in the TreeMap.
2. Check if the key exists in the TreeMap.
3. If the key exists, return the corresponding contact.
4. If the key does not exist, return null.
c. Deletion Algorithm (TreeMap)
1. Identify the contact's name as the key.
Parik Yash Sachin
Brahma Valley College of Engineering and Research Institute
2. Remove the contact from the TreeMap using the remove() method.
Flowchart:
Parik Yash Sachin
Brahma Valley College of Engineering and Research Institute
Conclusion:
This project demonstrated how different data structures—Array, Linked List,
HashMap, and TreeMap—affect the performance of a Contact Management
System. We found that:
• HashMap is the most efficient for fast lookups and updates.
• TreeMap is useful when sorted data is needed.
• Array and Linked List are simpler but slower for large datasets.
Choosing the right data structure greatly improves efficiency and system
performance.
Parik Yash Sachin
Brahma Valley College of Engineering and Research Institute
Code:
import [Link].*;
public class MiniDictionaryTest {
public static void main(String[] args) {
@SuppressWarnings("resource")
Scanner scanner = new Scanner([Link]);
[Link]("Enter number of words: ");
int n = [Link]([Link]());
String[] wordArray = new String[n];
List<String> wordList = new LinkedList<>();
HashMap<String, Boolean> wordMap = new HashMap<>();
[Link]("Enter " + n + " words:");
for (int i = 0; i < n; i++) {
String word = [Link]().toLowerCase();
wordArray[i] = word;
[Link](word);
[Link](word, true);
}
[Link]("Enter a word to search: ");
String searchWord = [Link]().toLowerCase();
long start, end;
start = [Link]();
boolean foundInArray = false;
for (String w : wordArray) {
if ([Link](searchWord)) {
foundInArray = true;
break;
}
}
end = [Link]();
long arrayTime = end - start;
Parik Yash Sachin
Brahma Valley College of Engineering and Research Institute
[Link]("Array Search: %8d ns (Found: %b)%n", arrayTime, foundInArray);
start = [Link]();
boolean foundInList = [Link](searchWord);
end = [Link]();
long listTime = end - start;
[Link]("LinkedList: %8d ns (Found: %b)%n", listTime, foundInList);
start = [Link]();
boolean foundInMap = [Link](searchWord);
end = [Link]();
long mapTime = end - start;
[Link]("HashMap: %8d ns (Found: %b)%n", mapTime, foundInMap);
long minTime = [Link](arrayTime, [Link](listTime, mapTime));
String fastest;
if (minTime == arrayTime) fastest = "Array";
else if (minTime == listTime) fastest = "LinkedList";
else fastest = "HashMap";
[Link]("\nFastest data structure for search: " + fastest);
}
}
Parik Yash Sachin
Brahma Valley College of Engineering and Research Institute
OutPut:
Parik Yash Sachin