Arrays - Fundamental Data Structure

Arrays are one of the most fundamental and widely-used data structures in computer programming. They provide an organized way to store collections of elements of the same data type in contiguous memory locations.

📚 Table of Contents

Key Characteristics
Memory Layout
Array Operations
Implementation
Complexity Analysis
Advantages & Disadvantages
Study Notes
Practice Problems

Key Characteristics

🔹 Fixed Size

When you create an array, you define its length at compile time
The size remains immutable after creation
Memory is allocated for the maximum number of elements specified

🔹 Sequential Storage

Elements are stored in contiguous memory locations
This enables efficient memory access and cache performance
Sequential storage is key to arrays’ performance advantages

🔹 Index-Based Access

Each element has a unique numerical index representing its position
Index typically starts at 0 for the first element
Random access: Any element can be accessed in O(1) time using its index
Example: arr[3] accesses the fourth element

🔹 Homogeneous Data

All elements must be of the same data type
Ensures consistent memory allocation per element
Type safety at compile time

Memory Layout

Array: [10, 20, 30, 40, 50]
Index:  0   1   2   3   4
Memory: [10][20][30][40][50]  <- Contiguous memory blocks
        ^
    Base Address

Address Calculation: Address = Base_Address + (Index × Element_Size)

Array Operations

Complete implementation: `Data Structures/Linear/Array/Array.java`

public class Array {

    public static void main(String[] args) {
        // Initialize an array with a fixed size and some elements
        int[] arr = new int[10];
        int nElems = 5;  // current number of elements in the array
        arr[0] = 10;
        arr[1] = 20;
        arr[2] = 30;
        arr[3] = 40;
        arr[4] = 50;

        // Display the array
        System.out.println("Initial Array:");
        displayArray(arr, nElems);

        // Search for an element
        int searchKey = 30;
        System.out.println("\nSearching for element " + searchKey + ":");
        searchArray(arr, nElems, searchKey);

        // Insert a new element
        int newValue = 60;
        System.out.println("\nInserting element " + newValue + ":");
        nElems = insertElement(arr, nElems, newValue);
        displayArray(arr, nElems);

        // Insert element at a specific position
        int insertPos = 2;  // insert at position 2 (third element)
        newValue = 25;
        System.out.println("\nInserting element " + newValue + " at position " + insertPos + ":");
        nElems = insertElementAtPosition(arr, nElems, newValue, insertPos);
        displayArray(arr, nElems);

        // Delete an element
        int deleteKey = 40;
        System.out.println("\nDeleting element " + deleteKey + ":");
        nElems = deleteElement(arr, nElems, deleteKey);
        displayArray(arr, nElems);
    }

    // Method to display the array
    public static void displayArray(int[] arr, int nElems) {
        for (int j = 0; j < nElems; j++) {
            System.out.print(arr[j] + " ");
        }
        System.out.println();
    }

    // Method to search for an element in the array
    public static void searchArray(int[] arr, int nElems, int searchKey) {
        int j;
        for (j = 0; j < nElems; j++) {
            if (arr[j] == searchKey) {
                System.out.println("Found element " + searchKey + " at index " + j);
                break;
            }
        }
        if (j == nElems) {
            System.out.println("Element " + searchKey + " not found.");
        }
    }

    // Method to insert an element at the end of the array
    public static int insertElement(int[] arr, int nElems, int newValue) {
        if (nElems < arr.length) {
            arr[nElems] = newValue;
            nElems++;
        } else {
            System.out.println("Array is full, cannot insert new element.");
        }
        return nElems;
    }

    // Method to insert an element at a specific position
    public static int insertElementAtPosition(int[] arr, int nElems, int newValue, int pos) {
        if (nElems < arr.length && pos <= nElems) {
            for (int k = nElems; k > pos; k--) {
                arr[k] = arr[k - 1];
            }
            arr[pos] = newValue;
            nElems++;
        } else {
            System.out.println("Cannot insert at this position.");
        }
        return nElems;
    }

    // Method to delete an element from the array
    public static int deleteElement(int[] arr, int nElems, int searchKey) {
        int j;
        for (j = 0; j < nElems; j++) {
            if (arr[j] == searchKey) {
                break;
            }
        }
        if (j == nElems) {
            System.out.println("Element " + searchKey + " not found.");
            return nElems;
        } else {
            for (int k = j; k < nElems - 1; k++) {
                arr[k] = arr[k + 1];
            }
            nElems--;
            return nElems;
        }
    }
}

1. 🔍 Display Operation

Print all elements in the array.

public static void displayArray(int[] arr, int nElems) {
    for (int j = 0; j < nElems; j++) {
        System.out.print(arr[j] + " ");
    }
    System.out.println();
}

Time Complexity: O(n) | Space Complexity: O(1)

2. 🔍 Search Operation

Find whether a specific element exists in the array.

public static void searchArray(int[] arr, int nElems, int searchKey) {
    int j;
    for (j = 0; j < nElems; j++) {
        if (arr[j] == searchKey) {
            break;
        }
    }
    if (j == nElems) {
        System.out.println("Element " + searchKey + " not found");
    } else {
        System.out.println("Element " + searchKey + " found at index " + j);
    }
}

Time Complexity: O(n) | Space Complexity: O(1)

3. ➕ Insertion Operations

Insert at End

public static int insertElement(int[] arr, int nElems, int newValue) {
    if (nElems < arr.length) {
        arr[nElems] = newValue;
        return nElems + 1;
    } else {
        System.out.println("Array is full!");
        return nElems;
    }
}

Insert at Specific Position

public static int insertElementAtPosition(int[] arr, int nElems, int newValue, int position) {
    if (nElems >= arr.length || position > nElems || position < 0) {
        System.out.println("Cannot insert at this position");
        return nElems;
    }

    // Shift elements to the right
    for (int k = nElems; k > position; k--) {
        arr[k] = arr[k - 1];
    }

    arr[position] = newValue;
    return nElems + 1;
}

Time Complexity:

At end: O(1)
At position: O(n) due to shifting

4. ➖ Deletion Operation

Remove an element and shift remaining elements to fill the gap.

public static int deleteElement(int[] arr, int nElems, int deleteKey) {
    int j;

    // Find the element
    for (j = 0; j < nElems; j++) {
        if (arr[j] == deleteKey) {
            break;
        }
    }

    if (j == nElems) {
        System.out.println("Element " + deleteKey + " not found");
        return nElems;
    } else {
        // Shift elements to the left
        for (int k = j; k < nElems - 1; k++) {
            arr[k] = arr[k + 1];
        }
        return nElems - 1;
    }
}

Time Complexity: O(n) | Space Complexity: O(1)

Implementation

The complete source implementation is included earlier in this lesson.

Our implementation demonstrates:

Array creation and initialization
All fundamental operations (display, search, insert, delete)
Error handling for edge cases
Memory-efficient operations

Creating Arrays in Java

// Method 1: Declare then allocate
int[] intArray;
intArray = new int[10];

// Method 2: Combined declaration and allocation
int[] intArray = new int[10];

// Method 3: Declaration with initialization
int[] intArray = {10, 20, 30, 40, 50};

Complexity Analysis

Operation	Time Complexity	Space Complexity	Notes
Access by Index	O(1)	O(1)	Direct memory access
Search	O(n)	O(1)	Linear search required
Insert at End	O(1)	O(1)	If space available
Insert at Position	O(n)	O(1)	Requires shifting
Delete	O(n)	O(1)	Requires shifting
Display All	O(n)	O(1)	Must visit each element

Advantages & Disadvantages

✅ Advantages

Direct Access: O(1) random access using index
Memory Efficiency: Minimal memory overhead
Cache Performance: Contiguous memory improves cache hits
Simplicity: Easy to understand and implement
Predictable Performance: Known time complexities

❌ Disadvantages

Fixed Size: Cannot grow or shrink dynamically
Insertion/Deletion Cost: O(n) for middle operations due to shifting
Memory Waste: May allocate more than needed
No Built-in Bounds Checking: Risk of array index out of bounds
Homogeneous Only: Cannot store different data types

Study Notes for Students

🎯 Key Concepts to Master

1. Memory Model Understanding

Visualize how arrays are laid out in memory
Understand address calculation: base + index × size
Appreciate why random access is O(1)

2. Index Manipulation

Arrays are 0-indexed in most languages
Last valid index is length - 1
Common off-by-one errors and how to avoid them

3. Shifting Operations

Right Shift: For insertion (start from the end)
Left Shift: For deletion (start from deletion point)
Why shifting makes insertion/deletion O(n)

4. Array Bounds

Always check bounds before access
Understand the difference between array size and current elements
Use a separate variable to track actual elements

📖 Study Patterns

Array Traversal Patterns

// Forward traversal
for (int i = 0; i < arr.length; i++) { /* process arr[i] */ }

// Backward traversal
for (int i = arr.length - 1; i >= 0; i--) { /* process arr[i] */ }

// Enhanced for loop (read-only)
for (int element : arr) { /* process element */ }

Common Array Algorithms

Linear Search: Sequential searching
Binary Search: Efficient search in sorted arrays
Two Pointers: For problems requiring comparison from both ends
Sliding Window: For subarray problems

🧩 Problem-Solving Strategies

When to Use Arrays

✅ Known maximum size at compile time
✅ Frequent random access needed
✅ Simple data storage requirements
✅ Memory efficiency is important

When to Consider Alternatives

❌ Dynamic resizing needed → Use ArrayList/Vector
❌ Frequent insertions/deletions → Use LinkedList
❌ Need fast search → Use HashMap/HashSet
❌ Need sorted data → Use TreeSet/PriorityQueue

Practice Problems

🟢 Beginner Level

Find the maximum/minimum element in an array
Calculate sum and average of array elements
Reverse an array in-place
Check if array is sorted
Count occurrences of each element

🟡 Intermediate Level

Rotate array by K positions (left/right)
Remove duplicates from sorted array
Merge two sorted arrays
Find second largest element
Implement array-based stack/queue

🔴 Advanced Level

Maximum subarray sum (Kadane’s algorithm)
Product of array except self
Trapping rainwater problem
Next greater element
Sliding window maximum

Searching Algorithms - Linear and Binary Search
Sorting Algorithms - Array-based sorting
Dynamic Arrays - Resizable arrays
Linked Lists - Alternative linear structure
Stacks - Array-based implementation
Queues - Array-based implementation

Real-World Applications

Database Systems: Storage of records in table rows
Image Processing: Pixel data representation
Scientific Computing: Matrix operations and numerical data
Game Development: Game boards, sprite arrays
System Programming: Buffer management, memory pools

Java Code Examples for Array Operations

The complete source implementation is included earlier in this lesson.

The following documentation outlines basic array operations in Java, such as displaying, searching, inserting, and deleting elements in an array. These operations are fundamental and demonstrate how to manipulate arrays using Java. While your original source files focus more on advanced topics like recursive methods, binary trees, algorithm analysis, and linked lists, here we cover basic array manipulation for a clearer understanding of array handling.

1. Displaying an Array

To display the contents of an array, you can use a for loop to iterate over each element and print it. Here’s a sample code snippet that prints all the elements of an array:

for (int j = 0; j < nElems; j++) {  // display items
  System.out.print(arr[j] + " ");
}
System.out.println("");

Explanation:

The loop iterates through each element of the array arr.
nElems represents the number of elements currently in the array.
Each element (arr[j]) is printed followed by a space, and at the end, a newline (System.out.println("")) is added to move to the next line after the array is printed.

2. Searching for an Element in an Array

To search for an element within an array, the following example shows how to find a specific value (searchKey) and report whether the element is found:

int searchKey = 66;  // The element we are searching for
int j;

for (j = 0; j < nElems; j++) {  // iterate over elements
  if (arr[j] == searchKey) {  // check if the current element matches the search key
    break;  // exit the loop if found
  }
}
if (j == nElems) {  // check if we reached the end without finding the element
  System.out.println("Can’t find " + searchKey);
} else {
  System.out.println("Found " + searchKey);
}

Explanation:

We loop through the array using j as the index to compare each element to the searchKey.
If the element is found, the loop breaks. If the loop completes without finding the key, it means the element is not in the array.

3. Inserting an Element into an Array

To insert a new element into an array, we need to ensure there’s space available, and we may need to shift elements to make room for the new value. Here’s how we do that:

int newValue = 33;
if (nElems < arr.length) {  // Check if there's space in the array
  arr[nElems] = newValue;  // Insert the new element at the end
  nElems++;  // Increment the number of elements
} else {
  System.out.println("Array is full, cannot insert new element");
}

Explanation:

The if condition checks whether there’s space left in the array (nElems < arr.length).
If space is available, the new element (newValue) is inserted at the end of the array, and nElems (the count of current elements) is incremented.

For inserting at a specific position, you need to shift existing elements:

int newValue = 33;
int insertPos = 5;  // The position where we want to insert

if (nElems < arr.length && insertPos <= nElems) {  // Ensure valid insert
  for (int k = nElems; k > insertPos; k--) {  // Shift elements to the right
    arr[k] = arr[k - 1];
  }
  arr[insertPos] = newValue;  // Insert the new value
  nElems++;
} else {
  System.out.println("Cannot insert at this position.");
}

Explanation:

The loop shifts elements to the right starting from the end of the array to make room for the new value at insertPos.
The new value is then inserted, and the element count (nElems) is updated.

4. Deleting an Element from an Array

To delete an element from the array, we find the element, shift the remaining elements to the left to fill the gap, and update the element count:

int searchKey = 55;  // The element to delete
int j;

for (j = 0; j < nElems; j++) {  // Search for the element to delete
  if (arr[j] == searchKey) {
    break;
  }
}
if (j == nElems) {  // Element not found
  System.out.println("Can’t find " + searchKey);
} else {  // Element found, shift the elements
  for (int k = j; k < nElems - 1; k++) {
    arr[k] = arr[k + 1];  // Shift elements to the left
  }
  nElems--;  // Decrease the count of elements
}

Explanation:

First, the element to be deleted is searched for. If found, all the elements after it are shifted to the left to fill the gap.
The total number of elements is decreased to reflect the deletion.