Array is one of the most basic data structures out there. We use it in a wide variety of applications as well as real-life situations. In this post, we will look at various array operations in detail. We will also be understanding the time and space complexity of these various operations.
If you want to first have an intro to array, check out this post and then come back to this one. If you already know what arrays are and want to dive right into array operations, just continue reading on.
So without wasting any more time, let’s start with array operations.
1 – Accessing an Element from the Array
This is arguably the most fundamental operation we would perform on an array. Also, the most common. We store data in an array and more often than not, we need to access it.
We can access elements in an array using the index value.
So what is the index?
Index is basically the position of each element in an array. It starts with 0 and is incremented by 1 as we move from left to right in an array.
As we can see in the above illustration, we have an array of 5 employees. It starts with index 0 and ends with index 4.
We can access the first element in the array using the index value. See below example written in C++.
int main() { int array[5] = {1, 2, 3, 4}; std::cout << array[0] << std::endl; }
Basically, here we declare an array of size 5. However, it only contains 4 elements currently. In the last statement, we print the first item in the array to the console. To access the first element, we use array[0]. Here, 0 is the index.
If we want to access the 3rd element in the array, we can use array[2]. The first element is at index 0. The second is at index 1 and lastly, the third is at index 2.
Time Complexity
Accessing an element in the array using index has a constant time complexity. In other words, O(1).
Now, you might wonder how that is possible?
This is because when we declare an array of a certain number of elements, all the elements in that array are stored in contiguous memory locations. For example, the first element is at location 0. Then, the second one is at 4. The third one is at 8 and so on.
See below illustration for an example.
Due to this arrangement, while accessing the elements, the program can easily calculate the memory location using the index value using the below formula.
Index N Memory Address = Starting Memory Address + (index * Size of an Element)So, if we want to access the 3rd element, we know that it will be at index 2. Using this, we can calculate the memory location as 0 + (2 * 4) or 8. Here, 4 is the size of an integer in C++.
Since this operation of finding the memory address can be done in constant time, the time complexity of accessing the element in an array using index is also O(1).
Space Complexity
Space Complexity is also pretty straightforward to calculate.
Since we don’t need to use any extra space depending on the number of elements in the array, the space complexity for accessing an element in the array.
2 – Inserting an Element into the Array
The next important one of the array operations is Insertion of Element in the array.
Insertion of an element has a couple of different flavors. We will discuss each of them.
2.1 – Insertion at the End of the Array
The most common way in which we add more elements to an array is by adding them at the end.
This is facilitated by the fact that in array we can always access the last index. So, it is trivial to insert an element after that.
Due to this reason, inserting an element at the end of the array can be done in constant time complexity i.e O(1).
Let’s see how we can do that in our C++ example.
#include <iostream> #include <vector> int main() { std::vector<int> arr; arr.push_back(1); arr.push_back(2); arr.push_back(3); std::cout << arr.size() << std::endl; }
As you can notice, we haven’t been able to see a normal array in this case. This is because in C++, a normal array does not know about its length. Also, the normal array has to be declared with a fixed size or initialized.
By using vectors (or specialized arrays), we can easily get around this issues. And through the push_back() method, we can easily push elements to the end of the array.
2.2 – Insertion Anywhere Except the End
The next flavor in inserting an element is inserting at the beginning of the array or somewhere in the middle.
Both of these operations have a linear time complexity i.e. O(n).
See below illustration for the reason.
As you can see, we want to insert the element 6 at index position 2. While doing so is easy since we know the memory address for index 2 because of contiguous memory allocation.
However, one 6 is inserted at index position 2, all the other elements to the right of 6 have to be shifted one position. So basically, element 3 will move to index 3. Same way, 4 will move to 4 and element 5 to index 5.
The complexity of this shuffling operation depends on the number of elements to be shuffled. In worst case scenario i.e. when we try to insert a new element at the beginning of the array, each element has to be shifted by one position. Therefore, the overall insertion in the beginning or middle is has a linear time complexity i.e. O(n).
Below is the code example on how to insert data at particular position in a Vector array.
#include <iostream> #include <vector> int main() { std::vector<int> arr; std::vector<int>::iterator it; arr.push_back(1); arr.push_back(2); arr.push_back(3); it = arr.begin(); it = arr.insert(it + 1, 6); std::cout << arr[0] << std::endl; std::cout << arr[1] << std::endl; std::cout << arr[2] << std::endl; std::cout << arr[3] << std::endl; }
Basically, here we are adding few elements to the vector using push_back() function. Then, using an iterator object, we insert a new element 6 at position 1 (or index 1) in the array.
The above program output is as follows:
1
6
2
3As you can see, the elements to the right of the new element 6 have been pushed one index.
3 – Traversing an Array
Apart from accessing individual elements, traversal is probably the most use array operations.
Traversal basically means accessing each element of the array once. However, it is not an operation in itself but is done using the access operation.
This operation is extremely useful when we want to perform some action on each element of the array. Below is an example where we basically print each element of the array.
#include <iostream> #include <vector> int main() { std::vector<int> arr; std::vector<int>::iterator it; arr.push_back(1); arr.push_back(2); arr.push_back(3); it = arr.begin(); it = arr.insert(it + 1, 6); for (int i = 0; i < arr.size(); i++) { std::cout << arr[i] << std::endl; } }
Here, the for-loop at the end is a basic example of traversal. Based on the size of the vector array, we loop over it and print each element to the console. To print each element to the console, we use the array access operation using index.
3.1 – Time Complexity
While the time complexity of accessing an individual element is constant time i.e. O(1). However, in a traversal scenario, we perform the same access n times. In other words, equal to the size of the array.
Hence, we can safely say that traversal operation has a linear time complexity i.e. O(n).
3.2 – Space Complexity
The space complexity of traversal and simply printing the element is still constant i.e. O(1). This is because we are reusing the variable i that stores the current index. And we do not use any additional memory.
However, this can change based on the kind of processing we do on the data.
4 – Deleting an Element from the Array
Deletion is also one of the more infrequently used array operations. In terms of its approach, it is quite similar to insertion.
There are two flavors again over here. They are listed as below:
- Deleting from the end of the array is having a time complexity of O(1). This is because we can access the last index of an array in constant time and make the element null.
- Deleting from anywhere else (beginning or middle) in the array has a time complexity of O(n). This is because we have to shift every element to the right of the deleted element 1 position backward. In other words, re-index each element.
To delete from the end of our example vector array, we can use the pop_back() function.
arr.pop_back();
To remove an element from a particular position, C++ vectors have another function known as erase().
it = arr.begin();
arr.erase(it);
Basically, the erase() function takes an iterator as input. Iteration specifies the position which we want to erase from the vector.
With this, we have looked at all the array operations along with their space and time complexities. These operations are fundamental aspects of using an array in our applications.
If you have any queries or comments, please do mention in the comments section below.
0 Comments