Array in Data Structures

What is an Array?

An array is a data structure with a fixed size that stores elements of the same type. Index numbers are used to access elements. Stored in contiguous memory spaces, the lowest memory address refers to the first element and the highest memory address corresponds to the last element.

What are the Types of Arrays?

Following are the types of arrays in data structure:

1. Single Dimensional Array (1-D)
2. Two-Dimensional Array (2-D)
3. Three-Dimensional Array (3-D)
4. Multi-Dimensional Array
5. Jagged Array

Single-Dimensional Array

A collection of elements of the same data type stored in a contiguous block of memory. Elements are stored only in rows.

Two-Dimensional Array

A two-dimensional array, often known as a matrix, is an array of arrays. It is composed of a grid of items that can be accessed using two indices. Elements are kept in a row and column manner. A matrix of size m x n, with m rows and n columns.

Three Dimensional Array 

An extension of the two-dimensional array that includes depth. A cube has rows, columns, and depth. Array elements are stored either rowwise or columnwise. 

Multi-Dimensional Array

A multi-dimensional array is a data structure that expands the concept of a one-dimensional array into two or more dimensions. It can be thought of as an array of arrays, with elements organized in rows and columns (plus additional dimensions in higher-dimensional arrays).

Jagged Array

An array collection in Java that has a variable number of elements in each array is called a jagged array. Jagged arrays are sometimes referred to as "ragged arrays" or "irregular arrays." They can be formed by defining the size of each array in the declaration.

Advantages of Arrays

• Constant time access: Each element is retrieved via index.
• Optimal memory use: There is no storage waste for links or additional information.
• Versatility: Can store any data type (integers, characters, strings, user-defined kinds).
• Flexibility: The foundation for building different data structures (stacks, queues, trees, graphs).
• Easy to remember: A single name identifies several data elements of the same type.

Disadvantages of Arrays

• Fixed-size: The array size is predetermined and cannot be modified after construction.
• Memory wastage: Unused space when there are fewer elements than the given size.
• Inefficient insertion/deletion: Shifts are necessary for insertion and deletion, particularly in big arrays.
• Homogeneous data: Homogeneous data only contains elements of the same data type.
• No built-in scaling: Some languages do not have built-in support, requiring complicated manual resizing logic.

Operations on Arrays in Data Structure

• Traversal: Access the array's items one at a time.
• Insertion: Inserts an element at the specified index.
• Deletion: Deletes the element at the specified index.
• Search: Locate an element using the supplied index or value.
• Update: Updates an element at the specified index.
• Sorting: Arrange components in either ascending or descending order.
• Merging: Combine two sorted arrays into a single sorted array.
• Order statistics: Determine the nth smallest and largest element in an array.

Complexity Analysis of Array Operations

Time Complexity

Space Complexity

Most array operations have a space complexity of O(1), except for resizing operations & certain insertions/deletions that may involve element shifting, resulting in O(n) space complexity.

Usage of Arrays

• Used to store many variables of the same type.
• Used to solve matrix problems.
• Used to implement sorting algorithms.
• Arrays also implement database records.
• Required for CPU scheduling.
• Used to implement different data structures like stacks, queues, heaps, hash tables, and so on.

Application of Arrays in Data Structures

• Storing and accessing data.
• Sorting and searching data.
• Implementing dynamic data structures.
• Image processing.
• Numerical computations.
• Games and simulations.

Access Elements of an Array in Data Structures

To access an array element, use its index number. The array index begins with 0. The last element's index is n-1.

Declare an Array

Arrays are commonly defined using square brackets and the size of the array as an input.

What is Array Bound Checking?

Array bound checking in data structures refers to determining whether an index used to access an array element is inside the array's valid range (from 0 to its size minus one). 

What is an Array List Integer?

An array list for integers is a resizable collection that holds a series of integer values. Unlike arrays, it dynamically adjusts its size to fit the items, allowing you to add or delete integers without specifying a size.