All right, let's talk about arrays, probably the most used data structure. This is part one of two in the array videos. The reason the array is you so much is because it forms a fundamental building block for all other data structures. So we end up seeing everywhere. with arrays and pointers alone, I'm pretty sure we can construct just about any data structure. So an outline for today's video.

First, we're going to begin by hiring discussion about arrays and the answer some fundamental questions such as what where and how are arrays used. Next, I will explain the basic structure of an array and the common operations we are able to perform on them. Lastly, we will go over some complexity, complexity analysis and look at some source code on how to construct a dynamic array using only static arrays, discussion and examples. So, what is a static array? So static array is a fixed length container containing elements, which are indexable usually on the range of zero inclusive to n minus one also inclusive. So a follow up question is what is meant by being indexable?

So, answer this is this means that each slot or index in the array can be referenced with a number. Furthermore, I would like to add that static arrays are given as contiguous chunks of memory. Meaning that your chunk of memory doesn't look like a piece of Swiss cheese with a bunch of holes and gaps. It's contagious. us all the addresses or adjacent in your static array. Okay, so when and where is a static array used?

Well, they're used everywhere, absolutely everywhere. It's hard to make a program that doesn't use them. In fact, here are a few places you may or may not know that do use arrays. So, of course, the first simple example is to temporarily store objects. The most common use of arrays that you're probably familiar with. Next is that we use raises buffers to store information from an input or an output stream.

Suppose you have a really large file, for instance, that you need to process but that file is so big, it doesn't fit it all in memory. So we use a buffer to read small chunks of the file into The buffer or the array, one at a time. And so eventually we're able to read the entire file. I also like to use arrays as lookup tables because of their indexing property. So this is a really easy way to retrieve data from a lookup table if you know where everything is supposed to be, and at what offset. Next, we can also use arrays as a workaround in a programming language that only allows one return value.

So the hack we use then is to return a pointer or a reference to an array, which then contains all the return values that we want. This last example is a bit more advanced, but arrays are heavily used the programming technique called dynamic programming, with tabulation to cache already computed subproblems. So a classic example of this might be the knapsack problem or the coin chicken problem. Alright time to talk about some complexity. So the access time for static arrays and a dynamic array is constant because of the property that arrays are indexable. So searching however, it can take up to the linear time because we potentially have to traverse all the elements in the array in the worst case, such as if the element you're looking for does not exist.

Inserting appending. And deletion from a static array doesn't really make sense. The static array is a fixed size container, it cannot grow larger or smaller. When inserting with a dynamic array, this operation can cost up to linear time, because you potentially have to shift all the elements to the right and recopy all the elements into the new static array. This is assuming we're implementing a dynamic array you using static arrays, however appending, though is constant. Doesn't that seem a little strange?

Well, when we append elements to a dynamic array, we have to resize the internal static array containing all those elements. But this happens so rarely appending becomes constant time. deletions are linear for the same reasons that insertions are linear, you have to shift all the elements over and re potentially recopy everything into your static array. Okay, so we have a static array A I've defined at the top. So a contains the values 4412 minus 517 6039 100. Currently, all the elements are distinct, but this is not a requirement.

Have an array also remarked that the very first element 44 has index of position zero in the array, not one. This confuses many, many intro computer science students you have no idea. The confusing part is that most, if not all mathematics is one based work computer science is one. Now, if we look at a you can see that it contains the values 4412 minus 517 6039 and 100. Currently all the elements are distinct. However, this is not at all a requirement of the array.

Also remark that the very first element 44 is indexed or positioned at index of zero in the array, not one, zero. This confuses a lot of intro computer science students. The confusing part is that most if not all, mathematics is one based while computer science is zero based. This is what causes the confusion. But worst of all is quantum computing. I did research one summer in quantum computing during my undergrad, and the field is a mess.

It tries to please mathematicians, computer scientists and physicists all at the same time. And indexing just doesn't work well. Anyways, factories. I should also know that elements can be iterated over using a for each loop something that's offered in some programming languages. It doesn't require While you explicitly reference the indices of your array, although the indexing is done internally, behind the scenes, the notation of the square brackets denotes indexing. So array A square bracket zero, close square bracket is equal to 44, meaning a at position zero is equal to the value 44.

Similarly, a position one is 12, a four six, a seven is nine, but a index nine is out of bounds, and our program will throw an exception. Unless you're in C, it doesn't always throw an exception, unfortunately, okay. Now if we assign position zero to B minus one that happens if we assign index Five btn. And if we assign index six to being 25, let's look at operations on dynamic arrays. So dynamic arrays can grow and shrink in size as needed. So the dynamic array can do all similar get set operation static arrays can do, but unlike the static array, it grows inside as dynamically as needed.

So if we have a containing 34, and four, then if we add minus seven, it gets appended to the end. If we add 34 again, then we'll add it to the end. And we can also remove elements. So you see here, our dynamic array shrink in size. Pretty cool, right? Okay, so we already talked about this a little bit, but how do we formally implement a dynamic array?

Well, the answer is typically this is done with a static right, but this is not the only way. Of course. So first we create a stack if your a with some initial capacity, usually nine zero. So as we add elements, we add elements to the underlying static, right, keeping track of the number of elements added. Once we have to add an element with exceeds the capacity of our internal static array, what we can do is we can double the size, copy all the elements into this new static array and add the new element we need to add. Let's see an example.

So suppose we create a dynamic array with an initial capacity to then we begin adding elements to it. So the little circle with the slash through it is a placeholder for an empty position. Okay, so we add seven, everything's fine, we are nine, everything's fine. But once we add three, it doesn't fit in our internal static array. So we double the size of the array, copy all the elements that And now we can add three. Now if we add 12 everything's still okay, we're doing good.

And if we add five, okay, we have to do a resize again. So double the size of the container, copy all the LLM elements into this new larger array and then finish off by adding five and similarly we can add six without any issues. Okay, so I will be showing you an implementation of a dynamic array in the next video. If you're interested and the source code can be found at the link below. The link should also be provided in the description. So guys, thanks for watching, and hopefully I will catch you in the next video.