If you’re learning programming, one of the first and most fundamental data structures you’ll encounter is the array. Arrays are incredibly useful and show up all the time in code, so having a solid grasp of how they work is essential. In this article, we’ll take an in-depth look at what arrays are, how they work under the hood, and some key operations and concepts. Let’s jump in!

What is an array ?

Fundamentally, an array is an abstract data type (ADT) that stores a collection of elements, each of which is identified by an index. An ADT is a mental model that defines a set of properties and operations that a data structure must have. For an array for example we want the index is a non-negative integer and that integer will represent the position of an element in the array. We also want to have some operations on the array, such as accessing an element, updating an element, deleting an element, and searching for an element.

Even though we define an array as ADT, we will use C programming language to demonstrate the concepts.

Array (ADT) Properties

1. Fixed size

An array has a fixed size. Once we define the size of an array, we cannot change it. If we need more slots in the array, then we have to create a new array, copy the elements from the old array to the new array, and then delete the old array.

int arr[5]; // array of size 5

// we cannot change the size of the array
arr[6] = 10; // invalid

2. Homogeneous elements

An array can only store elements of the same type. These types can vary based on how the array is implemented in a programming language. For example, an array in C can store elements of the same data type, while an array in Python can store elements of different data types. In our case, we will consider an array that stores elements of the same data type which we will define when we create the array.

int arr_of_ints[5]; // array of integers
char arr_of_chars[5]; // array of characters

arr_of_ints[0] = 10;
arr_of_ints[1] = 20;
//..

arr_of_chars[0] = 'a';
arr_of_chars[1] = 'b';
//..

3. Contiguous memory

All the elements of an array are stored in memory sequentially. This means that the elements are stored one after the other in memory and if we know the address of the first element, we can calculate the address of any element in the array.

int arr[5]; // array of size 5

// address of the first element
int *firstElement = &arr[0];

// access the second element
int *secondElement = firstElement + 1;
// access the third element
int *thirdElement = firstElement + 2;

Array (ADT) Operations

We will define some of the basic operations that we can perform on an array ADT. These are like the basic building blocks of an array. Of course, there are more operations that we can perform on an array, but these are the most common ones.

1. Accessing an element (O(1))

Given an array and an index, we can access the element via the index. The index represents the position of the element in the array starting from 0. Time complexity of this operation is O(1).

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

int firstElement = arr[0]; // element = 10
int secondElement = arr[1]; // element = 20
int lastElement = arr[4]; // element = 50

2. Updating an element (O(1))

Given an array and an index, we can update the element at the given index. Time complexity of this operation is O(1).

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

arr[0] = 100; // arr = {100, 20, 30, 40, 50}
arr[4] = 500; // arr = {100, 20, 30, 40, 500}

3. Deleting an element (O(n))

Given an array and an index, we can delete the element at the given index by shifting all the elements to the right of the index one position to the left.

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

// delete element at index 2
for (int i = 2; i < 4; i++) {
    arr[i] = arr[i + 1];
}

4. Searching for an element (O(n))

Given an array and an element, we can search for the element in the array by iterating over all the elements in the array.

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

int searchElement = 30;

for (int i = 0; i < 5; i++) {
    if (arr[i] == searchElement) {
        // element found
    }
}

Conclusion

In this article, we learned about arrays, a fundamental data structure in programming with its properties and operations. We also learned that arrays are an abstract data type that stores elements of the same type in contiguous memory and that we can perform operations like accessing, updating, deleting, and searching for elements in an array.

Arrays are the most basic data and fundamental data structure in programming. To use it efficiently, we need to understand how it works and how to perform operations on it and what are the limitations of it.