Topic 1 - 4 Hours

Introduction to Data Structures & Java Collections

Lecture: Foundations of Data Structures

What are Data Structures?

A data structure is a specialized format for organizing, processing, retrieving, and storing data. Different data structures excel at different tasks, making the choice of data structure critical to writing efficient algorithms. In this course, we'll explore how Java implements fundamental data structures and when to use each one.

Why Study Algorithms?

Algorithms are step-by-step procedures for solving problems. Understanding how to analyze algorithm efficiency allows you to write code that scales gracefully as data grows. We measure efficiency using Big-O notation, which describes how runtime or memory usage grows relative to input size.

Java Collections Framework Overview

Java provides built-in data structures through the Collections Framework. Unlike Python's native list and dict types, Java separates static arrays from dynamic collections. Here are the key mappings:

Arrays: Fixed-size, type-specific storage (int[], String[])
ArrayList: Dynamic arrays that grow automatically (replaces Python lists)
HashMap: Key-value pairs with O(1) average access (replaces Python dictionaries)

Arrays vs ArrayList

Static Arrays have a fixed size declared at creation. They offer fast access (O(1)) but cannot resize. ArrayList wraps arrays and automatically grows when needed, providing flexibility at a slight performance cost during resizing operations.

Numeral Algorithms

Numeral algorithms perform basic arithmetic operations on collections of numbers. Common tasks include:

Average: Sum all elements, divide by count
Min/Max: Iterate through collection, tracking extremes
Mode: Find the most frequently occurring value
GCD (Greatest Common Divisor): Using Euclidean algorithm

Linear Search

Linear search is the simplest search algorithm. It examines each element sequentially until finding the target or reaching the end. Time complexity is O(n) in the worst case, making it suitable for small datasets or unsorted collections where more sophisticated algorithms cannot be applied.

Code Showcase: IntroDataStructures.java

import java.util.ArrayList;
import java.util.HashMap;

public class IntroDataStructures {
    
    public static void main(String[] args) {
        demonstrateArrays();
        demonstrateArrayList();
        demonstrateHashMap();
        demonstrateLinearSearch();
        demonstrateGCD();
    }
    
    public static void demonstrateArrays() {
        int[] staticArray = new int[5];
        staticArray[0] = 10;
        staticArray[1] = 20;
        staticArray[2] = 30;
        staticArray[3] = 40;
        staticArray[4] = 50;
        
        System.out.println("Static Array Elements:");
        for (int i = 0; i < staticArray.length; i++) {
            System.out.println("Index " + i + ": " + staticArray[i]);
        }
    }
    
    public static void demonstrateArrayList() {
        ArrayList<Integer> dynamicList = new ArrayList<>();
        
        dynamicList.add(10);
        dynamicList.add(20);
        dynamicList.add(30);
        
        System.out.println("\nArrayList (Dynamic) Elements:");
        for (int i = 0; i < dynamicList.size(); i++) {
            System.out.println("Index " + i + ": " + dynamicList.get(i));
        }
        
        dynamicList.add(40);
        System.out.println("After adding 40, size: " + dynamicList.size());
    }
    
    public static void demonstrateHashMap() {
        HashMap<String, Integer> studentGrades = new HashMap<>();
        
        studentGrades.put("Alice", 95);
        studentGrades.put("Bob", 87);
        studentGrades.put("Charlie", 92);
        
        System.out.println("\nHashMap (Key-Value Pairs):");
        for (String name : studentGrades.keySet()) {
            System.out.println(name + " scored: " + studentGrades.get(name));
        }
        
        System.out.println("Bob's grade: " + studentGrades.get("Bob"));
    }
    
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }
    
    public static void demonstrateLinearSearch() {
        int[] numbers = {15, 23, 8, 42, 16, 4, 31};
        int target = 42;
        
        int result = linearSearch(numbers, target);
        
        System.out.println("\nLinear Search:");
        if (result != -1) {
            System.out.println("Found " + target + " at index " + result);
        } else {
            System.out.println(target + " not found in array");
        }
    }
    
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    public static void demonstrateGCD() {
        int num1 = 48;
        int num2 = 18;
        
        int result = gcd(num1, num2);
        
        System.out.println("\nGreatest Common Divisor:");
        System.out.println("GCD of " + num1 + " and " + num2 + " is: " + result);
    }
    
    public static int findMin(int[] arr) {
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        return min;
    }
    
    public static int findMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }
    
    public static int findMode(int[] arr) {
        HashMap<Integer, Integer> frequencyMap = new HashMap<>();
        
        for (int num : arr) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        int mode = arr[0];
        int maxFrequency = 0;
        
        for (int num : frequencyMap.keySet()) {
            if (frequencyMap.get(num) > maxFrequency) {
                maxFrequency = frequencyMap.get(num);
                mode = num;
            }
        }
        
        return mode;
    }
    
    public static double calculateAverage(int[] arr) {
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        return (double) sum / arr.length;
    }
}

Interactive Quiz

Lab Exercise: Numeral Algorithms Challenge

Challenge: Complete Statistics Calculator

Create a Java program called StatisticsCalculator.javathat performs the following operations on an array of integers:

Requirements:

Calculate Average: Compute the mean of all numbers in the array
Find Minimum: Return the smallest value in the array
Find Maximum: Return the largest value in the array
Find Mode: Return the most frequently occurring number
Calculate GCD: Create a method that accepts two integers and returns their Greatest Common Divisor using the Euclidean algorithm
Implement Linear Search: Create a search method that finds the index of a target value

Test Data:

int[] testArray = {12, 7, 12, 52, 3, 12, 52, 7, 8};
int searchTarget = 52;
int gcdA = 48;
int gcdB = 18;

Expected Output:

Average: 20.56
Minimum: 3
Maximum: 52
Mode: 12
GCD(48, 18): 6
Linear Search for 52: Found at index 3

Bonus Challenge: Modify your linear search to return ALL indices where the target appears, not just the first occurrence. Return the results as an ArrayList<Integer>.

Key Takeaways

Java separates static arrays (fixed size) from dynamic collections like ArrayList
HashMap provides O(1) average-case key-value lookups, replacing Python dictionaries
Linear search has O(n) time complexity but works on any collection
The Euclidean algorithm efficiently computes GCD in O(log min(a,b)) time
Understanding basic algorithms like min/max/mode prepares you for advanced data structure operations