Array Data Structure Explained — How Arrays Work, Why They Matter, and How to Use Them

package io.thecodeforge.ds;

import java.util.Arrays;

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

        int[] arr = {10, 20, 30, 40, 50};

        // 1. Access by index — O(1)
        System.out.println("Access arr[2]: " + arr[2]); // 30

        // 2. Update by index — O(1)
        arr[2] = 35;
        System.out.println("After update  : " + Arrays.toString(arr));

        // 3. Insert at index 2 — O(n) shift
        int[] expanded = new int[arr.length + 1];
        // Copy elements before insertion point
        System.arraycopy(arr, 0, expanded, 0, 2);
        // Place new value
        expanded[2] = 25;
        // Shift remaining elements right
        System.arraycopy(arr, 2, expanded, 3, arr.length - 2);
        System.out.println("After insert  : " + Arrays.toString(expanded));

        // 4. Delete at index 2 — O(n) shift
        int[] contracted = new int[expanded.length - 1];
        System.arraycopy(expanded, 0, contracted, 0, 2);
        System.arraycopy(expanded, 3, contracted, 2, expanded.length - 3);
        System.out.println("After delete  : " + Arrays.toString(contracted));

        // 5. Linear search — O(n)
        int target = 40;
        int foundIndex = -1;
        for (int i = 0; i < contracted.length; i++) {
            if (contracted[i] == target) { foundIndex = i; break; }
        }
        System.out.println("Linear search for " + target + ": index " + foundIndex);

        // 6. Binary search — O(log n) requires sorted array
        Arrays.sort(contracted);
        int bsResult = Arrays.binarySearch(contracted, 40);
        System.out.println("Binary search for 40: index " + bsResult);
    }
}

package io.thecodeforge.ds;

/**
 * Quick reference: array operation complexities.
 * Use this as a cheat sheet for interview prep and system design.
 */
public class ArrayComplexityReference {

    /*
     * OPERATION COMPLEXITY TABLE
     * ─────────────────────────
     * Access by index      : O(1)   — direct memory address calculation
     * Search (unsorted)    : O(n)   — linear scan through every element
     * Search (sorted)      : O(log n) — binary search, halving each step
     * Insert at end        : O(1)*  — amortized for dynamic arrays (ArrayList)
     * Insert at position i : O(n)   — must shift elements right
     * Delete at position i : O(n)   — must shift elements left
     * Copy entire array    : O(n)   — must visit every element
     *
     * * Amortized: most appends are O(1), but occasional resize is O(n).
     *   Over N appends, total cost is O(N), so per-append is O(1) amortized.
     */

    public static void main(String[] args) {
        // Demonstrate the address calculation that makes O(1) access possible
        int[] data = {100, 200, 300, 400, 500};

        // The JVM computes: address_of_data + (index * 4 bytes per int)
        // index 0 -> base + 0 = 100
        // index 3 -> base + 12 = 400
        // This is a single CPU instruction regardless of array size
        System.out.println("data[0] = " + data[0]);  // 100
        System.out.println("data[3] = " + data[3]);  // 400

        // Demonstrate O(n) insertion cost
        long startTime = System.nanoTime();
        int[] growing = new int[0];
        for (int i = 0; i < 100000; i++) {
            // Simulating insert-at-beginning: O(n) per insert
            int[] temp = new int[growing.length + 1];
            temp[0] = i;
            System.arraycopy(growing, 0, temp, 1, growing.length);
            growing = temp;
        }
        long insertAtStart = System.nanoTime() - startTime;

        startTime = System.nanoTime();
        int[] appending = new int[100000];
        for (int i = 0; i < 100000; i++) {
            // Append at end: O(1) per insert (pre-allocated)
            appending[i] = i;
        }
        long appendAtEnd = System.nanoTime() - startTime;

        System.out.println("Insert at start (100k): " + insertAtStart / 1_000_000 + " ms");
        System.out.println("Append at end  (100k): " + appendAtEnd / 1_000_000 + " ms");
        System.out.println("Ratio: " + (insertAtStart / Math.max(appendAtEnd, 1)) + "x slower");
    }
}

package io.thecodeforge.ds;

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

        // Declare and create an array of 5 student scores.
        // Java reserves 5 consecutive int-sized slots in memory right now.
        // Each int in Java takes 4 bytes, so this reserves 20 bytes in a row.
        int[] studentScores = new int[5];

        // Assign values to each slot using the index (offset from start).
        // Index 0 = first slot (0 steps from the start)
        // Index 4 = last slot (4 steps from the start)
        studentScores[0] = 91;  // first student
        studentScores[1] = 78;  // second student
        studentScores[2] = 85;  // third student
        studentScores[3] = 62;  // fourth student
        studentScores[4] = 99;  // fifth student

        // Access any element instantly by its index — no looping needed.
        // The JVM computes: base_address + (3 * 4 bytes) = value at index 3
        System.out.println("Score at index 3: " + studentScores[3]);

        // .length gives us the number of slots (declared size), not the last index.
        // Last valid index is always length - 1.
        System.out.println("Total slots reserved: " + studentScores.length);
        System.out.println("Last valid index    : " + (studentScores.length - 1));

        // Shorthand: declare and fill in one line using an array literal.
        // Java counts the values and sets the size automatically (5 here).
        int[] dailySteps = {4200, 8100, 6750, 9300, 7050};
        System.out.println("\nSteps on day 1 (index 0): " + dailySteps[0]);
        System.out.println("Steps on day 5 (index 4): " + dailySteps[4]);
    }
}

package io.thecodeforge.ds;

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

        int[] monthlyRainfall = {45, 30, 55, 80, 120, 95, 110, 105, 70, 40, 25, 50};

        // ── PATTERN 1: Classic for loop (use when you need the index) ──────────
        System.out.println("=== Monthly Rainfall Report ===");
        String[] monthNames = {"Jan","Feb","Mar","Apr","May","Jun",
                               "Jul","Aug","Sep","Oct","Nov","Dec"};

        for (int i = 0; i < monthlyRainfall.length; i++) {
            System.out.println(monthNames[i] + ": " + monthlyRainfall[i] + " mm");
        }

        // ── PATTERN 2: Enhanced for-each (use when you only need values) ───────
        int totalRainfall = 0;
        for (int rainfall : monthlyRainfall) {
            totalRainfall += rainfall;
        }
        System.out.println("\nTotal annual rainfall: " + totalRainfall + " mm");
        System.out.printf("Monthly average      : %.1f mm%n",
                          (double) totalRainfall / monthlyRainfall.length);

        // ── PATTERN 3: Finding the maximum (running champion pattern) ───────────
        int peakRainfall = monthlyRainfall[0];
        int peakMonth    = 0;

        for (int i = 1; i < monthlyRainfall.length; i++) {
            if (monthlyRainfall[i] > peakRainfall) {
                peakRainfall = monthlyRainfall[i];
                peakMonth    = i;
            }
        }
        System.out.println("\nWettest month: " + monthNames[peakMonth]
                           + " with " + peakRainfall + " mm");
    }
}

package io.thecodeforge.ds;

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

        boolean[][] cinemaSeats = {
            {true,  false, true,  true,  false},  // Row 0 (front)
            {false, false, false, true,  true },  // Row 1 (middle)
            {true,  true,  false, false, false}   // Row 2 (back)
        };

        System.out.println("=== Cinema Seating Plan ===");
        System.out.println("     Seat: 1    2    3    4    5");

        for (int row = 0; row < cinemaSeats.length; row++) {
            System.out.print("Row " + (row + 1) + ":  ");
            for (int seat = 0; seat < cinemaSeats[row].length; seat++) {
                System.out.print(cinemaSeats[row][seat] ? "[B]  " : "[_]  ");
            }
            System.out.println();
        }

        int availableCount = 0;
        for (boolean[] row : cinemaSeats) {
            for (boolean seatBooked : row) {
                if (!seatBooked) availableCount++;
            }
        }
        System.out.println("\nAvailable seats: " + availableCount
                           + " out of " + (cinemaSeats.length * cinemaSeats[0].length));

        cinemaSeats[1][2] = true;
        System.out.println("Seat 3 in Row 2 is now booked: " + cinemaSeats[1][2]);
    }
}

package io.thecodeforge.ds;

import java.util.ArrayList;

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

        // ── RAW ARRAY: Fixed size, fast, lightweight ─────────────────────────
        double[] weeklyTemperatures = {18.5, 21.0, 19.8, 23.4, 25.1, 22.7, 20.3};
        System.out.println("=== Fixed-Size Array (Weekly Temperatures) ===");
        for (int day = 0; day < weeklyTemperatures.length; day++) {
            System.out.printf("Day %d: %.1f°C%n", day + 1, weeklyTemperatures[day]);
        }

        // ── ARRAYLIST: Dynamic size, flexible ────────────────────────────────
        ArrayList<String> shoppingCart = new ArrayList<>();

        shoppingCart.add("Apples");
        shoppingCart.add("Bread");
        shoppingCart.add("Orange Juice");
        System.out.println("\n=== Dynamic ArrayList (Shopping Cart) ===");
        System.out.println("Cart after adding 3 items: " + shoppingCart);

        shoppingCart.remove("Bread");
        System.out.println("Cart after removing Bread: " + shoppingCart);
        System.out.println("Number of items in cart  : " + shoppingCart.size());

        System.out.println("First item in cart: " + shoppingCart.get(0));
    }
}

package io.thecodeforge.ds;

import java.lang.reflect.Array;

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

        // Primitive array: values stored directly in the array memory
        int[] primitiveArray = new int[1_000_000];
        // Memory: 16 bytes header + 4 bytes * 1,000,000 = ~4MB contiguous block

        // Object array: stores REFERENCES to objects, not the objects themselves
        Integer[] objectArray = new Integer[1_000_000];
        for (int i = 0; i < objectArray.length; i++) {
            objectArray[i] = i; // autoboxing: creates 1M Integer objects on the heap
        }
        // Memory: 16 bytes header + 8 bytes * 1,000,000 references = ~8MB for references
        // PLUS: 1,000,000 * ~16 bytes per Integer object = ~16MB for objects
        // Total: ~24MB vs ~4MB for primitive array — 6x more memory

        System.out.println("Primitive array length: " + primitiveArray.length);
        System.out.println("Object array length   : " + objectArray.length);

        // Demonstrate that object arrays hold references, not values
        Integer a = 42;
        Integer[] refs = {a};
        a = 99; // reassign the variable
        System.out.println("\nArray still holds: " + refs[0]); // still 42 — the reference didn't change

        // Default values differ by type
        System.out.println("\nDefault values in new arrays:");
        System.out.println("int[] default    : " + new int[1][0]);       // 0
        System.out.println("boolean[] default: " + new boolean[1][0]);  // false
        System.out.println("double[] default : " + new double[1][0]);   // 0.0
        System.out.println("String[] default : " + new String[1][0]);   // null
    }
}