Dynamic and Static Arrays

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 used so much is because it forms a fundamental building block for all other data structures so we end up seeing it 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 having a discussion about arrays and 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 complex 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 a static array is a fixed length container containing n Elements which are indexable usually on the range of zero inclusive to n minus one also inclusive so a follow-up question is well what is meant by by being indexable so answer to 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 contiguous all the uh addresses are 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 uh you may or may not know that do use arrays so of course the first simple example is to temporarily store objects this is the most common use of arrays that you are probably familiar with next is that we use arrays as buffers to store information from an input or an output stream suppose you have a really large file for instance uh that you need to process but that file is so big it doesn't fit in all in memory so we use a buffer to read small chunks of the file into uh 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 and it's 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 in a programming technique called dynamic programming um with tabulation to Cache already computed sub problems so a classic example of this might be the napsack problem or the coin change problem all right time to talk about some complexity so the access time for a static array and a dynamic array is constant because of the property that arrays are indexable so searching however can take up to 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 a pending and deletion from a static array doesn't really make sense the static array is a fix 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 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 that 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 44 12 - 5 17 6 0 3 9 100 currently all the elements are distinct but this is not a requir M of an array also remark that the very first element 44 has index or position zero in the array not one this confuses many many intro computer science students who have no idea the confusing part is that most if not all of mathematics is one based while computer science is one now if we look at a you can see that it contains the values 44 12 - 5 17 6 0 3 9 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 of mathematics is one based while Computer Science is zerob 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 back to Ras I should also note that the elements can be iterated over using a for each Loop something that's offered in some programming languages um it does doesn't require you to 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 0o uh closed square bracket is equal to 44 meaning a at position Z is equal to the value 44 similarly a position 1 is 12 a 4 is 6 a at 7 is 9 but a at index 9 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 be minus1 that happens um if we assign index 5 to be 18 and if we assign index 6 to be 25 let's look at operations on Dynamic arrays so Dynamic arrays can grow and shrink and size as needed so the dynamic array can do all similar get set operations 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 7 it gets appended to the end if we add 34 again then it'll add it to the end and we can also remove elements so you see here our Dynamic array shrank and 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 array but this is not the only way of course so first we create a static array with some uh initial capacity usually non zero so as we add elements we add elements to the underlying static array keeping track of the number elements added once we have to add an element which exceeds the capacity of our internal static array um 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 of two 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 add 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 in 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 all out El 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 in the source code it 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