arrays are most commonly used data structure in any programming language and that's what we'll be covering today here is the list of topics so feel free to skip ahead in the end I have an interesting exercise for you so watch till the end let's say you're writing code for storing Apple stock price for five days and you want to answer questions such as what was the price on day 1 day 2 etc for this kind of problem you can use array I'm going to use Python throughout the presentation but arrays are a data structure which
are available in other languages as well but for the code snippet I'm gonna use Python so using Python you can store Apple stock prices and to retrieve the price for a given day you can use the index like this now the index for array in most of the language is start with 0 hence if you want to retrieve a price of day one you use stock price is 0 similarly for day 3 you will use stock price of 2 when you look at the internal memory presentation it will look something like this when I say
memory I'm referring to a RAM when you are running your code the code is run by CPU on your computer but it is using Ram or a random access memory to store all the variables and data stock prices in my Python program is a variable which it will store on these type of memory locations which have addresses so this hexadecimal number are the addresses on Ram now if you have the ability to open your computer and if you look at the RAM and let's say there is some way of visualizing what is stored on that
Ram then you will notice that the numbers are stored in bits ones and zeros so the diagram that I have shown you here is a simple diagram in reality we convert that number into binary number so 298 is equal to this binary number you can watch other on how to convert a number into binary but there is some formula that you apply and you get binary number so here each single digit is a bit which could be either 0 or 1 and when you have integer number you use 4 bytes to store the number 4
bytes is the capacity of integer number in many programming languages hence you store 298 like this so one byte is 8 bits so you can see that this is 8 this is 8 8 & 8 now you have 4 bytes these 4 bytes are actually stored on memory location so 298 is stored like this so in reality the stock prices of apples are stored in a way that is shown on the right hand side diagram and you know that I address it like 500 is one byte 501 is another byte and so on so 4
bytes for every number but just to keep the presentation simple I'm gonna use the diagram on the left hand side but just remember internally it is all bits ones and zeros now let's walk through some of the scenarios in our program the first question you might ask your program was what was the price on day 3 for that you can use the index operator like this where you know then that starts from 0 that's why the price on day 3 will be stock prices in index operator 2 that will give you 320 so let's see
how it works under the hood when stock prices is assigned this memory location it is pointing to this particular memory address okay when you do index of 2 what it is doing is in that memory address it will add 2 into sizeof integer because he sizeof integer is 4 by it hence the first one is at 500 and OH 500 0 4 ok that is your 4 I mean I'm starting forum from zeroth element but in reality it's the second element so second element is it is at five hundred and fourth location third element is
five hundred and eight hence you can use formula like this which gives you an address 508 and if you have not watched my Big O notation tutorial please watch it because throughout the data structure series we are going to evaluate Big O complexity of our program which tells you how much time your program is going to take in terms of Big O notation and this is a common question you get during any programming interview so it's better that you get your understanding clearer on Big O notation so here the index lookup for an array will
be order of one so the Big O complexity of looking at an array element by index is order of one order of one means it is constant time operation the second scenario is on what day the price was 301 so here you are not looking by index you are looking by value a simple Python program can be running a full loop on your values and comparing this values one by one when you get 301 you return that value or print it okay you are doing n number of hydration in this loop so let's say if
you're looking for 292 element you have to go through all the elements in the list and Big O complexity is often looking at worse case analysis hence the complexity for this program will be order of n which means you how to do n number of iteration to find the value in the array third scenario is you want to print simply all the prices or you want to do a traversal in that case you can just go through all the elements in the for loop and just print them the complexity of this program is also order
of n you want to now insert a prize at a given index so what will you do you will use insert function in Python which takes the index as a first argument the second argument is the value that you want to insert when you insert the value after inserting the value of the first location it will shift all the elements by one position so say 305 it shifted to the next memory address so since you are doing all this vaps the complexity of this program is order of n because you have to do n number
of wraps deleting element is also similar let's say you want to delete 305 the function that you use in Python is dot remove you supply index as an argument so 305 is 1 at 1 index after it removes the element it has to or shift this elements upwards so 320 it will move up and so on so again the complexity of this program is order of n now in Python the actual memory presentation is little different because python uses objects and references but I'm just giving you a simple presentation so that you understand the concept
behind an array okay in Python the list that we used is actually a dynamic array arrays are of two type static arrays and dynamic arrays in Java and C++ they have both static and dynamic arrays so let's say you are writing a program in Java to store the same stock prices one way you can do it is by creating an integer integer array of fixed size when you do new and file it will create an array of fixed size which is 5 here so when you try to insert an element at the 7th position ok
since it is starting from 0 6 will be a 7th position this will give you an exception your program will crash it will not allow it because this is a static array in static array when the size is fixed you cannot insert elements beyond your size the other type is dynamic array or a list in Java is an example of dynamic array you don't have to specify any size here you can keep on adding elements and it just dynamically grows the first one was static array the second one is dynamic array now let's look at
how these static and dynamic array work under the hood steady car is very simple you have fixed size and it will only allocate the memory for that fixed size okay but for dynamic array when you create your array object like this it will allocate some initial capacity in the memory okay so let's say all these boxes the stand boxes it allocated it for this stock prices array and the gray boxes I have shown at the top and bottom is let's say this is a continuous memory area and these locations might be used by some other
program or maybe might it might be used by other variables in the same program so these gray boxes are not available for use to you when you created this array it created initial capacity of 10 and it will see if that capacity is enough so what happens is when you insert this elements it will keep on inserting okay so it will insert this six elements fine what happens after you insert an element so let's check that so let's say you inserted ten elements your capacity is over now you want to insert 139 in that case
what it will do is it will allocate one new memory area at a different location so let's say at a different location it will allocate a total capacity of 30 so 10 was the initial capacity and the new capacity it is going to insert will be current capacity which is tan multiplied by 2 so it will give you additional 20 spaces so 10 spaces you already have now you will have total 30 spaces then it will copy all these elements to new area so you see you have to do this copy and then it will
insert 139 when arrays dynamic arrays grow there is an overhead of allocating new memory and copying all the elements so now let's say you are at 30 capacity if at 30 capacity is over when you try to insert 30 first element it will again allocate new memory segment somewhere else in the memory area and it will now allocate 30 which is of current capacity and then 30 multiplied by 2 which is 60 so now your new capacity will be 90 this is called geometric progression if you know about mathematical geometric progression so that's how these
arrays work so that they can handle the load of new insertions arrays can store numbers they can store tags like this they can even store a complex objects the thing about Python is Python can even store multiple types of element Python can store integer and text both in the same array but Java and C++ cannot do it there the type is fixed once you say integer you cannot insert string in that array you can also have two-dimensional array three dimensional array okay so this is an example of two-dimensional array and if you want to get
let's say this 42 element you will do stock prices in bracket 1 in bracket 1 again because this is 0th one will give you this sub array and within that subarray now you have 1 which is 42 this shows the static and dynamic arrays in different languages we already covered Python in Java in C++ also there are native RS as well as dynamic arrays and those dynamic arrays are called vectors now comes the most interesting part of this tutorial which is an exercise I have this exercise link in the video description below so click on
that link it will take you to this page you read about the exercise you try to solve this on your on and then you can compare your answer with my answer by clicking on this solution link but do not click on solution link directly a good student will try to solve the problem on his own first and then looks at the solution all right you all are very good nice students so please try to solve it on your own exercise and practicing is the only way to learn programming so by just watching my video you're
not going to become expert okay you have to practice these so practice this and let me know your answer also comment in the video description below how you find this tutorial and if you want me to make any changes or maybe add more exercises and so on the next tutorial is going to be on link list so stay tuned and thanks for watching
