Introduction to Arrays
Types of indexing in an array :
- 0 (zero-based indexing): The first element of the array is indexed by a subscript of 0.
- 1 (one-based index): The first element of an array is indexed by a subscript of 1.
- n (n-based index): The base index of the array can be selected freely. Typically, programming languages allow n-based indexing. Negative index values and other scalar data types such as calculations, or characters can be used as array indexes.
Properties of array
Some of the properties of the array are listed below-
- Each element in an array is of the same data type and carries the same size that is 4 bytes.
- Elements in the array are stored at contiguous memory locations from which the first element is stored at the smallest memory location.
- The elements of the array can be accessed at random because you can calculate the address of each element of the array and the size of the data element with the given base address.
Representation of an array
We can represent arrays in different ways in different programming languages. For example, let us see the declaration of an array in C language -
As per the example above, some of the following are important points -
- Index starts with 0.
- The array's length is 10, which means we can store 10 elements.
- Each element in the array can be accessed via its index.
Why are arrays required?
Arrays are useful because -
- Value arrays are easy to find and find in arrays.
- Arrays are best for quick and easy processing of multiple values.
Arrays are good for storing multiple values in a single variable - In computer programming, most cases require storing a large number of data of a similar type. To store this amount of data, we need to define a large number of variables. It will be very difficult to remember the names of all the variables when writing programs. Instead of naming all the variables separately, it is better to define an array and store all the elements in it.
Memory allocation of an array
As mentioned above, all the data components of the array are stored in the attached space in the main memory. The name of the array represents the base address or the address of the first element in the main memory. Each element of the array is represented by the appropriate index.
We can define the indexing of an array as follows -
- 0 (zero-based index): The first element of the array will be arr [0].
- 1 (one-based indexing): The first element of the array will be arr[1].
- n (n - based indexing): The first element of the array can reside at any random index number.
In the image above, we have shown the memory allocation of an array of 5 sizes.The array follows a 0-based indexing approach. The base address of the array is 100 bytes. It is the address of arr[0]. Here, the size of the data type used is 4 bytes; therefore, each element will take 4 bytes in the memory.
How to access an element from the array?
We need the information below to access any random element in the array -
- Base Address of the array.
- Size of an element in bytes.
- Type of indexing, array follows.
The formula to calculate the address to access an array element -
Byte address of element A[i] = base address + size * ( i - first index)
Basic operations
Now, let's discuss the basic operations supported in the array -
- Traversal :-
- Insertion :-
- Deletion :-
- Search :-
- Update :-
Traversal operation
This operation is performed to traverse through the array elements. It prints all array elements one after another. We can understand it with the below program -
#include <stdio.h>
void main() {
int Arr[5] = {18, 30, 15, 70, 12};
int i;
printf("Elements of the array are:\n");
for(i = 0; i<5; i++) {
printf("Arr[%d] = %d, ", i, Arr[i]);
}
}
Insertion operation
This operation is performed to insert one or more elements into the array. As per the requirements, an element can be added at the beginning, end, or at any index of the array. Now, let's see the implementation of inserting an element into the array.
#include <stdio.h>
int main()
{
int arr[20] = { 18, 30, 15, 70, 12 };
int i, x, pos, n = 5;
printf("Array elements before insertion\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
x = 50; // element to be inserted
pos = 4;
n++;
for (i = n-1; i >= pos; i--)
arr[i] = arr[i - 1];
arr[pos - 1] = x;
printf("Array elements after insertion\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
Deletion operation :-
As the name implies, this operation removes an element from the array and then reorganizes all of the array elements.
#include <stdio.h>
void main() {
int arr[] = {18, 30, 15, 70, 12};
int k = 30, n = 5;
int i, j;
printf("Given array elements are :\n");
for(i = 0; i<n; i++) {
printf("arr[%d] = %d, ", i, arr[i]);
}
j = k;
while( j < n) {
arr[j-1] = arr[j];
j = j + 1;
}
n = n -1;
printf("\nElements of array after deletion:\n");
for(i = 0; i<n; i++) {
printf("arr[%d] = %d, ", i, arr[i]);
}
}
Search operation:-
This operation is performed to search an element in the array based on the value or index.
#include <stdio.h>
void main() {
int arr[5] = {18, 30, 15, 70, 12};
int item = 70, i, j=0 ;
printf("Given array elements are :\n");
for(i = 0; i<5; i++) {
printf("arr[%d] = %d, ", i, arr[i]);
}
printf("\nElement to be searched = %d", item);
while( j < 5){
if( arr[j] == item ) {
break;
}
j = j + 1;
}
printf("\nElement %d is found at %d position", item, j+1);
}
Update operation:-
This operation is performed to update an existing array element located at the given index.
#include <stdio.h>
void main() {
int arr[5] = {18, 30, 15, 70, 12};
int item = 50, i, pos = 3;
printf("Given array elements are :\n");
for(i = 0; i<5; i++) {
printf("arr[%d] = %d, ", i, arr[i]);
}
arr[pos-1] = item;
printf("\nArray elements after updation :\n");
for(i = 0; i<5; i++) {
printf("arr[%d] = %d, ", i, arr[i]);
}
}
Complexity of Array operations
Time and space complexity of various array operations are described in the following table.
Time Complexity
|
Operation |
Average
Case |
Worst
Case |
|
Access |
O(1) |
O(1) |
|
Search |
O(n) |
O(n) |
|
Insertion |
O(n) |
O(n) |
|
Deletion |
O(n) |
O(n) |
In array, space complexity for worst case is O(n).Space Complexity
Applications on Array
- Array stores data elements of the same data type.
- Used in solving matrices problem
- Applied as lookup table in computer.
- Databases record are also implemented by array.
- Helps in implementing sorting algorithm.
- Different variable of same type can be saved under one name.
- Arrays can be used for CPU scheduling.
- Used to Implement other data structures like Stacks, Queues, Heaps, Hash tables, etc.
Advantages of Array
- Array provides the single name for the group of variables of the same type. Therefore, it is easy to remember the name of all the elements of an array.
- Traversing an array is a very simple process; we just need to increment the base address of the array in order to visit each element one by one.
- Any element in the array can be directly accessed by using the index.
Disadvantages of Array
- Array is homogenous. It means that the elements with similar data type can be stored in it.
- In array, there is static memory allocation that is size of an array cannot be altered.
- There will be wastage of memory if we store less number of elements than the declared size.
Introduction to Arrays
Arrays in C/C++
Arrays in Python
Arrays in C#
