An array is a group of items of the same type that share a common name. The elements in an array are stored at contiguous memory locations. Each location of an element in an array is indicated by an integer known as index, which is used to identify the element. Value of index starts from 0 and goes on till size-1 where size is the number of elements present in the array. The values in the array are indicated by writing the index or subscript within square brackets after the array name.
For example, consider an array {2, 4, 6, 8, 10, 12}
:
Here, the array length is 6 that means it can store 6 elements. Each element can be accessed via its index. For example, element at index 2 is 6.
Arrays are generally represented as :
datatype array_name[array_size]
datatype array_name[] = {value1, vlaue2, value3};
datatype array_name[size] = {value1, vlaue2, value3}
where data-type has to be a valid data type ( int, float, char…)
name must be a valid identifier
We can create arrays of various data types :
Integer array : int arr[] = {10, 20, 30, 40, 50};
Character array :char arr[] = {‘a’, ‘b’, ‘c’, ‘d’, ‘e’};
accessing elements in array
To access elements in an array, the index or subscript is put within square brackets after the array name. : array_name[index]
For example, consider an array arr[] = {2, 4, 6, 8, 10, 12}
arr[0]
gives us the first element i.e. 2
,
arr[1]
gives us the second element i.e. 4
,
arr[5]
gives us the last element i.e. 12
.
This operation is to traverse through the elements of an array.
void Display() {
int size =5;
int arr[] = {2,4,6,8,10};
for(i = 0; i<size; i++) {
print(arr[i]);
}
}
For inserting at the beginning of an array, the existing element need to be shifted forward. Assume an array arr with N elements. The maximum numbers of elements it can store is defined by size.
void Insert(int val) {
//shift the elements
for(i = N; i >= 0; i--) {
arr[i+1] = arr[i];
}
// insert the new element
arr[0] = val;
N++;//increase current size of the array
}
Since inserting in the front of the array involves shifting all the elements to the right side, it has a time complexity of O(n)
The exact location of the array where the new element needs to be inserted is provided.
void Insert(int position,int val) {
// Shifting rest of the elements forward
for(int i = N; i >= position; i--) {
arr[i+1] = arr[i];
}
// add new element at given position
arr[positon] = val;
N++;
}
Since inserting element in the middle involves shifting the array elements to the right side, it has a worst case time complexity of O(n)
void Insert(int arr[], int size,int val,int capacity) {
// Cannot insert more elements if n is
// already more than or equal to capcity
if (n >= capacity) {
return n;
}
arr[n] = key;
return (n + 1);
}
Inserting at the end of the array doesn't involve any shifting. Therefore, it has a time complexity of O(1)
int Delete(int arr[], int pos, int n) {
if (pos == - 1) {
print(Element not found);
return n;
}
// Deleting element
for (int i = pos; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
return n - 1;
}
Since deletion from the beginning of array involves shifting all the elements to the left, it has a time complexity of O(n)
Since deletion at a tiven index involves shifting the elements on the right side to left, it has a worst case time complexity of O(n)
Since deletion at the end doesn't involve any shifting of elements, it has a time complexity of O(1)