--- title: "Arrays - Fundamental Data Structure" lastModified: "2026-10-07T16:05:18+05:30" --- 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](#key-characteristics) - [Memory Layout](#memory-layout) - [Array Operations](#array-operations) - [Implementation](#implementation) - [Complexity Analysis](#complexity-analysis) - [Advantages & Disadvantages](#advantages--disadvantages) - [Study Notes](#study-notes-for-students) - [Practice Problems](#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` ```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. ```java 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. ```java 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 ```java 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 ```java 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. ```java 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 ```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** 1. **Direct Access**: O(1) random access using index 2. **Memory Efficiency**: Minimal memory overhead 3. **Cache Performance**: Contiguous memory improves cache hits 4. **Simplicity**: Easy to understand and implement 5. **Predictable Performance**: Known time complexities ### ❌ **Disadvantages** 1. **Fixed Size**: Cannot grow or shrink dynamically 2. **Insertion/Deletion Cost**: O(n) for middle operations due to shifting 3. **Memory Waste**: May allocate more than needed 4. **No Built-in Bounds Checking**: Risk of array index out of bounds 5. **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 ```java // 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 1. **Linear Search**: Sequential searching 2. **Binary Search**: Efficient search in sorted arrays 3. **Two Pointers**: For problems requiring comparison from both ends 4. **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** 1. Find the maximum/minimum element in an array 2. Calculate sum and average of array elements 3. Reverse an array in-place 4. Check if array is sorted 5. Count occurrences of each element ### 🟑 **Intermediate Level** 1. Rotate array by K positions (left/right) 2. Remove duplicates from sorted array 3. Merge two sorted arrays 4. Find second largest element 5. Implement array-based stack/queue ### πŸ”΄ **Advanced Level** 1. Maximum subarray sum (Kadane's algorithm) 2. Product of array except self 3. Trapping rainwater problem 4. Next greater element 5. Sliding window maximum ## Related Topics - [**Searching Algorithms**](/docs/en/modules/data-structures-and-algorithms/algorithms) - Linear and Binary Search - [**Sorting Algorithms**](/docs/en/modules/data-structures-and-algorithms/algorithms) - Array-based sorting - **Dynamic Arrays** - Resizable arrays - [**Linked Lists**](/docs/en/modules/data-structures-and-algorithms/data-structures-linear-linked-list) - Alternative linear structure - [**Stacks**](/docs/en/modules/data-structures-and-algorithms/data-structures-linear-stack) - Array-based implementation - [**Queues**](/docs/en/modules/data-structures-and-algorithms/data-structures-linear-queue) - 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: ```java 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: ```java 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: ```java 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: ```java 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: ```java 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.