Data Structures and Algorithms

UNIT-I
What is a Data Structure?

A data structure is a way of organizing and storing data in a computer so that it can be
accessed and used efficiently. It defines the relationship between the data and the operations
that can be performed on the data

Why are Data Structures Important?

Data structures are essential for the following reasons:

 Efficient Data Management: They enable efficient storage and retrieval of

data, reducing processing time and improving performance.
 Data Organization: They organize data in a logical manner, making it easier to
understand and access.
 Data Abstraction: They hide the implementation details of data storage,
allowing programmers to focus on the logical aspects of data manipulation.
 Reusability: Common data structures can be reused in multiple applications,
saving time and effort in development.
 Algorithm Optimization: The choice of the appropriate data structure can
significantly impact the efficiency of algorithms that operate on the data.

classification of types of Data Structures:

There are two types of Data Structures: -

1. Primitive Data Structures

2. Non-primitive Data Structures

1) Primitive Data Structures: Also known as primitive data types, these are basic built-in
data types in Java. They include:

o Byte: Stores whole numbers from -128 to 127.

o short: Stores whole numbers from -32,768 to 32,767.
o int: Stores whole numbers from -2,147,483,648 to 2,147,483,647.
o float: Stores floating-point numbers with single precision.
o char: Stores individual characters.
o boolean: Stores true or false values.
o long: Stores large whole numbers.
o Double: Stores floating-factor numbers with double precision.

2) Non-primitive Data Structures: Non-primitive records structures are more complex and
are composed of primitive information sorts. They may be, in addition, categorized into two
sorts:

1. Linear Data Structures: In linear data structures, the elements are arranged linearly
or sequentially. Examples include:
o Arrays: A group of identically-typed elements placed in an array according to
a predetermined arrangement.
o Stacks: A Last-In-First-Out (LIFO) structure in which only the topmost items
may be added or removed.
o Queues: First-In-First-Out (FIFO) structures are utilized in queues, where
items are inserted on the returned and taken out on the front.
o Linked List: A related list comprises a collection of gadgets referred to as
nodes, each of which has a reference to the node after it and statistics inside it.
2. Non-linear Data Structures: In non-linear data structures, the elements are arranged
in a non-sequential manner. Examples include:
o Trees: Trees are a type of node-based hierarchical structure, with a root node
at the top and child nodes branching out of it. Examples include red-black
trees, AVL trees, binary search trees, and binary trees.
 o Graphs: A set of nodes linked by using edges, wherein nodes may have any
quantity of connections. Graphs are used to symbolize complex relationships
among items.
o Heap: A specialized tree-based structure in which every determined node has
a value more or smaller than its kids, relying on whether or not it is a max
heap or a min heap.
o Hash: Data structures that use a hash function to map keys to values.
Examples consist of hash sets and hash maps, which provide green retrieval
and storage of statistics based on precise keys.

Advantages of Data Structures in Java

1. Efficient Data Organization: Data structures provide organized ways to store and
manage data, allowing for efficient Access, manipulation, and retrieval operations.
They optimize memory usage and facilitate faster execution of algorithms.
2. Better Performance: Developers can improve performance in terms of speed and
memory utilization by selecting the suitable data structure for a particular activity.
Performance is optimized because specific data structures are made to excel at
particular actions like searching, sorting, or inserting information.
3. Code reusability: Java offers a wide range of built-in data structures that are simple
for programmers to use. These reusable data structures save time and effort by
removing the need to create sophisticated algorithms from scratch.
4. Code Simplicity: Data structures make the implementation of complicated processes
simpler to code. They offer high-level abstractions and encapsulate the specifics of
data management, which improves the code's readability, maintainability, and clarity.
5. Flexibility and Adaptability: Data structures offer flexibility in handling different
types and sizes of data. They can dynamically adjust to accommodate changing data
requirements and provide mechanisms for efficient data manipulation.
6. Standardized and Well-Tested: The standard library for Java contains built-in data
structures that have undergone significant testing and optimization, guaranteeing their
dependability and performance. Utilizing these common data structures lowers the
possibility of errors and gives application development a solid foundation.
7. Scalability: Data structures provide scalability options, allowing applications to
handle large volumes of data efficiently. They can dynamically grow or shrink based
on the data size, ensuring optimal performance even with increasing data demands.
 8. Algorithm Design: Data structures are crucial in algorithm design and analysis. They
provide the underlying structure and operations necessary for implementing various
algorithms and solving complex problems.

1. Arrays

An Array is a data structure used to collect multiple data elements of the same data type into
one variable. Instead of storing multiple values of the same data types in separate variable
names, we could store all of them together into one variable.

An Array is a list of elements where each element has a unique place in the list. The data
elements of the array share the same variable name; however, each carries a different index
number called a subscript. We can access any data element from the list with the help of its
location in the list. Thus, the key feature of the arrays to understand is that the data is stored
in contiguous memory locations, making it possible for the users to traverse through the data
elements of the array using their respective indexes.

Arrays can be classified into different types:

a. One-Dimensional Array: An Array with only one row of data elements is known as
a One-Dimensional Array. It is stored in ascending storage location.

b. Two-Dimensional Array: An Array consisting of multiple rows and columns of data

elements is called a Two-Dimensional Array. It is also known as a Matrix.

c. Multidimensional Array: We can define Multidimensional Array as an Array of

Arrays. Multidimensional Arrays are not bounded to two indices or two dimensions as
they can include as many indices are per the need.

Functions:
 1. Creating an Array: Declare and initialize an array with a specific size using the
array type and the new keyword.
2. Accessing Elements: Use the index to access individual elements in the array.
3. Modifying Elements: Update the value of an element by assigning a new value to a
specific index in the array.
4. Finding Length: Use the length attribute to determine the array's length.
5. Iterating through the Array: Use loops to go through each element in the array and
execute

Advantages:

1. Data Organization: Arrays provide a structured way to store and organize elements,
improving data management.
2. Random Access: Elements can be accessed directly using their index, allowing for
efficient retrieval and modification.
3. Fixed Size: Arrays have a predetermined size, enabling efficient memory allocation.
4. Homogeneous Elements: Arrays store elements of the same type, ensuring data
consistency and simplifying operations.
5. Iteration: Arrays support easy iteration through elements, facilitating traversal and
processing.
6. Sorting and Searching: Arrays work well with sorting and searching algorithms,
offering efficient operations.
7. Memory Efficiency: Arrays optimize memory usage by storing elements in
contiguous regions.
8. Compatibility: Arrays are widely supported in Java, making them compatible with
various frameworks and tools.

Disadvantages:

1. Fixed Size: Arrays cannot be dynamically resized, requiring recreation for size
changes.
2. Memory Wastage: Unused elements in larger arrays can lead to memory wastage.
3. Insertion and Deletion Overhead: Inserting or deleting elements in the middle of an
array requires shifting subsequent elements, resulting in inefficiency.
4. Lack of Flexibility: Arrays have rigid data types and cannot accommodate different
data kinds without additional arrays or data structures.
Example: Access Array Elements

class Main {
public static void main(String[] args) {
// create an array
int[] age = {12, 4, 5, 2, 5};
// access each array elements
System.out.println("Accessing Elements of Array:");
System.out.println("First Element: " + age[0]);
System.out.println("Second Element: " + age[1]);
System.out.println("Third Element: " + age[2]);
System.out.println("Fourth Element: " + age[3]);
System.out.println("Fifth Element: " + age[4]);
}
}
Accessing Elements of Array:
First Element: 12
Second Element: 4
Third Element: 5
Fourth Element: 2
Fifth Element: 5

Looping Through Array Elements:

Example: Using for Loop:

class Main {
public static void main(String[] args) {
// create an array
int[] age = {12, 4, 5};
 System.out.println("Using for Loop:");
for(int i = 0; i < age.length; i++) {
System.out.println(age[i]);
}
}
}

Output:
Using for Loop:
12
4
5

Example: Using for-each loop

class Main {
public static void main(String[] args) {

// create an array
int[] age = {12, 4, 5};

// loop through the array

// using for loop
System.out.println("Using for-each Loop:");
for(int a : age) {
System.out.println(a);
}
}
}

Output:
Using for-each Loop:
12
4
5

Example: Calculate SUM and AVERAGE :

class Main {
public static void main(String[] args) {
int[] numbers = {2, -9, 0, 5, 12, -25, 22, 9, 8, 12};
int sum = 0;
Double average;
// access all elements using for each loop
// add each element in sum
 for (int number: numbers) {
sum += number;
}
// get the total number of elements
int arrayLength = numbers.length;
// convert the average from int to double
average = ((double)sum / (double)arrayLength);

System.out.println("Sum = " + sum);

System.out.println("Average = " + average);
}
}

Outpiut:

Sum = 36
Average = 3.6

Linear Search Algorithm

Searching is the process of finding some particular element in the list. If the element
is present in the list, then the process is called successful, and the process returns the
location of that element; otherwise, the search is called unsuccessful.

Two popular search methods are Linear Search and Binary Search. So, here we will
discuss the popular searching technique, i.e., Linear Search Algorithm.

Linear search is also called as sequential search algorithm. It is the simplest

searching algorithm. In Linear search, we simply traverse the list completely and
match each element of the list with the item whose location is to be found. If the
match is found, then the location of the item is returned; otherwise, the algorithm
returns NULL.

Algorithm:
Working of Linear search
Now, let's see the working of the linear search Algorithm.

To understand the working of linear search algorithm, let's take an unsorted array. It
will be easy to understand the working of linear search with an example.

Let the elements of array are -

Let the element to be searched is K = 41

Now, start from the first element and compare K with each element of the array.

The value of K, i.e., 41, is not matched with the first element of the array. So, move to
the next element. And follow the same process until the respective element is found.
Implementation of Linear Search:
Binary Search Algorithm
Binary search is the search technique that works efficiently on sorted lists. Hence, to
search an element into some list using the binary search technique, we must ensure
that the list is sorted.

Binary search follows the divide and conquer approach in which the list is divided
into two halves, and the item is compared with the middle element of the list. If the
match is found then, the location of the middle element is returned. Otherwise, we
search into either of the halves depending upon the result produced through the
match.

Working of Binary search

Now, let's see the working of the Binary Search Algorithm.

To understand the working of the Binary search algorithm, let's take a sorted array. It
will be easy to understand the working of Binary search with an example.

There are two methods to implement the binary search algorithm -

o Iterative method
o Recursive method

The recursive method of binary search follows the divide and conquer approach.

Let the elements of array are -

Let the element to search is, K = 56

We have to use the below formula to calculate the mid of the array -

So, in the given array -

beg = 0

end = 8

mid = (0 + 8)/2 = 4. So, 4 is the mid of the array.

Now, the element to search is found. So algorithm will return the index of the
element matched.

Implementation of Binary Search

Now, let's see the programs of Binary search in different programming languages.

Program: Write a program to implement Binary search in Java language.

Bubble sort Algorithm
Bubble sort works on the repeatedly swapping of adjacent elements until they are not in the
intended order. It is called bubble sort because the movement of array elements is just like
the movement of air bubbles in the water. Bubbles in water rise up to the surface; similarly,
the array elements in bubble sort move to the end in each iteration.
Algorithm
In the algorithm given below, suppose arr is an array of n elements. The
assumed swap function in the algorithm will swap the values of given array elements.

Working of Bubble sort Algorithm

Now, let's see the working of Bubble sort Algorithm.

To understand the working of bubble sort algorithm, let's take an unsorted array. We
are taking a short and accurate array, as we know the complexity of bubble sort
is O(n2).

Let the elements of array are -

First Pass
Sorting will start from the initial two elements. Let compare them to check which is
greater.

Here, 32 is greater than 13 (32 > 13), so it is already sorted. Now, compare 32 with
26.
Here, 26 is smaller than 36. So, swapping is required. After swapping new array will
look like -

Now, compare 32 and 35.

Here, 35 is greater than 32. So, there is no swapping required as they are already
sorted.

Now, the comparison will be in between 35 and 10.

Here, 10 is smaller than 35 that are not sorted. So, swapping is required. Now, we
reach at the end of the array. After first pass, the array will be -

Now, move to the second iteration.

Second Pass
The same process will be followed for second iteration.

Here, 10 is smaller than 32. So, swapping is required. After swapping, the array will be
-
Now, move to the third iteration.

Third Pass
The same process will be followed for third iteration.

Here, 10 is smaller than 26. So, swapping is required. After swapping, the array will be
-

Now, move to the fourth iteration.

Fourth pass
Similarly, after the fourth iteration, the array will be -

Hence, there is no swapping required, so the array is completely sorted.

Implementation of Bubble sort

Selection Sort Algorithm
In selection sort, the smallest value among the unsorted elements of the array is
selected in every pass and inserted to its appropriate position into the array. It is also
the simplest algorithm. It is an in-place comparison sorting algorithm. In this
algorithm, the array is divided into two parts, first is sorted part, and another one is
the unsorted part. Initially, the sorted part of the array is empty, and unsorted part is
the given array. Sorted part is placed at the left, while the unsorted part is placed at
the right.

In selection sort, the first smallest element is selected from the unsorted array and
placed at the first position. After that second smallest element is selected and placed
in the second position. The process continues until the array is entirely sorted.

Selection sort is generally used when -

o A small array is to be sorted

o Swapping cost doesn't matter
o It is compulsory to check all elements

Algorithm
Working of Selection sort Algorithm
Now, let's see the working of the Selection sort Algorithm.

To understand the working of the Selection sort algorithm, let's take an unsorted
array. It will be easier to understand the Selection sort via an example.

Let the elements of array are -

Now, for the first position in the sorted array, the entire array is to be scanned
sequentially.

At present, 12 is stored at the first position, after searching the entire array, it is
found that 8 is the smallest value.

So, swap 12 with 8. After the first iteration, 8 will appear at the first position in the
sorted array.
For the second position, where 29 is stored presently, we again sequentially scan the
rest of the items of unsorted array. After scanning, we find that 12 is the second
lowest element in the array that should be appeared at second position.

Now, swap 29 with 12. After the second iteration, 12 will appear at the second
position in the sorted array. So, after two iterations, the two smallest values are
placed at the beginning in a sorted way.

The same process is applied to the rest of the array elements. Now, we are showing a
pictorial representation of the entire sorting process.

Now, the array is completely sorted.

Program: Write a program to implement selection sort in Java.

Insertion Sort Algorithm
Insertion sort works similar to the sorting of playing cards in hands. It is assumed
that the first card is already sorted in the card game, and then we select an unsorted
card. If the selected unsorted card is greater than the first card, it will be placed at
the right side; otherwise, it will be placed at the left side. Similarly, all unsorted cards
are taken and put in their exact place.

The same approach is applied in insertion sort. The idea behind the insertion sort is
that first take one element, iterate it through the sorted array.
Insertion sort has various advantages such as –

o Simple implementation
o Efficient for small data sets
o Adaptive, i.e., it is appropriate for data sets that are already substantially
sorted.

Now, let's see the algorithm of insertion sort.

Algorithm
The simple steps of achieving the insertion sort are listed as follows -

Step 1 - If the element is the first element, assume that it is already sorted. Return 1.

Step2 - Pick the next element, and store it separately in a key.

Step3 - Now, compare the key with all elements in the sorted array.

Step 4 - If the element in the sorted array is smaller than the current element, then
move to the next element. Else, shift greater elements in the array towards the right.

Step 5 - Insert the value.

Step 6 - Repeat until the array is sorted.

Working of Insertion sort Algorithm

Now, let's see the working of the insertion sort Algorithm.

To understand the working of the insertion sort algorithm, let's take an unsorted
array. It will be easier to understand the insertion sort via an example.

Let the elements of array are -

Initially, the first two elements are compared in insertion sort.

Here, 31 is greater than 12. That means both elements are already in ascending
order. So, for now, 12 is stored in a sorted sub-array.

Now, move to the next two elements and compare them.

Here, 25 is smaller than 31. So, 31 is not at correct position. Now, swap 31 with 25.
Along with swapping, insertion sort will also check it with all elements in the sorted
array.

For now, the sorted array has only one element, i.e. 12. So, 25 is greater than 12.
Hence, the sorted array remains sorted after swapping.

Now, two elements in the sorted array are 12 and 25. Move forward to the next
elements that are 31 and 8.

Both 31 and 8 are not sorted. So, swap them.

After swapping, elements 25 and 8 are unsorted.

So, swap them.

Now, elements 12 and 8 are unsorted.

So, swap them too.

Now, the sorted array has three items that are 8, 12 and 25. Move to the next items
that are 31 and 32.

Hence, they are already sorted. Now, the sorted array includes 8, 12, 25 and 31.

Move to the next elements that are 32 and 17.

17 is smaller than 32. So, swap them.

Swapping makes 31 and 17 unsorted. So, swap them too.

Now, swapping makes 25 and 17 unsorted. So, perform swapping again.

Now, the array is completely sorted.

Implementation of insertion sort

Quick Sort Algorithm

This algorithm follows the divide and conquer approach. Divide and conquer is a
technique of breaking down the algorithms into subproblems, then solving the
subproblems, and combining the results back together to solve the original problem.

Divide: In Divide, first pick a pivot element. After that, partition or rearrange the
array into two sub-arrays such that each element in the left sub-array is less than or
equal to the pivot element and each element in the right sub-array is larger than the
pivot element.

Conquer: Recursively, sort two subarrays with Quicksort.

Combine: Combine the already sorted array.

Quicksort picks an element as pivot, and then it partitions the given array around the
picked pivot element. In quick sort, a large array is divided into two arrays in which
one holds values that are smaller than the specified value (Pivot), and another array
holds the values that are greater than the pivot.

After that, left and right sub-arrays are also partitioned using the same approach. It
will continue until the single element remains in the sub-array.

Algorithm
Partition Algorithm:
The partition algorithm rearranges the sub-arrays in a place.

Working of Quick Sort Algorithm

Now, let's see the working of the Quicksort Algorithm.

To understand the working of quick sort, let's take an unsorted array. It will make the
concept more clear and understandable.

Let the elements of array are -

In the given array, we consider the leftmost element as pivot. So, in this case, a[left] =
24, a[right] = 27 and a[pivot] = 24.
Since, pivot is at left, so algorithm starts from right and move towards left.

Now, a[pivot] < a[right], so algorithm moves forward one position towards left, i.e. -

Now, a[left] = 24, a[right] = 19, and a[pivot] = 24.

Because, a[pivot] > a[right], so, algorithm will swap a[pivot] with a[right], and pivot
moves to right, as -

Now, a[left] = 19, a[right] = 24, and a[pivot] = 24. Since, pivot is at right, so algorithm
starts from left and moves to right.

As a[pivot] > a[left], so algorithm moves one position to right as -

Now, a[left] = 9, a[right] = 24, and a[pivot] = 24. As a[pivot] > a[left], so algorithm
moves one position to right as -
Now, a[left] = 29, a[right] = 24, and a[pivot] = 24. As a[pivot] < a[left], so, swap
a[pivot] and a[left], now pivot is at left, i.e. -

Since, pivot is at left, so algorithm starts from right, and move to left. Now, a[left] =
24, a[right] = 29, and a[pivot] = 24. As a[pivot] < a[right], so algorithm moves one
position to left, as -

Now, a[pivot] = 24, a[left] = 24, and a[right] = 14. As a[pivot] > a[right], so, swap
a[pivot] and a[right], now pivot is at right, i.e. -

Now, a[pivot] = 24, a[left] = 14, and a[right] = 24. Pivot is at right, so the algorithm
starts from left and move to right.
Now, a[pivot] = 24, a[left] = 24, and a[right] = 24. So, pivot, left and right are
pointing the same element. It represents the termination of procedure.

Element 24, which is the pivot element is placed at its exact position.

Elements that are right side of element 24 are greater than it, and the elements that
are left side of element 24 are smaller than it.

Now, in a similar manner, quick sort algorithm is separately applied to the left and
right sub-arrays. After sorting gets done, the array will be -

Implementation of quicksort
Program: Write a program to implement quicksort in Java.
Output
Merge Sort Algorithm

Merge sort is similar to the quick sort algorithm as it uses the divide and conquer
approach to sort the elements. It is one of the most popular and efficient sorting
algorithm. It divides the given list into two equal halves, calls itself for the two halves
and then merges the two sorted halves. We have to define the merge() function to
perform the merging.

The sub-lists are divided again and again into halves until the list cannot be divided
further. Then we combine the pair of one element lists into two-element lists, sorting
them in the process. The sorted two-element pairs is merged into the four-element
lists, and so on until we get the sorted list.

Now, let's see the algorithm of merge sort.

Algorithm
In the following algorithm, arr is the given array, beg is the starting element, and end is the
last element of the array.

The important part of the merge sort is the MERGE function. This function performs
the merging of two sorted sub-arrays that are A[beg…mid] and A[mid+1…end], to
build one sorted array A[beg…end]. So, the inputs of the MERGE function are A[],
beg, mid, and end.

The implementation of the MERGE function is given as follows -

Working of Merge sort Algorithm
Now, let's see the working of merge sort Algorithm.

To understand the working of the merge sort algorithm, let's take an unsorted array. It will be
easier to understand the merge sort via an example.

Let the elements of array are -

According to the merge sort, first divide the given array into two equal halves. Merge sort
keeps dividing the list into equal parts until it cannot be further divided.

As there are eight elements in the given array, so it is divided into two arrays of size 4.

Now, again divide these two arrays into halves. As they are of size 4, so divide them into new
arrays of size 2.

Now, again divide these arrays to get the atomic value that cannot be further divided.

Now, combine them in the same manner they were broken.

In combining, first compare the element of each array and then combine them into another
array in sorted order.

So, first compare 12 and 31, both are in sorted positions. Then compare 25 and 8, and in the
list of two values, put 8 first followed by 25. Then compare 32 and 17, sort them and put 17
first followed by 32. After that, compare 40 and 42, and place them sequentially.

In the next iteration of combining, now compare the arrays with two data values and merge
them into an array of found values in sorted order.
Now, there is a final merging of the arrays. After the final merging of above arrays, the array
will look like -

Now, the array is completely sorted.

Implementation of merge sort

Program: Write a program to implement merge sort in Java.
Output: