Operations on Arrays in Data Structures: Traversal, Insertion, Deletion and Searching

Guys, today we'll talk about some operations in array. We studied array in detail. Now we'll see what operations we want to perform. So see, you can do many operations in array, it could be of any kind, traversal, insertion, sorting, a traversal where you skip every second element, but here we'll talk about some primary operations. The first primary operation is called traversal. I'll explain but first I'll list the operations we'll see. The first one I wrote is traversal, second insertion. The third operation will be deletion, deleting an element.

Along with that, another operation will be searching. There could be many more apart from these, like sorting. We'll take up these topics later on. For now, we'll talk about the primary operations on array. Talking about that, the first is traversal. It's the easiest thing in array, it's like 2×2=4. You'll say you know this but I'll have to explain it again. I won't discuss traversal much.

I won't waste your time by telling you that for(int i=0 taking i less than the array's length i++, and you can print f ai and if you write %d ai then the array elements will start getting printed. You know all this, so I won't tell you that. Some of you may not know this while others do. If you've seen my C video, you'll know this. If you have an understanding of C and arrays, this might be new, it's very important. You know this, I'll erase it, it's simple. The definition of traversal, if someone asks you, you'll say umm forloop, no, don't say that. You should say that in traversal, every array element has to be visited once. If there's a festival at your house and your dad tells you to go to 10 relatives' homes and get their blessings, then what will you do? Traversal those houses. Suppose 0, 1, 2, 3 is your array, then you'll visit all these elements in array once and once you visit the entire array once, then traversal is done.

When will you need this? Either you want to print all the array elements or you may want to set this array. It's a new array so you want to put in values in it. Suppose you put in the values 7, 8, 9, etc. All these integer blocks, if I assume an integer array, you'll have to access them, that is traverse them. When you go through a road, you travel the whole road. You travel in an array, hence the name traversal. It's not necessary that you do this while printing alone. You can do it while setting the elements. You may be doing something else, like setting it.

You might be updating the elements and then traverse it. This is our traversal, this should be clear. If you're confused why 0, 1, 2, 3 etc. or similar doubts, then your situation is such that you need to write C language. At home, do C language, 15 hours sleep a little less one day and complete it. At about 11 at night, you'll be done with it. I'm kidding, watch it in breaks whenever possible. I've included practice in it. So here, we've seen traversal. I'll tell you what I was going to say. Suppose you build an array, you tell your compiler int arr[100]. Compiler will immediately reserve the memory. You want 100 blocks of memory, take it 0-99, there are 100 blocks in 0-99. Now it's your choice whether you use these 100 blocks or 5 blocks or you might use 3 blocks or 4 or 5, I'm using 5 blocks from 0-4. It's up to you how many blocks you want to use. You own these. Suppose you're very rich, you go to a colony and buy house no. 101 and 102. So, you know that one house is enough for you. If you have a lot of money, you might buy 102 and 103.

If you feel like washing clothes, you may hang them here. You'll say you own 3 houses but you're using this one. Will someone ask you why you're not using the others? You have reserved it, it's yours. To use only one or none at all is your choice. Similarly, I've reserved spaces for 100 integers in array. It's my choice to use 1, 2, 5 or 10 but I can't use 10,000 as it's not smaller than 100. I've reserved 100 spaces so I can only use 100. I can use less than 100 but not more than 100. What do I use if there's no space? When there are 3 houses and you say you'll use 4, then your neighbour will scold you for using his house.

The same case is in array too, from 0-99 you asked the compiler to reserve the space, these are continuous blocks, that's array's definition. One beside the other, like I told you in memory. It takes 4 bytes, so suppose this is a zero. If this is 4, then this will be 8, then 12. You can see the memory addresses with gaps of 4 because these are contiguous blocks. Suppose you need more blocks in the future, then you can't request, you'll have to make a new array and copy. In traversal, we can use as many elements present. So, you can make two variables, one will be capacity. The capacity here will be 100. You can make size, it will be 5. Size means how many elements you are using. Capacity means how many elements you can use. Capacity shows that this is the potential. If a pot can hold 10 liters and you store only a liter in it, but you bought it to store 10 liters if needed in future.

That's why you take a higher capacity in array and the size is 5 which means you're using only 5. I'll assume this and write .. and the notes that I've made I'll show you the notes if it's visible. I've used .. here. I've used .. where I've written array and this means that the array is bigger. This is the size but it has more capacity, I'll keep this. With that said, our traversal is complete. We don't have to worry about traversal now. Traversal means visiting every element of the array once. I'll make some space here and explain the remaining operations. Traversal is very easy. Apply a for loop till you reach the size. I'll show you by coding what I've explained theoretically. Keep traversing till you reach the size. Keep traversing, then you'll have understood. You'll be checking all these elements. They'll get printed, no big deal. Let's talk about insertion. Suppose this is my array. Now you say that in index number 2, 5 has to be inserted. Listen to this closely. There's 7, 8, 9 and you want 5 on index 2. If you put in 5 in index 2, where will 9 go? So that will be a problem.

We want to keep both 5 and 9. There are 2 cases here, listen carefully. Case 1 is that you want to maintain this order. That means 5 is followed by 9, 10, and 15. So, you'll have to make a gap here, how? It will be created by shifting every element, see what I do. Here was my array of 7, 8, 9, 10, and 15. Leave all this, you would've attended school. In school assembly, children used to stand in a line. The children are standing here and suppose something is being given out like ice cream.

You are in a line and your friend comes and says. You come and suppose this is your friend and you say please let me in, I'm very hungry, I want ice cream. Then your friend will have to shift everyone behind. He could go back but why would he? He goes back because of his friend, doesn't make sense. He'll let you in front and everyone will shift back. If I want 5 to be at index 2, I'll have to shift them first. Though in school you join the line first and shift later. You'll make space first, add 15, I have many blocks. This goes up to 99, 0, 1, 2, 3, 4. So I have to shift 15 aside. After that, what will happen? I'll shift 10 and 9, then I'll insert 5. What did I do for insertion? I shifted the elements. Now, if you're a very lucky person, then you'll get index number 5 for insertion. You'll add it as index 5 is empty, array will stay the same.

So best case, what will be its run time and computational capacity? Trigo of one go, that is you'll perform insertion in constant time, I'll write best case here. The best case insertion will be O(1). Now, if I want to do the worst-case insertion, if I'm unlucky and have a horrible fate, then I'll be told to add the element here. I'll have to shift everything for that. Suppose it is done and I've to do an insertion at index 0. I'll have to shift the entire array to that side. 15 will go here, then 10, 9, 5, 8, and then there'll be space. When these are shifted, there'll be space at 0. Then I can insert an element here, got it? If I dirty my finger to write here, I'll have to write 10, 9, 5 will shift here, 8, I'll write 7 here. Now I can insert an element here, suppose 3., I'll simply then insert 3 there. So how many did I shift in the worst case? I shifted n. So my worst case would be O(n). I had told you that in any algorithm, you'll find some best case with a constant run time.

That's why we don't discuss best case much, we discuss worst case instead. We'll not talk about best case, we'll discuss worst case. So what will happen in worst case here? It'll be O(n) in the worst case. If someone asks its complexity, I'll say O(n), not O(1). So, this is one thing, it was case 1. We wanted to maintain the order in this. What will be case 2? Case 2 will be that you don't have to maintain order.

Here, if I write case 2 and make some space. I'll erase this ice cream drawing. I'll make some space now. If someone says that they want to insert 5 here, in place of 8, at index 2, and we don't care about the order at all. So, I'll shift 8 to the end. 5 will come here and I have a lot of space. You have to keep in mind when performing insertion that size variable, that is the number of elements you're using remember to update that, plus one. Otherwise, you'll miss an element during traversal. So, remember to update the size, I'll show that in coding. All this is in the notes, nothing to worry about.

I have provided everything, just download the notes. I want to say one thing. Many people say the notes get downloaded as a zip file. I have zipped all these files for your convenience. Search how to unzip a file online. If you don't know how to do it, learn that. It's very important, it'll be useful in the future too. I zip it so that all codes, source codes, and pdfs are in one place. Otherwise, you'll be left downloading 10 times.

Zipping is for your convenience, use a computer to unzip. So, you'll have to google such things. I don't want to make a video on unzipping, so google it. I explained insertion in 2 cases, and that's done. Let's talk about deletion, it'll have the same cases. Deletion and insertion are brothers, they're only slightly different. In insertion, we add an element to the array.

In deletion, we remove it. So, if I want to delete 7, what will I do? First of all, I'll delete it. That means I'll shift 5 here. This 5 here, then this 9, then 9, then this. In the end, the size – = 1. I'll reduce the size by one as I deleted one element. How will it look? It'll look like this. 5, 5, 9, 10, 15. I'll draw lines too, so there's no confusion. It'll look like this as I've removed an element. I had to shift all the other elements. You'll tell me the best case and worst case complexity. I'm waiting, comment quickly with the time stamp. What will be the worst case and best case for deletion? I'll also get to know that you're watching the videos. Comment below what the best case deletion run time is and what the worst-case deletion run time is. From this case 1 method, okay. You would've written, I'll tell you. It'll be O(1) in best case, you had to delete the last one. It'll be O(n) in worst case, you had to delete the first one.

So, our case 2 is that the element order doesn't matter. You'll delete this element and directly bring the last one. Why are we doing this? Because this is my best option. If your friend wants to add you to the line, he doesn't care where he stands in the line, then you'll send him back and take his place. That's the best for you, no one else will agree. It's better to send him back than convince everyone else. Similarly, when you want to perform the deletion, and you don't want to maintain the relative order, delete this and bring 15 here. You've deleted the element with the least effort. Make the size – = 1 as it'll reduce. Then you'll use only these many array elements. First you were using all, now how many are you using? You were using 7, now you'll use 6. 0-5 is 6. 0-5 is not 5, sometimes interviewers trick you with this. They ask how many elements are being used, you say 5. What happened to zero? Why didn't you count it? So, they test your alertness sometimes.

They'll give you a simple question and you'll say 5. Wrong, 6. Oh right, sorry sorry sorry. It's done now, there are no takebacks. So, keep these things in mind. So, we'll perform deletion in constant time in case 2. In both best case and worst case, the size doesn't matter, we just have to shift the element. You would have understood the complexity of case 2. Both insertion and deletion will be at constant time. There's one more thing that we didn't see here. If we reach 99 while adding elements, what to do? We can't insert after that, there's only one option then. There's no other option, only prayers will work. You'll have to copy it then. You'll have to make a bigger array and copy the elements because if you filled all 100 elements, if you filled in elements from 0-99, where will you shift the elements? Both these ends are not your spaces.

You had asked the compiler to only reserve this space. Where is it? I erased it. You had said int arr 100 to the compiler. The compiler will say that it gave you the 100 spaces, don't ask for 101 now, that's wrong. You don't want an overflow condition, it's called overflow. You are breaking the array's borders. You can't cross LOC, it's the line of control, this and this, just stay in your country. Don't go out without a passport or visa. So, here we've understood how in a big array, we can insert a smaller array. We'll write its code as well. We're done with this and this, let's talk about searching. See, I'll erase this now. Talking about searching, in the last video we discussed. By the way, if you haven't accessed the playlist and you're only watching this then I suggest bookmarking the playlist from description because all the videos have been uploaded there.

In a past video, I analyzed two algorithms. Algo 1 was the first algorithm and algo 2 the second. I told you that algo 1 does linear searching. If your array is 7, 10, 18, 1, 3. This is an array and I want to search for 8. Then you'll search the elements one by one. If it's not sorted, in that case. You can search in this way, one by one. But if the array was sorted, you'll use binary search. This is called linear search. And binary search, okay. Let's see what binary search is. If this array was sorted, suppose it was 7, 10, 18, 21, 33. Assume it was sorted, we discussed unsorted before. Then what you'd do is you'd see whether 8 is in 7 or 33. You would call this low and this as high. You would check between 7 and 33 and if it's not there then you'll perform low + high divided by 2.

Your low is 0, then 1, 2, 3, 4. So, 0+4/2 will be your mid. You'll take its greatest integer and mid will be 2. Your mid is 2, so you come to it. You'll check if it's greater or smaller than mid, it's smaller. Now you'll make this is your high. You've reduced your array to half. You'll keep doing this till your array finishes or you find your element. You'll keep converging your array, keep halving it. After this convergence, your search will be over. You'll finally reach the element. Otherwise, you'll do 2+0/2 = 1. Your low is 0 and high is 1. What will happen next? When you converge again, your low = high, search over. You couldn't find the element. The benefit of binary search is that, if you've watched my video on analyzing 2 algorithms. In one, I was comparing it with every element, in another one, I was halving it to compare because my array was sorted. When the array is not sorted, use linear search. Otherwise, binary search is the way to go. It's computationally cheaper, that is quicker. Computationally expensive means you're doing unnecessary calculations. Computationally cheap means it's quicker and takes less space.

We've seen searching as well. We'll understand these things well with coding. And I've given you the notes. I've arranged everything for you. Now you've no excuse for not learning data structure and algorithms. You have no excuse, I don't know what it was before. You have notes, I'm helping you practice, if you're focusing, you'll surely understand the videos. I don't think you need anything else. Let's talk about sorting. We'll cover sorting algorithms, they help in sorting array. They help in sorting in ascending or descending order. Suppose an array has 7, 10, 15, and 1. To sort it in increasing order, I'll write 1, 7, 10, 15. This is a sorted array, this was unsorted. This is mentioned in the notes too. You would know what sorted means, it's an English word. So, if you didn't know, this is called sorting. We're done with this too. Guys, these are the notes that I've made for you. You can easily revise operations on array. I've summarised it for you, be it traversal or insertion, deletion, search, everything is in it.

I've summarised everything for you. Whatever we did is here in the notes. Do read them, I've written them by hand. You'll see that I've tried to keep it clean. I've made it as clean as possible. Definitely read the notes. You'll benefit from it. I'll show you the data structure algorithms playlist. Many people haven't accessed it. Around 14,000 people have accessed it but I want all of you to bookmark and save it so that you can see my course step by step. You'll be able to access the complete course. You can watch it video by video after completing the course. For example, if you want to solve time complexity you can watch this video. But if you're a beginner, you'll have to do it from the start. Link is in the description. So, I hope you got all the operations we did on array.

Along with this, in the coming videos, we'll code these operations in C language and C++ too. You can do it if you know C and C++ I already told you that I'll use that for obvious reasons which I stated initially. You can use Python, Java etc. too you can follow with those too as I said earlier but again I'm C, C++ here. Majority of the people wanted data structure algorithm in those languages. So, in the coming videos we'll code these. We'll understand whatever we did in theory and I hope you like this course. Do share the playlist with your friends if you like it. Thank you so much guys for watching this video.

And I will see you next time. [MUSIC].