Array Data Structure

An array is a fundamental data structure used to efficiently store and manage a collection of elements by using a continuous block of computer memory. This memory is divided into a series of sequential compartments, or slots and each slot can store a single item of information. The items stored within the array can be accessed or modified instantly by using their unique identifiers, known as indices or slot numbers.

Below are some of the key features of an Array Data Structure:

Contiguous Memory: Arrays allocate a block of memory that is contiguous, meaning the elements are stored in adjacent memory locations. This property enables quick access to individual elements using their index numbers.
Fixed Size: Arrays have a predetermined size defined at the time of creation. Once the size is set, it remains constant throughout the program execution. This fixed size ensures predictable memory allocation and efficient memory management.
Random Access: Arrays support direct access to elements based on their index. By specifying the index value, we can instantly retrieve or modify the object stored in the corresponding slot. This feature allows for quick and efficient data retrieval.

Structure of an Array

Below is how the structure of an array looks like:

A continuous section of memory space (the area highlighted in blue) is allocated for an Array a. This continuous memory space is further divided into 6 slots where each slot can store an element inside it. Here, the allocated size of the array is 6 (Since the memory is allocated to store a maximum of 6 items). However the actual size of all elements stored in the array is 4, since only the first 4 locations are used for storage.

Generally, all the slots in the arrays are fully used without any vacancies. In case if the array needs to be partially used, there has to be a variable which stores the total number of slots which are currently in use. This allows us to know from which index empty slots start from. For example a variable maxLength can store the maximum number of elements the array can store and length variable to store the actual number of elements actually stored in the array.

Each slot/element in the array is numbered starting from 0. So the first slot is identified by number 0, the second slot by number 1, the third slot by number 2 etc. So in order to access the third item stored in the array, we can use the corresponding slot’s number like this: a[2]. The number used to identify a slot is termed as the index of that slot. So for the second slot/item, the index is 1, for the third slot/item, the index is 2 etc. You can think of an array as a line of houses side by side, with the index as the address assigned to each house.

Example situations when an Array Necessary

Any program running on a computer requires storing and accessing of data temporarily. For example, if we write a program to add two numbers, we need to take input the two numbers to add and store them temporarily before adding them and displaying the result.

If the operation we need to do is simple and requires only a few variables, we can store the values in separate variables and perform the operation. For example, if we wish to add two numbers, we can initialize two numbers a and b and create a formula a+b to add the numbers.

But what if we need to add 10 numbers? sure we can initialize 10 variables with names as a1, a2, a3 .. to a10, store all numbers in those variables and add them up using the expression result = a1 + a2 + a3 + ... a10. But what if the number of numbers to add change dynamically? or if the number of numbers to add is very large? This is where an array is really useful.

We can initialize an array to store any number of items we desire and then we can iterate / go through each slot in the array and access the item. For example, if we wish to store 100 items, we can initialize an array like items[100] and start filling each item starting from index 0. So we fill items[0] first, items[1] next and finally items[99]. After filling all the items, we can go through each item and perform required operation like addition, finding the maximum element etc.

Declaring an Array and Accessing Stored Elements

Below are code examples in various programming languages that demonstrate how to create and initialize an array, as well as how to access and modify individual elements within the array.


#include <stdio.h>

int main() {
    // Declare and initialize an integer array
    int numbers[] = {1, 2, 3, 4, 5};

    // Access individual elements by index
    printf("Element at index 2: %d\n", numbers[2]);
    // Element at index 2 is 3

    // Update an element by index
    numbers[2] = 10;

    // Print the updated element
    printf("Updated element at index 2: %d\n", numbers[2]);
    // After the update, element at index 2 is 10

    return 0;
}


# Declare and initialize a list (Python's version of an array)
numbers = [1, 2, 3, 4, 5]

# Access individual elements by index
print("Element at index 2:", numbers[2])
# Element at index 2 is 3

# Update an element by index
numbers[2] = 10

# Print the updated element
print("Updated element at index 2:", numbers[2])
# After the update, element at index 2 is 10


// Declare and initialize an array
let numbers = [1, 2, 3, 4, 5];

// Access individual elements by index
console.log("Element at index 2:", numbers[2]);
// Element at index 2 is 3

// Update an element by index
numbers[2] = 10;

// Print the updated element
console.log("Updated element at index 2:", numbers[2]);
// After the update, element at index 2 is 10


public class ArrayExample {
    public static void main(String[] args) {
        // Declare and initialize an integer array
        int[] numbers = {1, 2, 3, 4, 5};

        // Access individual elements by index
        System.out.println("Element at index 2: " + numbers[2]);
        // Element at index 2 is 3

        // Update an element by index
        numbers[2] = 10;

        // Print the updated element
        System.out.println("Updated element at index 2: " + numbers[2]);
        // After the update, element at index 2 is 10
    }
}

Basic Operations on an Array Data Structure

Following are some of the fundamental operations which can be performed on an Array (Click on the title of each operation to learn more about it):

Access/Update: This operation involves retrieving or modifying the value of an element at a specific index in the array. It is typically a constant time O(1) operation, as arrays provide direct access to elements using their indices.
Traversal/Iteration: Traversal/Iteration refers to the process of visiting each element in the array sequentially. This operation is commonly used to perform actions on all elements or to find specific elements based on certain conditions. Traversal usually has a time complexity of O(n), where n is the number of elements in the array.
Insertion: Insertion is the process of adding a new element to the array. This can be done at the beginning, end, or at a specific position within the array. The time complexity varies depending on the insertion position and whether the array needs to be resized.
Removal/Deletion: This operation involves removing an element from the array. Like insertion, deletion can be performed at the beginning, end, or at a specific position. The time complexity also varies based on the deletion position and whether subsequent elements need to be shifted.
Search For an Element: Searching is the process of finding a specific element or set of elements in the array that match certain criteria. Linear search, with O(n) time complexity, is commonly used for unsorted arrays, while binary search, with O(log n) time complexity, can be used for sorted arrays.

Basic Problems on Array Data Structure

Below are some of the problems involving Arrays (Click on the title of each problem to learn more about it):

Create and Fill Array: This involves initializing an array with a specific size and populating it with elements with inputs from command line.
Linear Search: This is a simple search algorithm that checks each element of the array sequentially until a match is found or the entire array has been searched. It’s straightforward but can be inefficient for large arrays.
Sum Elements: This problem requires adding up all the elements in an array to calculate their total sum. It’s a common operation used in various applications, from basic statistics to more complex algorithms.
Finding Maximum and Minimum: This involves traversing the array to find the largest and smallest elements. It’s useful for understanding the range of values in a dataset and is often a building block for more complex algorithms.
Reverse an Array: This operation involves flipping the order of elements in an array, so the first element becomes the last, the second becomes the second-to-last, and so on. It’s a common operation that can be achieved through various methods.
Rotate an Array: This involves shifting all elements of an array by a certain number of positions, either to the left or right. Elements that “fall off” one end of the array are reinserted at the other end. It’s useful in various applications, including image processing and data manipulation.
Sort an Array of 0s and 1s: This is a specific sorting problem where an array contains only two types of elements (0s and 1s). The goal is to arrange the array so that all 0s come before all 1s. It’s a simplified version of sorting that can be solved more efficiently than general sorting algorithms.

Advanced Array Concepts

Multi-Dimensional Arrays: Multi-dimensional arrays are data structures that store elements in a grid-like format with two or more dimensions. They can be thought of as “arrays of arrays.” The most common type is a two-dimensional array, which resembles a table with rows and columns. For example, a 3x3 grid for a tic-tac-toe game could be represented as a multi-dimensional array. These arrays are useful for representing complex data relationships, such as matrices in mathematics, pixel data in images, or game boards. They allow for efficient organization and access of data that has a natural grid-like structure.
Dynamic Arrays: Dynamic arrays are a type of array that can change size during program execution. Unlike static arrays, which have a fixed size determined during creation, dynamic arrays can grow or shrink as needed. This flexibility makes them particularly useful when the amount of data to be stored is not known in advance. Dynamic arrays typically start with an initial capacity and automatically resize when more space is needed, often by creating a new, larger array and copying the existing elements. Many programming languages provide dynamic array implementations, such as ArrayList in Java or vector in C++.