👋🏼Hello Everyone, welcome back to another interesting topic today. If you're here, I can assume that you're interested in the array data structure and that you also agree with me about the example of arranging books on bookshelves. So, why does it take us more time? Let's explore the array structure together. 📚💻🤓
What is an array? In Computer Science, an array is a linear data structure consisting of a collection of elements of the same memory size, each identified by at least one array index or key.
Errr….. 😖 what? What does the above mean? Did it sense anything? You are thinking like this. Yes, we can’t say anything from this kind of complex definition. So let’s make it simple.
🧠As an example, let's consider a person who is very strict and always believes that he is right. He doesn't open up to the world and doesn't care about others' opinions, doing everything according to his own opinions 💭. Simply put, he is a closed-minded person. The same idea applies to an array, which is not open to extension or shrinkage. When creating an array, the first step is always to define its size, which is a key feature of this data structure. The array can only be shrunk or extended within the declared size. Now, let's take a closer look at this amazing data structure and understand how it works and how we can represent it.
Just think we have 5 blocks📦. So we have to make them connected.
How can we do this? Furthermore, those 5 blocks have numbers stored in them. They have a hook on one side and a buckle on the other side.
So how can we connect those? We can put the hook into the buckle and connect those blocks. Also, we can connect as they are in or we can change the order and connect it. Also, there are so many actions we can take. We can remove one block and connect another block with the next current existing box. Same as this we can understand the characteristics of the array There are many operations in array insertion, deletion, traversing, search, and sorting. But rather than the box connecting we have to consider the size of the array first. Because in this block connecting there is always a hook and buckle remaining as below.
So we can connect another two boxes 📦with those. Likewise, we can add blocks as many as blocks we wish. But in the array, we can’t because the main characteristic of the array is pre-defined. So let’s think it is a size of 4 arrays, then we can connect only 5 boxes. The reason which is we can connect 5 boxes in the size of 4 arrays is the indexing starts from 0 in the array. So the length of the array always can be obtained by adding one to the size of the array. In this case size is 4 Then length should be 4+1 = 5. Let’s see how can we implement the above case using blocks.
Wait a moment. What is an index? In the above one, the block that includes 7 is in the first place but in the array, its index is 0. So, the array will start from 0 index as below.
Oh no!😱
There is an opened hook and an opened buckle. But the size of the array is 4 we can’t extend the array more. So we have to remove that opened hook and open buckle.
Did you get the basic idea now about arrays and their behavior? Simply array is a data structure that stores a set of elements in a pre-defined size. Arrays can be categorized into one-dimensional, two-dimensional, and multi-dimensional.
The single-dimensional array represents the linear collection of data. It means it has only one dimension. It can only be represented linearly. Two-dimensional arrays can be defined as a mathematical matrix. It is two dimensional which is row and column. It gets row and column numbers. Then store data. In a Multidimensional array, it has more than two dimensions. It can be 3,4,5 or that. It has multiple dimensions. For example, let’s consider a box in one dimension we can only see the line. In two dimensions we see a square but in 3 dimensions we can see the block. Likewise, when we increase the dimension we can see more details.
Same as that concept we can represent the array types below.
One dimensional array
It is a linear representation.
Two dimensional Array
For example, if we want to store 7 in the 2nd column in the 3rd now. Then we have to first get the 2nd column. After that, we have to get the 3rd row.
Then the intersection location of both can be stored in the data.
Multi-dimensional array
Let’s consider about 3D array. We can represent the 3D array as below.
Likewise, we can implement for more than 3 dimensions. Because in multi dimensions it can be implemented to more dimensions.
Now you have a clear idea about what an array is, and how it can be categorized. Let’s explore the operation of the arrays that we defined before. There are several operations.
- Traversal
- Insertion
- Deletion
- Searching
- Sorting
Let’s see one by one.
Traversal
In general words, traversal means travel over or travel across. So what is the traversal in an array? Let’s see...
Here travel in an array means getting the elements of the array one by one and printing it. Let’s make it more clear. So array has a set of elements. For example let’s consider the array which has the element 2,3,7,9,4, and 1.
The size of the array is 5 and the length of the array is 5+1=6.
In the above how can we get the element by element? First, we have to get the size of the array, and until the index is smaller than the array length we should have to print the element. In that way, we can print and see what are the elements in this array. For that, we have to travel through the entire array from the starting index 0. So this is how we traverse across the array. As I mentioned before this is also traveling across because from index 0 to index 5 we travel through the array and get element.
For better understanding let’s visualize it by using the below illustrations.
First, we have the array. To traverse through an array we must have to check whether the index of the array is smaller than the size of the array.
Let’s start with index 0.
Likewise, we can do as follows.
0 < size of array? Array[0] ⇒ 2
1 < size of array? Array[1] ⇒ 3
2 < size of array? Array[2] ⇒ 7
3 < size of array? Array[3] ⇒ 9
4 < size of array? Array[4] ⇒ 4
5 < size of array? Array[5] ⇒ 1
6 < size of array? No. so we have to stop.
As a result, we can get the results as 2,3,7,9,4,1
I think that you get the idea of how the traverse operation works in the array.
Insertion
When we consider the insertion operation, We can divide this operation into main ways.
- Insertion to the beginning of the array
- Insertion to the given index of the array
- Insertion to the end of the array
Let’s consider one by one.
1. Insertion to the beginning of the array.
For a better understanding, Let’s work with an example. Imagine that we have an array with a size of 4 and already there are three elements stored respecting the elements 4,3, and 1.
So in this case we have to insert in the beginning which means we should insert the new element to the location of the 0 index.
Wait!🛑You can see it’s already filled with 4 how can we insert a new element to that location? Imagine that the new element is 5. Then we should follow the below steps.
We have to create space in the index 0th location. For that, we have to shift every element to its next current location. Now there is a space in the 0th location. So now we can insert the 5 into that location. The final result will be stored 5 in the location of the 0th index.
But there is a main consideration when the array is full. Then we can’t insert new elements. So when we are doing insertion as a very first stop we have to consider whether the array is full or not. If it is not full only we can insert new elements.
2. Insert at a given index
Sometimes we use this way to insert new elements. When we ask to insert a new element and also the index location is given, then we have to do the insertion like this. So what is the approach to do this how can we do this, If already an array has the element in that index what should we do? If the array is full, then is it possible to insert this new element? Let’s find answers to these problems,
As a very first step of the insertion, we also have to check whether the array is full or not. First like we did before in the above two ways of insertion. Then if the array is not full we can proceed with the rest. But in the insert at a given index, there are also two possible cases.
Case 1 : Already an element exists at that given index.
Case 2 : The index asked does not have any data it is empty.
Let’s consider each case.
Case I : The given index location already stored data.
So after we identified it we noticed that the index that asked us to insert the new element had already stored other data before. For example, let’s consider an array of size 5 with elements 9,5,4 and 7 respectively. We can illustrate this as below.
Length of the array = size of the array + 1
⇒ 5 + 1 = 6
We are asked to insert the new element 10 at the index 1. But there are 5 already existing at the index 1. So how can we insert another element also there? What do you think? Before we move on to the solution please comment below what is your opinion about this.
So let’s move on because there is already stored the data before and we have a new element also in there. There are two options.
- We have to delete that data. But if we do then we lose our data.
- The next solution is we have to shift that stored data to another index location but if we do that what happens to the next data after this data? We have to move that also to the next index location likewise from the data which is stored last. We have to shift one index next to their current index to understand this better. I will explain this form of illustration.
1. The existing array
2. Let’s shift
3. We have to shift one after starting the last stored data.
Case II: The index location which is asked to insert a new element is free.
In this case, there is no issue we can fill that space with the new element.
Because it is not empty and the array is not full. For example, let’s consider an array with size 5 with elements 4,3,1,5. Then we asked to insert a new element 9 to the index location 2. So index location 2 is already empty. So we can just insert the 9 to it. Like below.
So either the way 1,2, or 3 we can insert a new element to an array.
Deletion.
In deletion, we are going to remove the existing element of the array and make it empty. Sometimes if we mistakenly add some element or if we need to insert another element instead of the existing element we have to use the delete operation. The delete operation can be done in 3 ways.
- Delete the element at the beginning of the array
- Delete the element at the end of the array
- Delete the element of the given index of the array
1. Delete the element at the beginning of the array
When we need to remove an element of the array at the beginning means if we need to remove the element that is stored in the 0th index location we use this way. But in this case, it is the worst case of the deletion. If we are deleting the removing the element that is stored at the other index location to avoid memory wastage we have to shift every element after that index location to one index location back from their existing index location. Let’s make this clear by using an example. Consider an array of size of 5 and it has 4,3,9,5 elements respectively.
So if we are going to remove the element that is stored in the 0th index location. Let’s see what happens.
To avoid this memory wastage we have to shift every existing element, one index back. The final result will look like below.
2. Delete the element at the end of the array
Here we are going to remove an element from the end of the array. That means if the array has 4 elements, we are going to remove the last element of the array. This is the best case of the array deletion. Because in here we do not want to shift any element. The reason is if we remove the element We don’t want to identify and insert new data when we are going to insert new data it will show that space is empty as the next respective space for identifying this. let’s move on to illustration.
For example, let’s get an array of size 5 which has elements 4,3,1,5 respectively.
The space is empty when we insert the next new data it can be added to this location.
3. Delete an element at the given index of the array.
When we need to remove an element from a particular location we use this method probably you will remember I said that insertion at a given index can also be done by deleting the element that exists there. This is the process we are using in that kind of situation. Also if we are added an element mistakenly at the wrong location by using this we can remove that. So how can we do this? In this case, also we have to shift the rest of the elements to avoid memory wastage. Because if we removed that element and kept that space empty most probably when we are inserting the next new element. We add that to the end of the array not on that location so to avoid that kind of risk we have to delete the particular element and we have to shift the elements which are stored after that element to one step back let’s see how we are doing this in illustration.
Let’s get an example as an array of size 5 with elements 4,3,1,5 and 7 respectively. We are asked to remove the data stored at the location of index 2. How can we do it?
Let’s do it step by step.
We have to remove the element at the given index.
According to the situation we can select either 1,2 or 3 as our deletion method and make it fulfill.
Sorting
In our usual lifestyle, we all have an order of life. If we don’t have such a thing it will be worse. We can’t do anything clear or succeed. We need to make something better or we need to achieve something, then we have to do it according to an order. We have to make the activities, plans and the stuff according to that order. Here also array should have the order. It can be ascending or descending we have to order the elements of the array. Because when we have an array it is not always ordered according to the element it has. As an example, if we have an integer array we have to order it according to the integer values. If we have the string or character array we have to order it according to the alphabetical order. So let’s make this clear by using one example.
Let’s take an array of size 5 with elements 4 9 7 2 10 and 1. So is it in order? Does it have any order with that arrangement? We can see 9 after the 4 then it is ok because 4 is less than 9 but after that what happens? There is 7 after the 9 but 7 is less than 9. There is no ascending order or descending order. So we have to sort it. Let’s sort it in ascending order by an illustration.
The initial unsorted array.
We have to do the comparison in times of 5 because the size of the array is 5.
Comparison 1
Step 1
Compare 1st and 2nd element
Step 2
Let’s move on to the next element
Compare 2nd and 3rd element
Step 3
Compare 3rd and 4th
Step 4
Step 5
Now we are done with one comparison. Let’s do this until the array gets sorted.
Comparison 2
We don’t have to compare with the last element because we sort it in the first comparison.
Comparison 3
Comparison 4
Comparison 5
The array is sorted now. The sorted array will look like the above.
When we sort an array into descending order, instead of checking whether the previous element is less than to next element we check whether the previous element is greater than to next element or not. If it is less than the next element we swap those.
Little challenge.
Try to sort the array 4,9,7,2,10,1 in descending order. Comment below if it is going well or not and the parts you want to be clear about.
Searching
In general idea of searching is to find something. If we don’t know the exact meaning of something we search for it. So it is the same in this case also. We are searching through the array a particular element exists or not. The search can be done in 2 different ways.
- Linear Search
- Binary Search
Let’s explore each one by one.
1. Linear Search
This is the most common approach in searching for an element through the array. We search that particular element one by one through the entire array. Let’s clear this with one example.
Just consider an array with size 5 with elements 4,7,9,1,10,5 respectively. We are asked to check whether there is an element 1 in the array. Let’s do it by using linear search.
Do we have to search if 1 is in the array or not? Let’s check it one by one. We have to check whether there is an element equal to 1. If it exists the 1 is in the array if it is not the 1 is not in the array.
This is the procedure in linear search when it is equal to that element we stop moving. Until it equals we moving. But it is not equal until we reach the last element, then there is no element like the element we search for.
2. Binary Search
When we hear binary always we get reminded 2. Because it is binary. Yes here also it is about two parts. But there is a very first stop we should follow before we do the binary search. What is that? Is there any guessing? First, as a very stop have to sort the array. After that, we can proceed with the rest.
Imagine that we have the same array that we used to understand the Linear search and there is the same question is 1 in the array or not? So let’s make an illustration and understand it clearly.
The existing array is 4,7,9,1,10,5. Is it sorted? No. So as a very first step, we have to sort it. After the sorting, it will look like 1,4,5,7,9,10. (I used the ascending order)
So then we have to divide the array into two parts. We have to divide it from either index 2 or 3. Let’s choose 3.
Then we have to check whether 7 is less than or greater than to 1. If 7 is less than 1, we must move on to the right part and search for the given lament. Otherwise, we have to visit the left part and search for the element.
Let’s move to the left part.
It also should be divided into 2 parts. So we can divide it from index 1.
Then move to the left part. So there is only one element. Is it equal to 1? Yes. Then 1 exists in the array.
This is the procedure of binary search.
So either using binary search or linear search we can check whether the given element is in the array or not.
Ar away we discussed the features, operations, and basic behavior of the array. So why do we have to use an array? What are the advantages and what are the disadvantages of the array?
Advantages:
- Code optimization; It makes the code optimized, and we can retrieve or sort the data efficiently.
- Random access; We can get any data located at an index position.
Disadvantages:
- Size limit; We can store only the fixed size of elements in the array. It doesn’t grow its size at runtime.
After learning all the facts about the arrays, what do you think about my question? Why did god move onto the linked list to store our sins? What will be caused by it? Please comment on your ideas about it. To solve the problem I will meet you with existing content about the linked list soon. Happy learning!
Read About :
