From the free course Java Programming and Algorithmic Thinking Fundamentals on Lykke

Arrays and Data Collections

Key concepts: Array Initialization and Indexing · Reference Aliasing vs. Deep Copying · Standard and Enhanced For-Loops · Linear Search · 2D Arrays

Introduction to one-dimensional and two-dimensional arrays for managing collections of data.

Arrays and Data Collections

In the architecture of computer science, the array stands as the most fundamental data structure for organizing information. While individual variables allow us to store discrete data points—a single integer, a solitary boolean, a lone floating-point number—they fail to scale when we encounter datasets of significant magnitude. Imagine representing the daily closing prices of a stock over a decade; declaring 3,650 individual variables is not only impractical but computationally unmanageable.

An array solves this by providing a contiguous block of memory capable of storing a fixed-size, sequential collection of elements of the same type. In Java, arrays are treated as objects, a distinction that has profound implications for how they are stored in memory, passed to methods, and manipulated during execution.

Array Initialization and Indexing

What it is

An array is a collection of variables of the same type, referenced by a single name. Each individual value in the array is called an element, and its position is identified by an index.

Why it matters

Arrays provide constant-time access ($O(1)$ complexity) to any element if the index is known. This efficiency is possible because the computer calculates the memory address of an element using a simple formula: $$\text{Address} = \text{Base Address} + (\text{Index} \times \text{Size of Element})$$

How it works: Declaration and Instantiation

In Java, creating an array is a two-step process (often combined into one):

  1. Declaration: Informing the compiler of the array's name and the type of data it will hold.
  2. Instantiation: Using the new keyword to allocate a specific amount of memory on the heap.
// Declaration
int[] grades; 

// Instantiation (allocating space for 5 integers)
grades = new int[5];

// Combined syntax
double[] prices = new double[100];

Indexing and Bounds

Java utilizes zero-based indexing. For an array of length $N$, the valid indices are $0, 1, 2, \dots, N-1$. Accessing an index outside of this range (e.g., grades[5] for an array of size 5) results in the dreaded ArrayIndexOutOfBoundsException.

Feature Description
Type Homogeneity All elements must be of the same declared type.
Fixed Size Once instantiated, the size cannot be changed.
Default Values Numeric types initialize to 0 or 0.0, booleans to false, and objects to null.
Length Property Accessed via arrayName.length (note: no parentheses).

Concrete Example: Command-Line Parsing

As seen in the source materials, arrays are often populated using command-line arguments (args[]).

public class ArrayInit {
    public static void main(String[] args) {
        // args is an array of Strings provided by the OS
        int n = args.length;
        int[] nums = new int[n];
        
        for (int i = 0; i < n; i++) {
            // Parsing String to int and storing in the array
            nums[i] = Integer.parseInt(args[i]);
        }
    }
}

Common Pitfalls: The Off-by-One Error

The most common mistake for beginners is attempting to access array[array.length]. Because indexing starts at 0, the final element is always at length - 1.


Reference Aliasing vs. Deep Copying

What it is

In Java, an array variable does not "hold" the array data; it holds a reference (a memory address) to where the data lives on the heap.

  • Aliasing: When two variables point to the same memory address.
  • Deep Copying: Creating a brand new array and copying the actual values from the original into the new one.

Why it matters

Understanding the distinction is critical for data integrity. If you "copy" an array using the assignment operator (=), you are only copying the address, not the data. Changing an element through one variable will change it for the other, as they both point to the same physical memory.

How it works: The Mechanics of Memory

When you execute int[] b = a;, Java performs a shallow copy of the reference.

The Aliasing Theorem: If $A$ and $B$ are aliases, then the operation $A[i] = v$ implies that $B[i]$ also equals $v$, for all valid $i$.

To create a truly independent copy, you must perform a Deep Copy:

  1. Create a new array of the same length.
  2. Iterate through the original array.
  3. Assign each value to the corresponding index in the new array.

Concrete Example: Aliasing vs. Deep Copy

int[] original = {10, 20, 30};

// ALIASING (Shallow Copy)
int[] alias = original;
alias[0] = 99; 
// original[0] is now also 99!

// DEEP COPYING
int[] deepCopy = new int[original.length];
for (int i = 0; i < original.length; i++) {
    deepCopy[i] = original[i];
}
deepCopy[0] = 55;
// original[0] remains 99. deepCopy is independent.

Comparison Table: Copying Methods

Method Type Result Use Case
b = a Reference Assignment Aliasing Passing arrays to methods (efficient).
for loop copy Manual Deep Copy Independent Array When the original data must be preserved.
a.clone() Built-in Method Deep Copy (1D) Quick duplication of 1D arrays.
System.arraycopy() System Method Deep Copy High-performance copying of large blocks.

Traversal: Standard and Enhanced For-Loops

What it is

Traversal is the process of visiting every element in a data structure exactly once. In Java, this is primarily achieved through two types of loops.

Why it matters

Most array-based algorithms—finding a sum, searching for a value, or calculating an average—require a full traversal. Choosing the right loop type improves code readability and reduces errors.

How it works: Standard vs. Enhanced

  1. Standard For-Loop: Uses an index variable (usually i) to access elements.
  2. Enhanced For-Loop (For-Each): Introduced in Java 5, it abstracts the indexing away to provide a cleaner syntax.
double[] measurements = {1.2, 3.5, 2.0, 4.8};

// Standard For-Loop: Provides index access
for (int i = 0; i < measurements.length; i++) {
    System.out.println("Element at " + i + ": " + measurements[i]);
}

// Enhanced For-Loop: Read-only, cleaner
for (double val : measurements) {
    System.out.println("Value: " + val);
}

Comparison of Loop Capabilities

Feature Standard for Enhanced for
Index Access Yes (can use i) No
Modification Yes (can change arr[i]) No (variable is a local copy)
Direction Any (forward, backward, skip) Forward only
Multiple Arrays Can traverse multiple simultaneously One array at a time

Common Pitfall: Modifying with Enhanced For-Loops

A common mistake is trying to initialize or change an array using an enhanced for-loop:

for (int x : myIntArray) {
    x = 10; // This does NOT change the array. It only changes the local variable 'x'.
}

Linear Search and Extrema Algorithms

What it is

Linear Search is the simplest searching algorithm. It examines each element of a collection sequentially until a match is found or the end of the collection is reached.

Why it matters

While more advanced algorithms like Binary Search exist, Linear Search is the only option for unsorted data. It serves as the baseline for algorithmic complexity ($O(n)$).

How it works: The Search Logic

  1. Initialize a "found" flag or a "target index" variable (often to -1).
  2. Iterate through the array from index 0 to $n-1$.
  3. Compare the current element to the target.
  4. If they match, record the index and break the loop.

Concrete Example: Finding the Maximum and Searching

public class ArrayAlgorithms {
    public static void main(String[] args) {
        int[] data = {4, 12, 7, 19, 3, 21, 8};
        int target = 19;
        
        // 1. Finding Maximum
        int max = data[0]; // Assume first is max
        for (int i = 1; i < data.length; i++) {
            if (data[i] > max) {
                max = data[i];
            }
        }
        
        // 2. Linear Search
        int foundIndex = -1;
        for (int i = 0; i < data.length; i++) {
            if (data[i] == target) {
                foundIndex = i;
                break; // Efficiency: stop once found
            }
        }
    }
}

Variations: Swapping and Shifting

  • Swapping: To swap a[i] and a[j], a temporary variable is required: int temp = a[i]; a[i] = a[j]; a[j] = temp;
  • Shifting: Moving elements to the left or right (used in queues or when deleting elements). Shifting requires careful loop direction to avoid overwriting data before it is moved.

2D Arrays: Grids and Matrices

What it is

A 2D Array is essentially an "array of arrays." It is used to represent data in a grid format, such as a chessboard, a spreadsheet, or pixels in an image.

Why it matters

Many real-world problems are multidimensional. Scientific computing, image processing, and game development rely heavily on matrix operations.

How it works: Row-Major Order

In Java, 2D arrays are stored in row-major order. When you declare int[][] matrix = new int[3][4];, you are creating an array with 3 elements, where each element is itself an array of 4 integers.

  • matrix.length returns the number of rows.
  • matrix[i].length returns the number of columns in row i.

Concrete Example: Matrix Summation

To process a 2D array, nested loops are required. The outer loop typically iterates through rows, while the inner loop iterates through columns.

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

int totalSum = 0;
for (int row = 0; row < table.length; row++) {
    for (int col = 0; col < table[row].length; col++) {
        totalSum += table[row][col];
    }
}

Complexity and Performance

Accessing table[row][col] is still $O(1)$, but traversing the entire matrix is $O(R \times C)$, where $R$ is rows and $C$ is columns. In Java, 2D arrays can be ragged (or "jagged"), meaning each row can have a different number of columns.

Structure Declaration Access Logic
1D Array int[] a a[i]
2D Array int[][] a a[row][col]
3D Array int[][][] a a[x][y][z]

Summary of Array Operations Complexity

Operation Complexity Note
Access by Index $O(1)$ Direct memory calculation.
Search (Unsorted) $O(n)$ Must check every element in worst case.
Insertion (Start) $O(n)$ Must shift all existing elements to the right.
Deletion (Start) $O(n)$ Must shift all existing elements to the left.
Traversal $O(n)$ Linear time relative to size.

Professor's Note: While arrays are powerful due to their speed and simplicity, their fixed-size nature is their greatest limitation. In advanced software engineering, we often use ArrayList or LinkedList to handle dynamic data, but the underlying principles of indexing and memory references remain identical to those covered here.

Arrays and Data Collections - Java Programming and Algorithmic Thinking Fundamentals - image 1
Arrays and Data Collections - Java Programming and Algorithmic Thinking Fundamentals - image 1
Arrays and Data Collections - Java Programming and Algorithmic Thinking Fundamentals - diagram 1
Arrays and Data Collections - Java Programming and Algorithmic Thinking Fundamentals - diagram 1

Source Materials

Study Java Programming and Algorithmic Thinking Fundamentals on Lykke

This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.

Add the free extensionSign in to open every section

All sections of Java Programming and Algorithmic Thinking Fundamentals · Browse more course pages

Arrays and Data Collections — Java Programming and Algorithmic Thinking Fundamentals | Lykke