Array
Data Structure
- Theory
- Implementation
- Leetcode Problems
- Notes
1.1 Array Definition
Arrays are defined as the collection of similar types of data items stored at contiguous memory locations. It is one of the simplest data structures where each data element can be randomly accessed by using its index number. In C++, an array is a variable that can store multiple values of the same type. For example,
In C++, an array is a variable that can store multiple values of the same type. For example, Suppose a class has 27 students, and we need to store the grades of all of them. Instead of creating 27 separate variables, we can simply create an array:
For example, if we want to store the marks of a student in 6 subjects, then we don’t need to define a different variable for the marks in different subjects. Instead, we can define an array that can store the marks in each subject at the contiguous memory locations.
Properties of array
- An Array is a collection of data of the same data type, stored at a contiguous memory location.
- Indexing of an array starts from 0. It means the first element is stored at the 0th index, the second at 1st, and so on.
- Elements of an array can be accessed using their indices.
- Once an array is declared its size remains constant throughout the program.
- An array can have multiple dimensions.
- The number of elements in an array can be determined using the sizeof operator.
- We can find the size of the type of elements stored in an array by subtracting adjacent addresses.
C++ Array Declaration
dataType arrayName[arraySize];
- int: It is the type of data to be stored in the array. We can also use other data types such as char, float, and double.
- array: It is the name of the array.
- 10: It is the size of the array which means only 5 elements can be stored in the array.
int arr[5] = {1, 7, 3, 2, 5};
int arr[] = {1, 9, 2, 4, 5};
for (int i = 1; i < N; i++) {
arr[i] = value;
}
int partialArray[5] = {1, 2};
int zero_array[5] = {0};
Why Arrays are required ?
Arrays are useful because –
- Sorting and searching a value in an array is easier.
- Arrays are best to process multiple values quickly and easy.
- Arrays are good for storing multiple values in a single variable
How to access an element from the array?
The formula to calculate the address to access an array element
Byte address of element A[i] = base address + size * ( i - first index)
Suppose an array, A[-10 ….. +2 ] having Base address (BA) = 999 and size of an element = 2 bytes, find the location of A[-1].
L(A[-1]) = 999 + 2 x [(-1) – (-10)]
= 999 + 18
= 1017
Basic operations
Operations That we can perform on array –
- Traversal – This operation is used to print the elements of the array.
- Insertion – It is used to add an element at a particular index.
- Deletion – It is used to delete an element from a particular index.
- Search – It is used to search an element using the given index or by the value.
- Update – It updates an element at a particular index.
#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]);
}
}
#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;
}
#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]);
}
}
#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);
}
#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]);
}
}
Complexities of Operations
Advantages Of an Array
Advantages of array are –
- 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 an Array
Disadvantage Of array are-
- 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.
