DATA STRUCTURE GROUP PRESENTATION

NASAAZI TAKIA 2200706674 22/U/6674

AKANKWASA WILLIAM 2200702914 22/U/2914/PS
BWIRE IVAN 1600703908 16/U/3908

ARRAYS AND DESIGN STRATEGIES

Algorithm to create an array
1)Create Array Method (createIntArray):
Declare a method named createIntArray that takes an integer parameter size.
Inside the method, declare an array newArray of integers with the specified size.
Use a for loop to initialize the array elements. In this example, the values are set to
increment from 1 to the specified size.
private static int[] createIntArray(int size) {
int[] newArray = new int[size];
for (int i = 0; i < size; i++) {
newArray[i] = i + 1;
}
return newArray;
}
2)Print Array Method (printArray):
Declare a helper method named printArray that takes an array of integers as a parameter.
Use a for loop to iterate through the elements of the array and print each element along
with its index.
private static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.println("Element at index " + i + ": " + arr[i]);
}
}
3)Main Method:
In the main method, call createIntArray to create an array of integers with a specified size.

1
 DATA STRUCTURE GROUP PRESENTATION

Print the elements of the created array using the printArray method.
public static void main(String[] args) {
int[] numbers = createIntArray(5);
System.out.println("Array Elements:");
printArray(numbers);
}

Implementation of the algorithm to create an array

public class CreateArray {
public static void main(String[] args) {
// Method 1: Declare and Initialize in a Single Line
int[] numbers1 = {1, 2, 3, 4, 5};

// Method 2: Declare and Initialize in Two Steps

int[] numbers2;
numbers2 = new int[]{6, 7, 8, 9, 10};

// Method 3: Declare and Initialize an Empty Array

int[] numbers3 = new int[5]; // Creates an array of size 5 with default values (0 for
integers)

// Print the elements of each array

System.out.println("Array 1 Elements:");
printArray(numbers1);

System.out.println("\nArray 2 Elements:");
printArray(numbers2);

System.out.println("\nArray 3 Elements:");

2
 DATA STRUCTURE GROUP PRESENTATION

printArray(numbers3);
}

// Helper method to print the elements of an array

private static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.println("Element at index " + i + ": " + arr[i]);
}
}
}
Algorithm to destruct an array
1)Initialize an Array:
Declare an array myArray and assign values to it: {1, 2, 3, 4, 5}.
int[] myArray = {1, 2, 3, 4, 5};
2)Output the Original Array:
Print the original array using Arrays.toString().
System.out.println("Original array: " + Arrays.toString(myArray));
3)Destructure the Array:
"Destructure" the array by assigning a new empty array to the original array variable.
myArray = new int[0];
4)Output the Destructured Array:
Print the "destructured" array using Arrays.toString().
System.out.println("Destructured array: " + Arrays.toString(myArray));
Implementation of the algorithm to destruct an array
import java.util.Arrays;

public class ArrayDestruction {

public static void main(String[] args) {
// Declare an array

3
 DATA STRUCTURE GROUP PRESENTATION

int[] myArray = {1, 2, 3, 4, 5};

// Output the original array

System.out.println("Original array: " + Arrays.toString(myArray));

// "Destructure" the array by assigning a new empty array

myArray = new int[0];

// Output the "destructured" array

System.out.println("Destructured array: " + Arrays.toString(myArray));
}
}

Algorithm to update an array

Algorithm UpdateArray(arr: array, index: integer, newValue: any):
// Check if the index is within the valid range of the array
If index < 0 OR index >= arr.length Then
Print "Index out of bounds"
Return
End If

// Update the value at the specified index

arr[index] = newValue
End Algorithm
Implementation of the algorithm
public class UpdateArrayElement {
public static void main(String[] args) {

4
 DATA STRUCTURE GROUP PRESENTATION

// Declare an array
int[] myArray = {1, 2, 3, 4, 5};

// Update the third element (index 2) to a new value

myArray[2] = 10;

// Output the updated array

for (int element : myArray) {
System.out.print(element + " ");
}
}
}
Algorithm to insert in an array
1)Input:

• An array array of size n (original array).

• An element element to be inserted.
2)Create a new array:

• Create a new array newArray of size n + 1.

3)Copy elements:

• Copy all elements from the original array array to the new array newArray up to the
index n - 1.
4)Insert the new element:

• Insert the new element element at the last index of the new array newArray (at index
n).
5)Output:

• The new array newArray is the modified array with the inserted element at the end.

Implementation of the algorithm insert into an array

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

5
 DATA STRUCTURE GROUP PRESENTATION

// Example array
int[] array = {1, 2, 3, 4, 5};

// Element to insert
int elementToInsert = 6;

// Insert element at the end of the array

array = insertAtEnd(array, elementToInsert);

// Print the modified array

System.out.print("Modified Array: ");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}

static int[] insertAtEnd(int[] array, int element) {

// Create a new array with increased size
int[] newArray = new int[array.length + 1];

// Copy elements from the original array to the new array

for (int i = 0; i < array.length; i++) {
newArray[i] = array[i];
}

// Insert the new element at the end

newArray[newArray.length - 1] = element;

return newArray;

6
 DATA STRUCTURE GROUP PRESENTATION

}
}

Algorithm to delete an element in an array

1)Input:

• An array array containing integers.

• An element elementToDelete that needs to be deleted from the array.
2)Find the index to delete:

• Iterate through the array to find the index of the element to delete
(elementToDelete).
3)Shift elements to fill the gap:

• If the element is found, shift all elements to the left, starting from the index after the
element to delete, effectively overwriting the element to be deleted.
4)Create a new array:

• Create a new array newArray with a size one less than the original array.
5)Copy elements to the new array:

• Copy elements from the modified array (after shifting) to the new array.
6)Output:

• The array newArray is the modified array with the specified element deleted.

Implementation of the algorithm to delete an element in an array

public class DeleteElementFromArray {
public static void main(String[] args) {
// Example array
int[] array = {1, 2, 3, 4, 5};

// Element to delete
int elementToDelete = 3;

7
 DATA STRUCTURE GROUP PRESENTATION

// Delete the element from the array

array = deleteElementFromArray(array, elementToDelete);

// Print the modified array

System.out.print("Modified Array: ");
for (int value : array) {
System.out.print(value + " ");
}
}

static int[] deleteElementFromArray(int[] array, int element) {

int indexToDelete = -1;

// Find the index of the element to delete

for (int i = 0; i < array.length; i++) {
if (array[i] == element) {
indexToDelete = i;
break;
}
}

// If the element is found, delete it

if (indexToDelete != -1) {
// Create a new array with reduced size
int[] newArray = new int[array.length - 1];

// Copy elements before and after the element to delete

System.arraycopy(array, 0, newArray, 0, indexToDelete);

8
 DATA STRUCTURE GROUP PRESENTATION

System.arraycopy(array, indexToDelete + 1, newArray, indexToDelete, array.length -

indexToDelete - 1);

return newArray;
} else {
// If the element is not found, return the original array
return array;
}
}
}
Algorithm to merge arrays
1)Input:

• Two arrays array1 and array2 that need to be merged.

2)Calculate merged array length:

• Calculate the length of the merged array by adding the lengths of array1 and array2.
3)Create a new array:

• Create a new array mergedArray with a length equal to the sum of the lengths of
array1 and array2.
4)Copy elements from array1 to mergedArray:

• Use System.arraycopy to copy elements from array1 to mergedArray starting from

the beginning of mergedArray.
5)Copy elements from array2 to mergedArray:

• Use System.arraycopy again to copy elements from array2 to mergedArray, starting

from the index after the elements of array1.
6)Output:

• The array mergedArray is the result of merging array1 and array2.

Implementation of the algorithm to merge arrays

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

9
 DATA STRUCTURE GROUP PRESENTATION

// Example arrays
int[] array1 = {1, 2, 3};
int[] array2 = {4, 5, 6};

// Merge arrays
int[] mergedArray = mergeArrays(array1, array2);

// Print the merged array

System.out.print("Merged Array: ");
for (int value : mergedArray) {
System.out.print(value + " ");
}
}

static int[] mergeArrays(int[] array1, int[] array2) {

// Calculate the length of the merged array
int mergedLength = array1.length + array2.length;

// Create a new array for the merged elements

int[] mergedArray = new int[mergedLength];

// Copy elements from array1 to the merged array

System.arraycopy(array1, 0, mergedArray, 0, array1.length);

// Copy elements from array2 to the merged array

System.arraycopy(array2, 0, mergedArray, array1.length, array2.length);

return mergedArray;
}

10
 DATA STRUCTURE GROUP PRESENTATION

Algorithm to traverse an array

1)Initialize the Array:

• Declare an array of integers named array and assign values to it: {1, 2, 3, 4, 5}.
int[] array = {1, 2, 3, 4, 5};
2)Traverse the Array:

• Use a for loop to iterate through the elements of the array.

• The loop variable i is initialized to 0, and the loop continues as long as i is less than
the length of the array (array.length).
In each iteration, print the element at the current index (i) along with the index.
for (int i = 0; i < array.length; i++) {
System.out.println("Element at index " + i + ": " + array[i]);
}
3)Print the Array Elements:

• Display a header indicating that the following output represents the elements of the
array.
System.out.println("Array Elements:");
4)Print Each Element:

• Inside the loop, print each element along with its corresponding index.
System.out.println("Element at index " + i + ": " + array[i]);
The algorithm traverses the array from the first element to the last, printing each element
along with its index.

Implementation of the algorithm to traverse an array

public class ArrayTraversal {
public static void main(String[] args) {
// Example array
int[] array = {1, 2, 3, 4, 5};

11
 DATA STRUCTURE GROUP PRESENTATION

// Traverse the array and print each element

System.out.println("Array Elements:");
for (int i = 0; i < array.length; i++) {
System.out.println("Element at index " + i + ": " + array[i]);
}
}
}

Algorithm to bubble sort an array

Class BubbleSort:

Function bubbleSort(array):
size = length(array)

// loop to access each array element

for i from 0 to size - 2:
swapped = false

// loop to compare adjacent elements

for j from 0 to size - i - 2:

// compare two array elements

if array[j] > array[j + 1]:

// swapping occurs if elements

// are not in the intended order
swap(array[j], array[j + 1])
swapped = true

12
 DATA STRUCTURE GROUP PRESENTATION

// no swapping means the array is already sorted

// so no need for further comparison
if not swapped:
break

Function swap(a, b):

temp = a
a=b
b = temp

Function main():
// initialize array
data = [-2, 45, 0, 11, -9]

// call the bubbleSort method using the class name

BubbleSort.bubbleSort(data)

// print the sorted array

print("Sorted Array in Ascending Order:")
print(arrayToString(data))
Implementation of the algorithm to bubble an array
// Optimized Bubble sort in Java

import java.util.Arrays;

class Bubble{

// perform the bubble sort

static void bubbleSort(int array[]) {

13
 DATA STRUCTURE GROUP PRESENTATION

int size = array.length;

// loop to access each array element

for (int i = 0; i < (size-1); i++) {

// check if swapping occurs

boolean swapped = false;

// loop to compare adjacent elements

for (int j = 0; j < (size-i-1); j++) {

// compare two array elements

// change > to < to sort in descending order
if (array[j] > array[j + 1]) {

// swapping occurs if elements

// are not in the intended order
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;

swapped = true;
}
}
// no swapping means the array is already sorted
// so no need for further comparison
if (!swapped)
break;

14
 DATA STRUCTURE GROUP PRESENTATION

}
}

public static void main(String args[]) {

int[] data = { -2, 45, 0, 11, -9 };

// call method using the class name

Bubble.bubbleSort(data);

System.out.println("Sorted Array in Ascending Order:");

System.out.println(Arrays.toString(data));
}
}

Algorithm to quick sort an array

Class QuickSort:

Function partition(array, low, high):

// choose the rightmost element as pivot
pivot = array[high]

// pointer for greater element

i = low - 1

// traverse through all elements

// compare each element with pivot
for j from low to high - 1:

15
 DATA STRUCTURE GROUP PRESENTATION

if array[j] <= pivot:

// if element smaller than pivot is found

// swap it with the greater element pointed by i
i++

// swapping element at i with element at j

swap(array[i], array[j])

// swap the pivot element with the greater element specified by i

swap(array[i + 1], array[high])

// return the position from where partition is done

return i + 1

Function quickSort(array, low, high):

if low < high:

// find pivot element such that

// elements smaller than pivot are on the left
// elements greater than pivot are on the right
pi = partition(array, low, high)

// recursive call on the left of pivot

quickSort(array, low, pi - 1)

// recursive call on the right of pivot

quickSort(array, pi + 1, high)

16
 DATA STRUCTURE GROUP PRESENTATION

Class Main:

Function main():
// initialize array
data = [8, 7, 2, 1, 0, 9, 6]
print("Unsorted Array")
print(arrayToString(data))

size = length(data)

// call quickSort() on array data

QuickSort.quickSort(data, 0, size - 1)

print("Sorted Array in Ascending Order")

print(arrayToString(data))
Implementation of the algorithm to quick sort an array
import java.util.Arrays;

class QuickSort {

// method to find the partition position

static int partition(int array[], int low, int high) {

// choose the rightmost element as pivot

int pivot = array[high];

// pointer for greater element

int i = (low - 1);

17
 DATA STRUCTURE GROUP PRESENTATION

// traverse through all elements

// compare each element with pivot
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {

// if element smaller than pivot is found

// swap it with the greater element pointed by i
i++;

// swapping element at i with element at j

int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

// swapt the pivot element with the greater element specified by i

int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;

// return the position from where partition is done

return (i + 1);
}

static void quickSort(int array[], int low, int high) {

if (low < high) {

18
 DATA STRUCTURE GROUP PRESENTATION

// find pivot element such that

// elements smaller than pivot are on the left
// elements greater than pivot are on the right
int pi = partition(array, low, high);

// recursive call on the left of pivot

quickSort(array, low, pi - 1);

// recursive call on the right of pivot

quickSort(array, pi + 1, high);
}
}
}

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

int[] data = { 8, 7, 2, 1, 0, 9, 6 };
System.out.println("Unsorted Array");
System.out.println(Arrays.toString(data));

int size = data.length;

// call quicksort() on array data

QuickSort.quickSort(data, 0, size - 1);

System.out.println("Sorted Array in Ascending Order ");

System.out.println(Arrays.toString(data));

19
 DATA STRUCTURE GROUP PRESENTATION

}
}

Algorithm for selection sort of an array

Algorithm SelectionSort(arr):
Input: An array arr of n elements

1. Set n to the length of arr.

2. Iterate i over the range from 0 to n-2 (inclusive):
a. Set min_idx to i.
b. Iterate j over the range from i+1 to n-1 (inclusive):
i. If arr[j] is less than arr[min_idx], set min_idx to j.
c. Swap arr[i] with arr[min_idx].

3. Output the sorted array arr.

Algorithm printArray(arr):
Input: An array arr

1. Set n to the length of arr.

2. Iterate i over the range from 0 to n-1 (inclusive):
a. Print arr[i] followed by a space.
3. Print a newline.

Algorithm main():
1. Create a SelectionSort object ob.
2. Create an array arr with elements {64, 25, 12, 22, 11}.
3. Call ob.sort(arr) to sort the array using Selection Sort.

20
 DATA STRUCTURE GROUP PRESENTATION

4. Print "Sorted array".

5. Call ob.printArray(arr) to print the sorted array.
Implementation of the algorithm for selection sort of an array
public class SelectionSort
{
void sort(int arr[])
{
int n = arr.length;

// One by one move boundary of unsorted subarray

for (int i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;

// Swap the found minimum element with the first

// element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}

// Prints the array

void printArray(int arr[])
{

21
 DATA STRUCTURE GROUP PRESENTATION

int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}

// Driver code to test above

public static void main(String args[])
{
SelectionSort ob = new SelectionSort();
int arr[] = {64,25,12,22,11};
ob.sort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
}

Algorithm to shell sort an array.

procedure shellSort(arr):
n = length(arr)

// Start with a large gap and reduce it with each iteration

for gap = n / 2 to 1:
// Perform Insertion Sort for the elements at the current gap
for i = gap to n - 1:
temp = arr[i]
j=i

22
 DATA STRUCTURE GROUP PRESENTATION

// Move elements that are greater than temp to the right

while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j = j - gap

// Place temp in its correct position

arr[j] = temp

// Example usage:
arr = [12, 34, 54, 2, 3]
shellSort(arr)
Implementation of the algorithm to shell sort an array
public class ShellSort {
public static void main(String[] args) {
int[] array = {12, 34, 54, 2, 3};

System.out.println("Original Array:");
printArray(array);

shellSort(array);

System.out.println("\nSorted Array:");
printArray(array);
}

// Shell Sort implementation

static void shellSort(int[] array) {
int n = array.length;

23
 DATA STRUCTURE GROUP PRESENTATION

// Start with a large gap and reduce it with each iteration

for (int gap = n / 2; gap > 0; gap /= 2) {
// Perform Insertion Sort for the elements at the current gap
for (int i = gap; i < n; i++) {
int temp = array[i];
int j;

// Move elements that are greater than temp to the right

for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
array[j] = array[j - gap];
}

// Place temp in its correct position

array[j] = temp;
}
}
}

// Utility method to print an array

static void printArray(int[] array) {
for (int value : array) {
System.out.print(value + " ");
}
System.out.println();
}
}

Sequential search Algorithm of an array

24
 DATA STRUCTURE GROUP PRESENTATION

procedure sequentialSearch(array, target):

for i = 0 to length(array) - 1:
if array[i] == target:
return i // Element found, return its index
return -1 // Element not found in the array

// Example usage:
array = [4, 2, 7, 1, 9, 5, 6, 8, 3]
target = 5
result = sequentialSearch(array, target)

if result != -1:
print("Element", target, "found at index", result)
else:
print("Element", target, "not found in the array")
Implementation of the sequential search algorithm of an array
public class SequentialSearch {
public static void main(String[] args) {
int[] array = {4, 2, 7, 1, 9, 5, 6, 8, 3};
int target = 5;

int result = sequentialSearch(array, target);

if (result != -1) {
System.out.println("Element " + target + " found at index " + result);
} else {
System.out.println("Element " + target + " not found in the array");
}
}

25
 DATA STRUCTURE GROUP PRESENTATION

// Sequential Search implementation

static int sequentialSearch(int[] array, int target) {
for (int i = 0; i < array.length; i++) {
if (array[i] == target) {
return i; // Element found, return its index
}
}
return -1; // Element not found in the array
}
}
Binary search Algorithm of an array
1) Initialize low and high pointers to the start and end of the array.
2) Use a while loop to repeatedly narrow down the search range by adjusting low and
high.
3) Calculate the middle index mid of the current range.
4) Check if the element at index mid is equal to the target element.
5) If the target element is found, return the index mid.
6) If the element at index mid is less than the target, discard the left half by updating
low.
7) If the element at index mid is greater than the target, discard the right half by
updating high.
8) Repeat steps 3-7 until low is greater than high.
9) If the loop completes without finding a match, return -1 to indicate that the target
element is not present in the array.
10) Top of Form

procedure binarySearch(array, target):

low = 0
high = length(array) - 1

while low <= high:

mid = low + (high - low) / 2

26
 DATA STRUCTURE GROUP PRESENTATION

if array[mid] == target:
return mid // Element found, return its index
else if array[mid] < target:
low = mid + 1 // Discard the left half
else:
high = mid - 1 // Discard the right half

return -1 // Element not found in the array

// Example usage:
sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
result = binarySearch(sortedArray, target)

if result != -1:
print("Element", target, "found at index", result)
else:
print("Element", target, "not found in the array")
Implementation of the Binary search algorithm of an array
public class BinarySearch {
public static void main(String[] args) {
int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int target = 5;

int result = binarySearch(sortedArray, target);

if (result != -1) {
System.out.println("Element " + target + " found at index " + result);
} else {

27
 DATA STRUCTURE GROUP PRESENTATION

System.out.println("Element " + target + " not found in the array");

}
}

// Binary Search implementation

static int binarySearch(int[] array, int target) {
int low = 0;
int high = array.length - 1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (array[mid] == target) {
return mid; // Element found, return its index
} else if (array[mid] < target) {
low = mid + 1; // Discard the left half
} else {
high = mid - 1; // Discard the right half
}
}

return -1; // Element not found in the array

}
}

Interpolation search Algorithm of an array

1)Input: Sorted array array, target element target

28
 DATA STRUCTURE GROUP PRESENTATION

2)Initialize: Set low to 0 (the beginning of the array) and high to array.length - 1 (the end of
the array).
3)While loop: While low is less than or equal to high and the target is within the range of
elements from array[low] to array[high]:
a. Calculate the estimated position pos using the interpolation formula: pos = low + ((target
- array[low]) * (high - low)) / (array[high] - array[low])
b. If array[pos] is equal to the target: - Return pos as the index of the target element.
c. If array[pos] is less than the target: - Adjust the search range to the right: set low to pos +
1.
d. If array[pos] is greater than the target: - Adjust the search range to the left: set high to
pos - 1.
4)Return -1: If the loop completes without finding a match, return -1 to indicate that the
target element is not present in the array.

Implementation of the Interpolation search algorithm of an array

public class InterpolationSearch {
public static void main(String[] args) {
int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int target = 5;

int result = interpolationSearch(sortedArray, target);

if (result != -1) {
System.out.println("Element " + target + " found at index " + result);
} else {
System.out.println("Element " + target + " not found in the array");
}
}

// Interpolation Search implementation

static int interpolationSearch(int[] array, int target) {

29
 DATA STRUCTURE GROUP PRESENTATION

int low = 0;
int high = array.length - 1;

while (low <= high && target >= array[low] && target <= array[high]) {
int pos = low + ((target - array[low]) * (high - low)) / (array[high] - array[low]);

if (array[pos] == target) {
return pos; // Element found, return its index
} else if (array[pos] < target) {
low = pos + 1; // Adjust the search range to the right
} else {
high = pos - 1; // Adjust the search range to the left
}
}

return -1; // Element not found in the array

}
}

DATA DESIGN STRATEGIES

BINARY SEARCH USING DIVIDE AND CONQUER
1)Initialize:
Set low to the index of the first element in the array (usually 0).
Set high to the index of the last element in the array.
2)Divide:
Calculate the middle index as mid = (low + high) / 2.
3)Conquer:
If the middle element is equal to the target, return the index.

30
 DATA STRUCTURE GROUP PRESENTATION

If the target is less than the middle element, repeat the search in the left half (high = mid -
1).
If the target is greater than the middle element, repeat the search in the right half (low =
mid + 1).
4)Base Case:
If low is greater than high, the target is not in the array; return -1.
5)Recursion:
Recursively repeat steps 2-4 on the selected half until the base case is reached.
PSEUDOCODE
function binarySearch(array, target, low, high):
if low <= high:
mid = (low + high) / 2

if array[mid] == target:
return mid
else if array[mid] > target:
return binarySearch(array, target, low, mid - 1)
else:
return binarySearch(array, target, mid + 1, high)
else:
return -1
ITS IMPLEMENTATION
public class DivideAndConquer {

// Binary Search implementation using divide and conquer

public static int binarySearch(int[] array, int target) {
return binarySearch(array, target, 0, array.length - 1);
}

private static int binarySearch(int[] array, int target, int low, int high) {

31
 DATA STRUCTURE GROUP PRESENTATION

if (low <= high) {

int mid = (low + high) / 2;

// Check if the target is present at the middle

if (array[mid] == target) {
return mid;
}

// If the target is smaller than the middle element,

// then it can only be present in the left subarray
if (array[mid] > target) {
return binarySearch(array, target, low, mid - 1);
}

// Otherwise, the target can only be present in the right subarray

return binarySearch(array, target, mid + 1, high);
}

// If the target is not present in the array

return -1;
}

public static void main(String[] args) {

int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int target = 7;

int result = binarySearch(array, target);

if (result != -1) {

32
 DATA STRUCTURE GROUP PRESENTATION

System.out.println("Element found at index " + result);

} else {
System.out.println("Element not found in the array");
}
}
}
GREEDY ALGORITHM
Coin Change Problem Algorithm:
Sort the coins array in non-ascending order:

• Ensure that the coins are sorted in decreasing order.

Initialize a variable to represent the number of coins used (coinCount):

• This variable will be used to count the number of coins needed to make change for
the given amount.
Iterate through each coin in the sorted coins array:

• While the amount is greater than or equal to the current coin:

• Use the current coin to make change.
• Update the amount by subtracting the coin value.
• Increment the count of coins used (coinCount).
Return the count of coins used (coinCount).
IMPLEMENTATION
import java.util.Arrays;

public class GreedyCoinChange {

public static int greedyCoinChange(int amount, int[] coins) {

// Sort coins in non-ascending order
Arrays.sort(coins);
reverseArray(coins);

int coinCount = 0;

33
 DATA STRUCTURE GROUP PRESENTATION

// Use greedy approach to make change

for (int coin : coins) {
while (amount >= coin) {
// Use the coin
amount -= coin;
coinCount++;
}
}

return coinCount;
}

// Helper function to reverse an array in-place

private static void reverseArray(int[] arr) {
int start = 0;
int end = arr.length - 1;

while (start < end) {

// Swap elements at start and end indices
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;

// Move indices towards the center

start++;
end--;
}
}

34
 DATA STRUCTURE GROUP PRESENTATION

public static void main(String[] args) {

// Example usage
int amount = 63;
int[] coins = {25, 10, 5, 1};

int result = greedyCoinChange(amount, coins);

System.out.println("Minimum number of coins needed: " + result);

}
}
DYNAMIC PROGRAMMING
Fibonacci memorization algorithm
1)Input:
n: The index of the Fibonacci number to be calculated.
2)Base Case:
If n is less than or equal to 1, return n because the Fibonacci sequence for indices 0 and 1 is
0 and 1, respectively.
3)Memoization Check:
Check if the result for Fibonacci number at index n is already memoized in the HashMap
(memo).
If yes, return the memoized result.
4)Recursive Calculation:
If the result is not memoized, calculate the Fibonacci number for index n by recursively
calling the fibonacci function for indices n - 1 and n - 2.
Add the results of these recursive calls to get the Fibonacci number at index n.
5)Memoization:
Memoize the result by storing it in the memo HashMap with the key n.
6)Return Result:
Return the calculated Fibonacci number.

35
 DATA STRUCTURE GROUP PRESENTATION

Implementation of the Fibonacci memoization algorithm

import java.util.HashMap;

public class FibonacciMemoization {

public static void main(String[] args) {
int n = 10;
System.out.println("Fibonacci(" + n + "): " + fibonacci(n, new HashMap<>()));
}

// Fibonacci function using memoization

private static int fibonacci(int n, HashMap<Integer, Integer> memo) {
if (n <= 1) {
return n;
}

// Check if the result is already memoized

if (memo.containsKey(n)) {
return memo.get(n);
}

// Calculate and memoize the result

int result = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
memo.put(n, result);
return result;
}
}
Fibonacci tabulation algorithm
1)Input:
n: The index of the Fibonacci number to be calculated.

36
 DATA STRUCTURE GROUP PRESENTATION

2)Initialize Table:
Create an array fib of size n + 1 to store intermediate results of Fibonacci numbers.
Initialize fib[0] to 0 (the 0th Fibonacci number) and fib[1] to 1 (the 1st Fibonacci number).
3)Tabulation Loop:
Use a loop to iteratively calculate Fibonacci numbers from index 2 to n.
For each index i, set fib[i] to the sum of the two preceding Fibonacci numbers, fib[i - 1] and
fib[i - 2].
4)Result:
After the loop, fib[n] contains the Fibonacci number at index n, which is the result.
5)Return Result:
Return the calculated Fibonacci number fib[n].
Implementation of the Fibonacci tabulation algorithm
public class FibonacciTabulation {
public static void main(String[] args) {
int n = 10;
System.out.println("Fibonacci(" + n + "): " + fibonacci(n));
}

// Fibonacci function using tabulation

private static int fibonacci(int n) {
int[] fib = new int[n + 1];
fib[0] = 0;
fib[1] = 1;

for (int i = 2; i <= n; i++) {

fib[i] = fib[i - 1] + fib[i - 2];
}

return fib[n];

37
 DATA STRUCTURE GROUP PRESENTATION

}
}
Backtracking algorithm to solve Hamiltonian circuit problem
function HamiltonianCircuit(graph):
vertices = number of vertices in graph
path = array of size vertices filled with -1
path[0] = 0 // Start from the first vertex

if hamiltonianCircuitUtil(graph, path, 1):

printSolution(path)
else:
print("No Hamiltonian circuit exists")

function hamiltonianCircuitUtil(graph, path, position):

if position == number of vertices:
// Check if the last vertex is connected to the starting vertex
return graph[path[position - 1]][path[0]] == 1

for each vertex v from 1 to number of vertices - 1:

if isSafe(v, graph, path, position):
path[position] = v

if hamiltonianCircuitUtil(graph, path, position + 1):

return true

path[position] = -1 // Backtrack

return false

38
 DATA STRUCTURE GROUP PRESENTATION

function isSafe(v, graph, path, position):

// Check if the vertex can be added to the Hamiltonian circuit
if graph[path[position - 1]][v] == 0:
return false

for i from 0 to position - 1:

if path[i] == v:
return false // Vertex is already in the path

return true

function printSolution(path):
print("Hamiltonian Circuit:")
for i from 0 to number of vertices - 1:
print(path[i] + " ")
print(path[0]) // Print the starting vertex again to complete the circuit
Implementation of the backtracking algorithm
import java.util.Arrays;

public class HamiltonianCircuit {

private int[][] graph;
private int[] path;
private int vertices;

public HamiltonianCircuit(int[][] graph) {

this.graph = graph;
this.vertices = graph.length;
this.path = new int[vertices];
Arrays.fill(path, -1);

39
 DATA STRUCTURE GROUP PRESENTATION

public void solveHamiltonianCircuit() {

path[0] = 0; // Start from the first vertex

if (hamiltonianCircuitUtil(1)) {
printSolution();
} else {
System.out.println("No Hamiltonian circuit exists");
}
}

private boolean hamiltonianCircuitUtil(int position) {

if (position == vertices) {
// Check if the last vertex is connected to the starting vertex
return graph[path[position - 1]][path[0]] == 1;
}

for (int v = 1; v < vertices; v++) {

if (isSafe(v, position)) {
path[position] = v;

if (hamiltonianCircuitUtil(position + 1)) {
return true;
}

path[position] = -1; // Backtrack

}
}

40
 DATA STRUCTURE GROUP PRESENTATION

return false;
}

private boolean isSafe(int v, int pos) {

// Check if the vertex can be added to the Hamiltonian circuit
if (graph[path[pos - 1]][v] == 0) {
return false;
}

for (int i = 0; i < pos; i++) {

if (path[i] == v) {
return false; // Vertex is already in the path
}
}

return true;
}

private void printSolution() {

System.out.println("Hamiltonian Circuit:");
for (int i = 0; i < vertices; i++) {
System.out.print(path[i] + " ");
}
System.out.println(path[0]); // Print the starting vertex again to complete the circuit
}

public static void main(String[] args) {

int[][] graph = {

41
 DATA STRUCTURE GROUP PRESENTATION

{0, 1, 1, 1, 0},
{1, 0, 1, 0, 1},
{1, 1, 0, 1, 1},
{1, 0, 1, 0, 0},
{0, 1, 1, 0, 0}
};

HamiltonianCircuit hamiltonianCircuit = new HamiltonianCircuit(graph);

hamiltonianCircuit.solveHamiltonianCircuit();
}
}
Branch and bound algorithm
1)Define the Node Structure:
Create a Node structure with fields for the current level, accumulated profit, accumulated
weight, and the bound (estimated maximum possible profit).
2)Define the bound Function:
Implement a function bound(level, weight, profit, values, weights, capacity) that calculates
the bound for a given partial solution. The bound represents the maximum possible profit
that can be obtained from the remaining items.
3)Initialize Variables:
Initialize a priority queue to explore nodes based on their bounds. Start with the root node
representing an empty solution.
4)Branch and Bound Loop:
While the priority queue is not empty:
Pop a node from the priority queue.
If the bound of the node is greater than the current best solution:
Explore adding the next item to the knapsack:
Calculate the new weight, profit, and bound.
Update the current best solution if a better solution is found.
Add the new node to the priority queue.

42
 DATA STRUCTURE GROUP PRESENTATION

Explore not adding the next item to the knapsack:

Add a node with the same weight, profit, and bound to the priority queue.
5)Return the Result:
Once the priority queue is empty, return the maximum profit found.
Implementation of the branch and bound algorithm
import java.util.Arrays;
import java.util.PriorityQueue;

class Node implements Comparable<Node> {

int level;
int profit;
int weight;
double bound;

public Node(int level, int profit, int weight, double bound) {

this.level = level;
this.profit = profit;
this.weight = weight;
this.bound = bound;
}

@Override
public int compareTo(Node other) {
return Double.compare(other.bound, this.bound);
}
}

public class KnapsackBranchAndBound {

43
 DATA STRUCTURE GROUP PRESENTATION

private static double bound(int level, int weight, int profit, int[] values, int[] weights, int
capacity) {
if (weight >= capacity) {
return 0; // Cannot add more weight
}

double bound = profit;

int i = level + 1;
int totalWeight = weight;

while (i < values.length && totalWeight + weights[i] <= capacity) {

totalWeight += weights[i];
bound += values[i];
i++;
}

if (i < values.length) {
bound += (capacity - totalWeight) * ((double) values[i] / weights[i]);
}

return bound;
}

public static int knapsackBranchAndBound(int[] values, int[] weights, int capacity) {

int n = values.length;

Node rootNode = new Node(-1, 0, 0, 0);

PriorityQueue<Node> priorityQueue = new PriorityQueue<>();

44
 DATA STRUCTURE GROUP PRESENTATION

priorityQueue.add(rootNode);

int maxProfit = 0;

while (!priorityQueue.isEmpty()) {
Node node = priorityQueue.poll();

if (node.bound > maxProfit) {

int level = node.level + 1;
int weight = node.weight + weights[level];
int profit = node.profit + values[level];

if (weight <= capacity && profit > maxProfit) {

maxProfit = profit;
}

double bound = bound(level, weight, profit, values, weights, capacity);

if (bound > maxProfit) {

priorityQueue.add(new Node(level, profit, weight, bound));
}

priorityQueue.add(new Node(level, node.profit, node.weight, bound));

}
}

return maxProfit;
}

45
 DATA STRUCTURE GROUP PRESENTATION

public static void main(String[] args) {

int[] values = {60, 100, 120};
int[] weights = {10, 20, 30};
int capacity = 50;

int result = knapsackBranchAndBound(values, weights, capacity);

System.out.println("Maximum profit: " + result);
}
}
SINGLE LINKEDLIST

public class Student {

private StudentNode head;

private static class StudentNode {

private String name;
private StudentNode next;

public StudentNode(String name) {

this.name = name;
this.next = null;
}
}
Algorithm For Traverse
Method()
Current=head
While(current !=null)
Yield current.name

46
 DATA STRUCTURE GROUP PRESENTATION

Implementation For Traverse

public void traverseAndPrint() {
StudentNode current = head;
while (current != null) {
System.out.println(current.name);
current = current.next;
}
}
Implementation For insertAtBeginning
public void insertAtBeginning(String name) {
StudentNode newNode = new StudentNode(name);
newNode.next = head;
head = newNode;
}
Implementation For insertAtEnd

public void insertAtEnd(String name) {

StudentNode newNode = new StudentNode(name);
if (head == null) {
head = newNode;
} else {
StudentNode current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}

47
 DATA STRUCTURE GROUP PRESENTATION

Implementation For insertAfterKey

public void insertAfterKey(String key, String name) {

StudentNode newNode = new StudentNode(name);
StudentNode current = head;

while (current != null) {

if (current.name.equals(key)) {
newNode.next = current.next;
current.next = newNode;
return;
}
current = current.next;
}

System.out.println("Key not found: " + key);

}
Implementation For insertBeforeKey

public void insertBeforeKey(String key, String name) {

StudentNode newNode = new StudentNode(name);

if (head == null) {
System.out.println("List is empty.");
return;
}

if (head.name.equals(key)) {
newNode.next = head;

48
 DATA STRUCTURE GROUP PRESENTATION

head = newNode;
return;
}

StudentNode current = head;

while (current.next != null) {
if (current.next.name.equals(key)) {
newNode.next = current.next;
current.next = newNode;
return;
}
current = current.next;
}

System.out.println("Key not found: " + key);

}
Implementation For deleteAtBeginning

public void deleteAtBeginning() {

if (head == null) {
System.out.println("List is empty. Cannot delete from an empty list.");
} else {
head = head.next;
}
}
Implementation For deleteAtEnd
public void deleteAtEnd() {
if (head == null) {
System.out.println("List is empty. Cannot delete from an empty list.");

49
 DATA STRUCTURE GROUP PRESENTATION

} else if (head.next == null) {

head = null; // If there's only one node in the list, set head to null.
} else {
StudentNode current = head;
while (current.next.next != null) {
current = current.next;
}
current.next = null;
}
}
Implementation For deleteBeforeKey
public void deleteBeforeKey(String key) {
if (head == null || head.next == null) {
System.out.println("Not enough nodes to delete before the key.");
return;
}

if (head.next.name.equals(key)) {
head = head.next;
return;
}

StudentNode current = head;

while (current.next != null && current.next.next != null) {
if (current.next.next.name.equals(key)) {
current.next = current.next.next;
return;
}
current = current.next;

50
 DATA STRUCTURE GROUP PRESENTATION

System.out.println("Key not found: " + key);

}
Implementation For deleteAfterKey
public void deleteAfterKey(String key) {
StudentNode current = head;

while (current != null) {

if (current.name.equals(key) && current.next != null) {
current.next = current.next.next;
return;
}
current = current.next;
}

System.out.println("Key not found or no element to delete after the key: " + key);
}
Implementation For mergeLists
public static Student mergeLists(Student s, Student s1) {
Student mergedStudentList = new Student();

// if (s.head == null) {
// mergedStudentList.head = s1.head;
// return mergedStudentList;
// }

StudentNode current = s.head;

51
 DATA STRUCTURE GROUP PRESENTATION

while (current.next != null) {

current = current.next;
}

if (s1.head != null) {
current.next = s1.head;
}

mergedStudentList.head = s.head;
return mergedStudentList;
}
Implementation For Searching
public boolean search(String searchKey) {
StudentNode current = head;
int position = 0;

while (current != null) {

position++;
if (current.name.equals(searchKey)) {
System.out.println("Element found at position: " + position);
return true;

}
current = current.next;
}
System.out.println("Element not found");
return false;
} Implementation For copyingList
public Student copyList() {

52
 DATA STRUCTURE GROUP PRESENTATION

Student copiedList = new Student();

if (head == null) {
return copiedList;
}

StudentNode current = head;

StudentNode newHead = new StudentNode(current.name);
copiedList.head = newHead;

while (current.next != null) {

current = current.next;
newHead.next = new StudentNode(current.name);
newHead = newHead.next;
}

return copiedList;
}

public static void main(String[] args) {

Student s = new Student();
s.head = new StudentNode("Tahia");
StudentNode second = new StudentNode("Tasha");
StudentNode third = new StudentNode("Shafik");
StudentNode fourth = new StudentNode("Mercy");
s.head.next = second;
second.next = third;
third.next = fourth;

Student s1=new Student();

53
 DATA STRUCTURE GROUP PRESENTATION

s1.head = new StudentNode("Nasaazi");

StudentNode s1second = new StudentNode("Mbabazi");
StudentNode s1third = new StudentNode("Kakooza");
s1.head.next = s1second;
s1second.next = s1third;

s.insertAtBeginning("Annet");
s.insertAtEnd("Ukasha");
s.insertAfterKey("Shafik", "Nashif");
s.insertBeforeKey("Shafik", "Imran");
s.deleteAtBeginning();
s.deleteAtEnd();
s.deleteBeforeKey("Shafik");
s.deleteAfterKey("Shafik");
s.search("Tasha");

s.traverseAndPrint();

System.out.println("Meged student List");

Student mergedList = mergeLists(s, s1);
mergedList.traverseAndPrint();

System.out.println("Copied List:");
Student copiedList = s.copyList();
copiedList.traverseAndPrint();

54
 DATA STRUCTURE GROUP PRESENTATION

}
}
DOUBLE LINKEDLIST
public class Student1 {
private Student1Node head;
private Student1Node tail;
private int length;
public class Student1Node {
int age;
Student1Node next;
Student1Node prev;
public Student1Node(int age){
this.age=age;
this.next=null;
this.prev=null;
}

}
public Student1(){
this.head=null;
this.tail=null;
this.length=0;

}
public boolean isEmpty(){
return length==0;
}
public void append(int age) {

55
 DATA STRUCTURE GROUP PRESENTATION

Student1Node n = new Student1Node(age);

if (head == null) {
head = tail = n;
} else {
tail.next = n;
n.prev = tail;
tail = n;
}
}
public void traverse1(){
Student1Node temp=head;
while (temp!=null) {
System.err.println(temp.age);
temp=temp.next;
}
System.out.println("null");
}
public void traverse2(){
Student1Node temp=tail;
while (temp!=null) {
System.out.println(temp.age);
temp=temp.prev;
}
System.out.println("null");
}
public void insertAtBeginning(int age) {
Student1Node n = new Student1Node(age);
if (head == null) {
head = tail = n;

56
 DATA STRUCTURE GROUP PRESENTATION

} else {
n.next = head;
head.prev = n;
head = n;
}
}
public void deleteAtEnd() {
if (head == null || head == tail) {
head = tail = null;
} else {
tail = tail.prev;
tail.next = null;
}
}
public void deleteAtBeginning() {
if (head == null || head == tail) {
head = tail = null;
} else {
head = head.next;
head.prev = null;
}
}
public void merge(Student1 listToMerge) {
if (listToMerge.head != null) {
if (head == null) {
head = listToMerge.head;
tail = listToMerge.tail;
} else {
tail.next = listToMerge.head;

57
 DATA STRUCTURE GROUP PRESENTATION

listToMerge.head.prev = tail;
tail = listToMerge.tail;
}
}
}
public static void main(String[] args) {
Student1 s=new Student1();
Student1 s2=new Student1();
s.append(21);
s.append(24);
s.append(23);
s.append(22);
s2.append(31);
s2.append(34);
s2.append(33);
s2.append(32);

s. insertAtBeginning(20);
// s.deleteAtEnd();
// s.deleteAtBeginning();
s.merge(s2);

s.traverse1();
s.traverse2();
}
}

Binarytree
import java.util.LinkedList;

import java.util.Queue;

58
 DATA STRUCTURE GROUP PRESENTATION

public class BinaryTree {

public TreeNode root;

public class TreeNode {

public TreeNode left;

public TreeNode right;

public int data;

public TreeNode(int data) {

this.data = data;

public BinaryTree() {

root = null; // Initializing root as null initially

public void CreateTree() {

TreeNode A = new TreeNode(1);

TreeNode B = new TreeNode(2);

TreeNode C = new TreeNode(3);

root = B;

B.right = C;

B.left = A;

IMPEMENTATION FOR INSERTING IN A TREE

public void Insert(int value) {

59
 DATA STRUCTURE GROUP PRESENTATION

if (root == null) {

root = new TreeNode(value);

} else {

InsertNode(root, value);

private void InsertNode(TreeNode node, int value) {

if (value < node.data) {

if (node.left == null) {

node.left = new TreeNode(value);

} else {

InsertNode(node.left, value);

} else {

if (node.right == null) {

node.right = new TreeNode(value);

} else {

InsertNode(node.right, value);

IMPEMENTATION FOR SEARCHING IN A TREE

public boolean Contains(TreeNode root, int value) {

if (root == null) {

return false; // If the root is null, value is not found

if (root.data == value) {

return true; // If root's data matches the value, value is found

60
 DATA STRUCTURE GROUP PRESENTATION

} else if (value < root.data) {

return Contains(root.left, value); // Search in the left subtree

} else {

return Contains(root.right, value); // Search in the right subtree

IMPEMENTATION FOR POSTORDER IN A TREE

public void Postorder(TreeNode root) {

if (root != null) {

Postorder(root.left);

Postorder(root.right);

System.out.print(root.data );

IMPEMENTATION FOR PREORDER IN A TREE

public void Preorder(TreeNode root) {

if (root != null) {

System.out.print(root.data );

Preorder(root.left);

Preorder(root.right);

IMPEMENTATION FOR INORDER IN A TREE

public void Inorder(TreeNode root) {

if (root != null) {

Inorder(root.left);

System.out.print(root.data );

Inorder(root.right);

61
 DATA STRUCTURE GROUP PRESENTATION

IMPEMENTATION FOR BREADTHFIRST IN A TREE

public void BreadthFirst(TreeNode root) {

Queue<TreeNode> Q = new LinkedList<>();

Q.add(root);

while (!Q.isEmpty()) {

TreeNode current = Q.poll();

System.out.println(current.data);

if (current.left != null) {

Q.add(current.left);

if (current.right != null) {

Q.add(current.right);

IMPEMENTATION FOR FINDPARENTNODE IN A TREE

public TreeNode findParent(int value, TreeNode root) {

if (root == null) {

System.out.println("Tree is empty");

return null;

TreeNode parent = null;

TreeNode current = root;

62
 DATA STRUCTURE GROUP PRESENTATION

while (current != null) {

if (value == current.data) {

System.out.println("Root node has no parent");

return null;

} else if (value < current.data) {

if (current.left != null && current.left.data == value) {

return current;

parent = current;

current = current.left;

} else {

if (current.right != null && current.right.data == value) {

return current

parent = current;

current = current.right;

System.out.println("Node with value " + value + " not found");

return null;

public static void main(String[] args) {

BinaryTree tree = new BinaryTree();

tree.CreateTree();

tree.Insert(7) ;

tree.Contains(tree.root,6);

tree.findParent(3, tree.root);

63
 DATA STRUCTURE GROUP PRESENTATION

System.out.println("Preorder traversal:");

tree.Preorder(tree.root);

System.out.println("Postorder traversal:");

tree.Postorder(tree.root);

System.out.println("Inorder traversal:");

tree.Inorder(tree.root);

System.out.println("BreadthFirst traversal:");

tree.BreadthFirst(tree.root);

public class BinaryTreeOne {

public TreeNode root;

public class TreeNode {

public TreeNode left;

public TreeNode right;

public String data;

public TreeNode(String data) {

this.data = data;

public BinaryTreeOne() {

root = null; // Initializing root as null initially

public void CreateTree() {

64
 DATA STRUCTURE GROUP PRESENTATION

TreeNode A = new TreeNode("1");

TreeNode B = new TreeNode("+");

TreeNode C = new TreeNode("3");

root = B;

B.right = C;

B.left = A;

IMPEMENTATION FOR PREFIX IN A TREE

public void infix(TreeNode root) {

if (root != null) {

if (isOperand(root.data)) {

System.out.print(root.data + " ");

} else {

System.out.print("( ");

infix(root.left);

System.out.print(root.data + " ");

infix(root.right);

System.out.print(") ");

private boolean isOperand(String token) {

// A simple check if the token is not an operator (+, -, *, /, etc.)

return !token.equals("+") && !token.equals("-") &&

!token.equals("*") && !token.equals("/");

public static void main(String[] args) {

65
 DATA STRUCTURE GROUP PRESENTATION

BinaryTreeOne tree = new BinaryTreeOne();

tree.CreateTree();

System.out.println("Infix notation:");

tree.infix(tree.root);

import java.util.*;

import java.util.Queue;

public class Queue_Enqueue_Single {

// Queue class representing a singly linked list-based queue

private The_Queue_Node front; //Front of the queue

private The_Queue_Node rear; //Rear of the queue

public Queue_Enqueue_Single(){

this.front=null;

this.rear=null;

//Enqueue operation to imsert an element into the queue

public void enqueue (int newData){

//Create a new node with the given data

The_Queue_Node newNode = new The_Queue_Node(newData);

//If the queue is empty, set set both the front and the rear to new node

if (isEmpty()){

front = rear = newNode;

} else {

//otherwise, add the new node at the end (Rear) of the queue

rear.nextNode = newNode;

rear = newNode;

66
 DATA STRUCTURE GROUP PRESENTATION

//Methed to check if the queue is empty

public boolean isEmpty(){

return front == null;

//Display elements in the queue

public void display(){

if(isEmpty()){

System.out.println(" This queue is empty!!");

return;

The_Queue_Node currentNode = front;

while (currentNode != null){

System.out.print("\nThe value is "+currentNode.dataValue+".");

currentNode = currentNode.nextNode;

System.out.println();

//IMPLEMENTATION FOR ENQUEUE

class EnqueueImplementation{

public static void main(String args []){

Queue_Enqueue_Single myQueue = new Queue_Enqueue_Single();

//Enqueue some elements

myQueue.enqueue(13);

myQueue.enqueue(22);

myQueue.enqueue(30);

myQueue.enqueue(113);

myQueue.enqueue(55);

myQueue.enqueue(7);

67
 DATA STRUCTURE GROUP PRESENTATION

//Display the elemwnta in qeue

System.out.print("");

myQueue.display();

public class Queue_Dequeue_Single {

// Queue class representing a singly linked list-based queue

private The_Queue_Node front; // Front of the queue

private The_Queue_Node rear; // Rear of the queue

public Queue_Dequeue_Single() {

this.front = null;

this.rear = null;

// Enqueue operation to insert an element into the queue

public void enqueue(int data) {

// Create a new node with the given data

The_Queue_Node newNode = new The_Queue_Node(data);

// If the queue is empty, set both front and rear to the new node

if (isEmpty()) {

front = rear = newNode;

} else {

// Otherwise, add the new node to the end (rear) of the queue

rear.nextNode = newNode;

rear = newNode;

68
 DATA STRUCTURE GROUP PRESENTATION

// Dequeue operation to remove an element from the front of the queue

public void dequeue() {

// If the queue is empty, print an error message

if (isEmpty()) {

System.out.println("Queue is empty. Cannot dequeue.");

return;

// If there is only one element in the queue, set front and rear to null

if (front == rear) {

front = rear = null;

} else {

// Otherwise, move front to the next node in the queue

front = front.nextNode;

// Method to check if the queue is empty

public boolean isEmpty() {

return front == null;

// Display the elements in the queue

public void display() {

if (isEmpty()) {

System.out.println("Queue is empty.");

return;

69
 DATA STRUCTURE GROUP PRESENTATION

The_Queue_Node currentNode = front;

while (currentNode != null) {

System.out.print(currentNode.dataValue + " ");

currentNode = currentNode.nextNode;

System.out.println();

IMPMENTATION FOR DEQUEUE

class DequeueImplement {

public static void main(String[] args) {

Queue_Dequeue_Single mySingleQueue = new Queue_Dequeue_Single();

// Enqueue some elements

mySingleQueue.enqueue(2024);

mySingleQueue.enqueue(2023);

mySingleQueue.enqueue(2022);

// Display the elements in the queue

System.out.print("Queue elements: ");

mySingleQueue.display();

// Dequeue an element

mySingleQueue.dequeue();

// Display the updated queue

System.out.print("Queue after dequeue operation: ");

mySingleQueue.display();

//import java.util.*;

70
 DATA STRUCTURE GROUP PRESENTATION

public class Stack_Pop_Single {

private The_Stack_Node topNode;

public Stack_Pop_Single() {

this.topNode = null;

IMPLEMENTATION FOR PUSH

public void push(int Number) {

// Step 1: Create a new node with data equal to newElement

The_Stack_Node newNode = new The_Stack_Node(Number);

// Step 2: Set the next pointer of the new node to point to the current top of the
Stack_Push_Single

newNode.nextNode = topNode;

// Step 3: Update the top of the Stack_Push_Single to the new node

topNode = newNode;

// POP operation

public int pop() {

// Step 1: If the stack is empty, return an indication that the stack is empty

if (topNode == null) {

System.out.println("Stack is empty.");

return -1; // Assuming -1 is an indication of an empty stack for integers; adjust accordingly

// Step 2: Create a temporary variable to hold the current top of the stack

The_Stack_Node temp = topNode;

// Step 3: Update the top of the stack to the next node

71
 DATA STRUCTURE GROUP PRESENTATION

topNode = topNode.nextNode;

// Step 4: Return the data stored in the temporary variable

return temp.dataValue;

// Display the stack

public void display() {

The_Stack_Node currentNode = topNode;

while (currentNode != null) {

System.out.print("\nThe element is :>> "+currentNode.dataValue + ".");

currentNode = currentNode.nextNode;

System.out.println();

class ImplementStack {

public static void main(String[] args) {

Stack_Pop_Single stack = new Stack_Pop_Single();

// Perform PUSH operations

stack.push(1);

stack.push(2);

stack.push(10);

stack.push(101);

stack.push(30);

stack.push(37);

// Display the original stack

System.out.print("\nSTACK BEFOR POP OPERATIONS:");

72
 DATA STRUCTURE GROUP PRESENTATION

stack.display();

// Perform POP operations

int poppedElement1 = stack.pop();

int poppedElement2 = stack.pop();

// Display the popped elements

System.out.println("\nPOPPED ELEMENTS:");

System.out.println("Popped Element 1: " + poppedElement1);

System.out.println("Popped Element 2: " + poppedElement2);

// Display the updated stack after POP operations

System.out.print("\nSTACK AFTER POP OPERATIONS:");

stack.display();

//import java.util.*;

public class Stack_Pop_Single {

private The_Stack_Node topNode;

public Stack_Pop_Single() {

this.topNode = null;

// PUSH operation

public void push(int Number) {

// Step 1: Create a new node with data equal to newElement

The_Stack_Node newNode = new The_Stack_Node(Number);

73
 DATA STRUCTURE GROUP PRESENTATION

// Step 2: Set the next pointer of the new node to point to the current top of the
Stack_Push_Single

newNode.nextNode = topNode;

// Step 3: Update the top of the Stack_Push_Single to the new node

topNode = newNode;

IMPLEMENTATION FOR POP

public int pop() {

// Step 1: If the stack is empty, return an indication that the stack is empty

if (topNode == null) {

System.out.println("Stack is empty.");

return -1; // Assuming -1 is an indication of an empty stack for integers; adjust accordingly

// Step 2: Create a temporary variable to hold the current top of the stack

The_Stack_Node temp = topNode;

// Step 3: Update the top of the stack to the next node

topNode = topNode.nextNode;

// Step 4: Return the data stored in the temporary variable

return temp.dataValue;

// Display the stack

public void display() {

The_Stack_Node currentNode = topNode;

while (currentNode != null) {

System.out.print("\nThe element is :>> "+currentNode.dataValue + ".");

currentNode = currentNode.nextNode;

74
 DATA STRUCTURE GROUP PRESENTATION

System.out.println();

class ImplementStack {

public static void main(String[] args) {

Stack_Pop_Single stack = new Stack_Pop_Single();

// Perform PUSH operations

stack.push(1);

stack.push(2);

stack.push(10);

stack.push(101);

stack.push(30);

stack.push(37);

// Display the original stack

System.out.print("\nSTACK BEFOR POP OPERATIONS:");

stack.display();

// Perform POP operations

int poppedElement1 = stack.pop();

int poppedElement2 = stack.pop();

// Display the popped elements

System.out.println("\nPOPPED ELEMENTS:");

System.out.println("Popped Element 1: " + poppedElement1);

System.out.println("Popped Element 2: " + poppedElement2);

// Display the updated stack after POP operations

75
 DATA STRUCTURE GROUP PRESENTATION

System.out.print("\nSTACK AFTER POP OPERATIONS:");

stack.display();

76