An array holds a fixed number of similar elements that are stored under one name. These elements are stored in contagious memory locations. It is one of the simplest data structures. Most modern programming languages have arrays built-in by default.
The reason why we use arrays is that every element can be accessed by its index value. This has several advantages over storing a bunch of variables.
For example: Consider we have to implement a system to store the age of all employees in an office. There is the traditional way with variables.
One can create a variable for each employee in the office. Let’s say the office has only 3 employees. Fairly easy right? Just declare 3 variables: emp1_age , emp2_age and emp3_age .
When new recruitments come in, we sit down to create more variables. Maintaining a system like this gets tedious. Imagine one new employee and the whole system code has to be modified.
Accessing each variable would also be a headache. It is stupid to sum 20 variables by hand to calculate the average age of the employees.
An array data structure tries to solve these problems.
One of the properties of arrays is that it holds the same kind of data under one name.
For this example, the array can hold all the ages of the employees under one name, like employees_age . These are all of the integer type.
The second property of arrays is that it stores each element in a continuous block which can be accessed using its index.
Every employee’s age can be accessed by iterating through the indices of the array. This can be used to easily access all values serially by looping through them. The function to calculate average becomes much easier to implement as the name of the array is constant and only the index is changing.
Let’s see how an array is declared and used.
An array has to be declared before it can be used. In C, declaring an array means specifying the following:
Syntax Used
An array can be declared in C by using the following syntax:
type name[size];
For example, an array of marks of a class of 100 students can be created using:
int marks[100];
There are 2 ways to assign elements to an array:
The values of the elements can be assigned while declaring the array. If some of the values are not explicitly defined, they are set to 0.
int marks[10] = ;
By default, an array is created whenever memory is available at any random location. We do not know what information that random location of memory will contain, as any other program could have used that memory previously.
If array elements are not initialized while creation, then accessing them directly they would result in such garbage values.
Therefore, it is always recommended to empty the elements or assign values to it if a calculation is to be performed on the array.
int ages[10]; // accessing array without assigning elements first for(int i = 0; i < 10; i++) printf("\n arr[%d] = %d", i, ages[i]);
Each element of the array can be accessed using its index. The indexing in an array generally starts with 0, which means that the first element is at the 0th index. Subsequently, the last element of the array would be at the (n-1)th index. This is known as 0-based indexing.
The indexing of the array may also be different by using any other base. These are known as n-based indexing.
Accessing all the elements is possible by using a simple for-loop going through all the indices in the array.
for(int i = 0; i < arraySize; i++) printf("\n arr[%d] = %d", i, arr[i]);
Example: Values are first being assigned and then displayed from the array.
int id[10]; // assigning values using a loop for (int i = 0; i < 10; i++) < printf("\nEnter an id: "); scanf("%d", &id[i]); >// displaying the entered ids for (int i = 0; iMaintaining the order of an array while inserting or deleting requires manipulating the others already present in the array. This is one of the disadvantages, as such operations can be costly on larger arrays.
At the end
Inserting an element at the end of the array is easy provided the array has enough space for the new element. The index of the last element of the array is found out and the new element is inserted at the index + 1 position.
At any other position
An element can be inserted in between at any position by shifting all elements from that position to the back of the array. The element to be inserted is then inserted at the required position.
void insert_position(int arr[]) < int i = 0, pos, num; printf("Enter the number to be inserted : "); scanf("%d", &num); printf("Enter position at which the number is to be added :"); scanf("%d", &pos); for (i = n-1; i>= pos; i--) arr[i+1] = arr[i]; arr[pos] = num; n = n + 1; // increase total number of used positions display_array(arr); >
At the end
Deleting an element at the end of the array is equally easy provided there is some element to begin with (not an empty array). The index of the last element is found out and this element is deleted.
At any other position
An element can be deleted at any index by deleting the element at that position and then moving up all the elements from the back of the array to the front to fill up the position of the deleted element.
void delete_position(int arr[]) < int i, pos; printf("\nEnter the position where the number has to be deleted: "); scanf("%d", &pos); for (i = pos; i < n-1; i++) arr[i] = arr[i+1]; n = n - 1; // decrease total number of used positions display_array(arr); >
An array may have more than one dimension to represent data. These are known as multidimensional arrays. The elements in these arrays are accessed using multiple indices.
A two dimensional array can be considered as an array within an array. It can be visualised as a table, having a row and a column. Each item in the table can be accessed using 2 indices corresponding to the row and column.
A 2D array is declared using 2 parameters:
type name[max_size_x][max_size_y]
The max_size_x and max_size_y are the max values each dimension can store.
A three dimensional array similarly can be visualised as a cube. Each item can be accessed using 3 indices corresponding to the 3D position.
Example: Every block of a Rubik’s Cube can be represented by a three dimensional array of size 3 x 3 x 3.
A 3D array is declared using 2 parameters:
type name[max_size_x][max_size_y][max_size_z];
The max_size_x, max_size_y and max_size_z are the max values each dimension can store.
Since an array stores all its data elements in consecutive memory locations, storing just the base address, that is, the address of the first element is sufficient. The address of other elements can be then calculated using the base address.
A simple formula consisting of the size of the element and the lower bound is used.
A[i] = base_address(A) + size_of_element(i – lower_bound)
The lower bound is the smallest index in the array. Similarly, an upper bound is the largest index in the array. In C programming, the lower bound value may be omitted as it is generally 0.
The elements in a two dimensional array can be stored using 2 representations and their addresses can be calculated using the respective formulae.
In this form, the elements are stored column by column. m elements of the first column are stored in the first m locations, elements of the second column element are stored in the next m locations, and so on.
Address(A[I][J]) = base_address + widthIn this form, the elements are stored row by row. n elements of the first row are stored in the first n locations, elements of the second row elements are stored in the next n locations, and so on.
Address(A[I][J]) = base_address + widthAny array element could be accessed directly through its index. Hence the access time is constant O(1).
Searching for a given value through the array requires iterating through each element in the array until the element is found. This is assuming that linear search is used (which is the most basic type of search to find any element). This makes the search time O(n).
The other more efficient search algorithm, binary search could be used to search in O(log n) time but it requires the array to be sorted beforehand.
Inserting an element in between 2 elements in an array involves shifting all the elements to the right by 1. This means that at most all the elements have to be shifted right (insertion at the beginning of the array), hence the complexity of the insert operation in O(n).
Deleting an element in between 2 elements in an array involves shifting all the elements to the left by 1. This means that at most all the elements have to be shifted left (deletion at the beginning of the array), hence the complexity of the delete operation in O(n).
An array only takes the space used to store the elements of the data type specified. This means that for storing n elements the space required is O(n).
Arrays have various advantages over other more complex data structures.
Shorter
Longer
HackerEarth provides excellent beginner competitive questions when learning about data structures. If you are comfortable with these questions, you may increase the difficulty and attempt those. Try some questions here.
LeetCode has a good number of arrays with various difficulty levels. These may be attempted after solving the HackerEarth questions. Try some questions here.