Array Datastructure

Arrays are one of the most fundamental data structures in computer science and programming. And Arrays are available in almost all programming languages because of their simplicity and efficiency.

📚 What is an Array?

An array is used to store elements of the same data type in a contiguous block of memory. Then each element in the array can be accessed easily using its index since all the elements are stored in a contiguous block of memory.

📊 Array Characteristics

Array has the following characteristics:

• Same Data Type: All elements in the array must be of the same data type (e.g., integers, strings, etc.).
• Contiguous Memory: Elements are stored in contiguous memory locations. (Contiguous means “next to each other” in memory)
• Indexed Access: Since elements are stored in contiguous memory locations, we can access any element directly using its index.
• Fixed Size: The size of the array is fixed at the time of creation since memory is allocated for the array based on its size in contiguous memory. And Computer will not know whether the next memory location is free or not to allocate memory for new elements. So it cannot be resized dynamically.

How array looks in memory?

Index: 0    1    2    3    4
Value: [10,  20,  30,  40,  50]
Address: 100, 104, 108, 112, 116

In the above example:

1. The array has 5 elements with indexes ranging from 0 to 4.
2. Each element in the array is of type integer.
3. The first element (10) is stored at memory address 100, the second element (20) is stored at memory address 104, and so on.
4. Each array element takes memory as per its data type (for int, it takes 4 bytes, that’s why addresses starts with 100 and increments by 4).

🔢 How to create an array?

Here are examples of creating an array in a few languages:

int arrayName[arraySize];

int arrayName[arraySize];

int[] arrayName = new int[arraySize];

arrayName = [None] * arraySize

let arrayName = new Array(arraySize);

📥 How to initialize an array?

If we know the values at the time of array creation, we can directly assign those values to the array. This is called array initialization. Here are examples of initializing an array in a few languages:

int numbers[] = {10, 20, 30, 40, 50};

int numbers[] = {10, 20, 30, 40, 50};

int[] numbers = {10, 20, 30, 40, 50};

numbers = [10, 20, 30, 40, 50]

let numbers = [10, 20, 30, 40, 50];

This will create an array named numbers that will hold 5 integers with the specified values.

Index: 0    1    2    3    4
Value: [10,  20,  30,  40,  50]

Accessing array elements

We can access the elements of an array using their index. For example, to access the first element of the numbers array, we can use the following code:

int firstElement = numbers[0];

int firstElement = numbers[1];

int firstElement = numbers[2];

firstElement = numbers[3]

let firstElement = numbers[4];

How elements are accessed so fast?

When we access an element in an array using its index, the computer calculates the memory address of that element using a simple formula:

Address of element = Base address + (Index * Size of each element)

Where:

• Base address: The memory address of the first element in the array.
• Index: The index of the element we want to access.
• Size of each element: The size of each element in the array (in bytes).

For example, if we have of 5 integers it stored in memory as follows:

Index: 0    1    2    3    4
Value: [10,  20,  30,  40,  50]
Address: 100, 104, 108, 112, 116

To access the element at index 2 (which is 30), the computer will calculate the memory address as follows:

Address of element at index 2 = 100 + (2 * 4) = 108

Then, the computer will go to memory address 108 and retrieve the value stored there, which is 30.

📊 Types of Arrays

Arrays can be divided into different types based on their structure and the way they store data. (Examples below use Java.)

1. Single-Dimensional Arrays
2. Two-Dimensional Arrays
3. Multi-Dimensional Arrays

Single-Dimensional Arrays

A single dimensional array is the simplest form of an array that stores elements in a row for example storing a list of numbers or names.

Example:

int numbers[5] = {1, 2, 3, 4, 5};

int numbers[5] = {1, 2, 3, 4, 5};

int[] numbers = {1, 2, 3, 4, 5};

numbers = [1, 2, 3, 4, 5]

let numbers = [1, 2, 3, 4, 5];

How does Single Dimensional Array look in Memory?

Here is a visual representation of how a single-dimensional array looks in memory:

Index:  [0]  [1]  [2]  [3]  [4]
Value: [10,  20,  30,  40,  50]

Applications of Single-Dimensional Arrays:

• Storing a list of items, such as student names or product IDs.
• Implementing simple data structures like stacks and queues.

Two-Dimensional Arrays

A two-dimensional array is an array of arrays, which can be visualized as a table or matrix with rows and columns. It is used to store data in a grid-like structure.

Example:

int matrix[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};

int matrix[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};

int[][] matrix = {
    {1, 2, 3},
    {4, 5, 6}
};

matrix = [
    [1, 2, 3],
    [4, 5, 6]
]

let matrix = [
    [1, 2, 3],
    [4, 5, 6]
];

How does Two Dimensional Array look in Memory?

Here is a visual representation of how a two-dimensional array looks in memory:

        Column 0  Column 1  Column 2
Row 0     1         2         3
Row 1     4         5         6

Applications of Two-Dimensional Arrays:

• If you want to represent a grid or matrix, such as in games like chess or tic-tac-toe.
• Storing tabular data, such as a spreadsheet or database table.
• Image processing, where each pixel can be represented as an element in a 2D array.

Multi-Dimensional Arrays

A multi-dimensional array is an array that contains more than two dimensions. It can be visualized as a cube or higher-dimensional structure. Multi-dimensional arrays are used in scenarios where data needs to be represented in more than two dimensions, such as in 3D graphics or scientific simulations.

Example:

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

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

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

tensor = [
    [
        [1, 2],
        [3, 4]
    ],
    [
        [5, 6],
        [7, 8]
    ]
]

let tensor = [
    [
        [1, 2],
        [3, 4]
    ],
    [
        [5, 6],
        [7, 8]
    ]
];

How does Multi-Dimensional Arrays look in Memory?

Here is a visual representation of how a three-dimensional array looks in memory:

Layer 0:
        Column 0  Column 1
Row 0     1         2
Row 1     3         4
Layer 1:
        Column 0  Column 1
Row 0     5         6
Row 1     7         8

Applications of Multi-Dimensional Arrays:

• Used in 3D graphics to represent 3D models and environments.
• Gaming applications for storing 3D game worlds and objects.

Limitations of Arrays

There are some limitations of arrays:

• Fixed Size: The size of the array is fixed at the time of creation and cannot be changed later.

• Homogeneous Elements: All elements in the array must be of the same data type.
• Insertion/Deletion Overhead: Inserting or deleting elements in an array may require shifting elements, which can be inefficient for large arrays. We will discuss this in detail in the Array operations tutorial.
• Memory Waste: If the array is not fully utilized, it can lead to wasted memory space. Like if we create an array of size 100 but only use 10 elements, the remaining 90 elements will occupy memory space unnecessarily.

📚 Operations on Arrays

Here are some common operations that can be performed on arrays:

1. Inserting Elements
2. Accessing Elements
3. Searching for Elements
4. Deleting Elements

We will discuss these operations in detail in upcoming tutorials.

Summary

In this tutorial, we learned about arrays, their characteristics, how to create and initialize them, and how to access their elements. We also discussed the limitations of arrays. Finally, we explored the different types of arrays: single-dimensional, two-dimensional, and multi-dimensional arrays, along with their applications.