Hello and welcome to this lecture on data structures. So, in this lecture, we're going to talk about what is a data structure and give you some basic idea or basic flavor of how data structures work and what do they do? All right, let's talk about what a data structure is. So, the basic job of a data structure is to store and organize data, and I will explain what data means in the next slide. But, suppose you have a large number of data items that comes from the stock market. And so let's say each item has the name of the stock, let's say it has the stock price, and it has the time at which the stock price is valid. And let's say you're getting a lot of these data items that come and go as stock price change so data items can come in and data items can go out. And the data structure is going to organize all this data, and it's going to help you support some queries efficiently. So that's the basic big idea of a data structure, so it's a system of organizing data in a computer that takes the data and supports certain queries. So what kind of queries? So some of the queries people support include rapidly finding some relevant data. So if I gave you the name of a stock, then help me retrieve all the information rapidly, okay? So that's an example of a query and another way is, if I told you to find all stocks whose current price is less than $10, okay? Per unit, so these could be examples of queries where you are interested in finding something. Obviously you are interested in inserting data, deleting data and modifying data. So when a new stock value comes in, you want to insert, if stock price is no longer valid, you want to delete, if a stock price changes, then you want to modify. So these are all standard operations, of course and then you want to iterate over some or all of this data. And what does iteration mean? Iteration means you need to be able to run a for loop for each data items and be able to do something in that for loop, and this is called iteration. So these are some basic operations, but we will study data structures that support many special operations in a bit. All right, and what are the kinds of data structures that we commonly encounter? These include arrays, hash tables, trees, graphs and so on, so there is a ton of these types of data structures that we commonly study. Now, what about the data in this data structure? So, in general, the data can be any object that you wish to store. So it could be basic types such as int, str, these are kind of basic types of floating point numbers. It could be combinations of these basic types, it could be a tuple of an int and a string that could be the data in your data structure. And that could be the id of the stock, the price of the stock, the name of the stock and some information about the stock market, something like that. So this could be the data tuples and this is a for tuple, and that's an example of how you can take an inbuilt object from the language, and this is a tuple type, these are basic types in python. On the other hand, you could have your own user defined classes with its field, as an example, you could store student record data, where you have student Id, okay? And then along with the student id, you have their name, you have their grades, you have their degree and so on. Okay, so these are examples of record and in python, you could program this using a class. One thing that's important is there is a way or a key, which helps us identify each data item. So, for example, if you have your student id, then you know that no two students should be sharing the same student id. So this is an example that's in databases, it's called primary key, we would just call it a key, and a key is usually a unique way of identifying a data object. Although this uniqueness is often not needed, sometimes in some data structures you can have multiple objects with the same key, so you can have the same key, but you can have multiple objects that associate with the same key. On the other hand, there would be some data structures where you assume that for every key it uniquely identifies a single object, so if it exists, then you would identify a unique object with that key. So those distinctions have to be made for the type of data that could be stored in a given data structure. All right, now, let's talk about data structure operations, the standard operations that any data structure should support would be to insert new data items, find all the items associated with a given key. And again, if the key has the property that there's one unique item with a key, then you would say, find the item if it's unique, but in general, it's find all the items associated with the unique key. Remove a specific item from the data structure, iterate over all these items, so we already mentioned this. And then there are some application specific operation, so you could say, find the object with the least value of some specific field. And we will talk about a data structure just coming up called a min heap, which will allow us to do exactly that, sort the objects in the specified manner. So next module, we're going to study a bunch of sorting algorithms, to do exactly that, update information associated with some data object, reorganize the data in a specific manner. So there is a lot of special operations that sometimes you may be called to support, and this would need us to design special data structures. All right, so I wanted to talk about data structures and introduce you to a simple data structure, which is a built in data structure called the list. And this is in Python, but you should note that every modern programming language like Python, Java, C++, they all come with their own data structure library. And which implements data structures like lists, they implement data structures like maps, we'll talk about this data structure called hash table. They implement the data structure for set, so languages, will implement built in support for many useful data structures, as first class objects in the language. As an example, Python allows you to create a list, let's say the list of 1, 4, 67 minus 5 and 10. You can append 20 to the end of the list, you can extract an element from the list, you can pop an element from the list, you can access the element at index 2, so index 0, index 1, index 2. Then that should return 67, you can iterate through the elements of the list. So, these are operations that Python allows you to carry out over this list data structure. and And you have a pen. You have inserted arbitrary position, remove or delete from the end or so called pop, remove or delete at the heart Arbitrary position. Then you have access to any element trade over the elements, and there's a large A p I of available functions that you can you can read online about the C P I. Now, how are these? How are they supported for the user? How are these operations supported? And the way Clayton would do it is using something called a dynamic today. And just to give you a brief flavor of how dynamic arrays work, Let me just walk you through. How How would this kind of a data structure work? And this is this would be a very, very basic data structure. Okay, so the idea here is when you create a list like one, this kind of a list like one minus 12, 14 4 minus 2 17. What this list is is an area in the memory. It's just an area in the memory which has been reserved for this list. So the list itself is a pointer. The appointed to this area So it says that the list begins here in the memory and the list begins ends here in the memory, and you would store the raw address of the start and the hand and and this would allow you to access, and and insert and delete and so on. OK, but these are not static areas, and these are called dynamic areas for a reason. So let me explain a little bit more of what these are, so the way you can imagine And it looks like or a list looks like is something like this. So So you have your current list here. So this is the current list right here. But attached to every list is also something called a space to grow. So this is currently unused space, but it's deserved for this place, so this is completely unused, so new elements can come in here. So as the list grows, you can you can grow into this space and no other list will use the space. So this is reserved deserved for the list. So this is how a dynamic array data structure would be implemented, right? So what do you do when you want to append an element to the end. Well, very simple. Suppose you have some space to grow And let's talk about what happens if you don't have space to grow But let's talk about when you have space to grow And I wanted to upend the element eight to the end The answer is very simple. I simply take the element aid the space to grow decreases Right, So I get rid of some of the space to grow I can't seem to do today, so I get rid of some of the space to grow I add my element eight here and I have one more element. Then I recorded the end of the list is here. Okay. And, and then what I simply do is my space to grow is now I have less space to go So this is my new space to grow. Okay, I hope I hope this is clear. Alright. I hope this is clear now. What happens if you want to insert things somewhere in the middle again? It's the same idea. Suppose you have space to grow. One of the things you need to do is you need to make space. Let's say you want to insert a five here at this position between the four and the 17. Let's say Okay, so you move the remaining elements here, and then this encroaches a little bit into the space to close. So this is the new end of the list. Okay, Once you've made this move, you insert five years. Okay? So in the worst case, in the worst case, the number of operations you want to do is going to be the size of the list, the number of elements in the list. And this is a big data because it's a constant factor times the size of the list. It's both a lower bound and an upper part. Why is that? Because in the worst case, you might want to insert things here, in which case everything has to move. Everything has to move to make space, and that, therefore, inserting at an arbitrary position in the end is data. And But as I look at this inserting at the very end, if you have space to grow, if you have space to grow, if space to grow, then to Ottawa all right, now you might ask what about deletion. Well, you can imagine how delicious is going to go. Suppose I want to delete 17. Then I just delete that element 17. But the blank spaces created. So I move everything past 17 back one step. I have more space to grow. And the end, this update. So you know how in certain elite works and the worst case for the elite s Dida of end the size of the list? Because in the worst case, I believe the first element here, So every element has to move, everything has to move. And that's data. Okay, now there is a problem which is running out of space to grow. So suppose I have I wanted to insert something at the end here, and I ran out of space to grow. Then what happens is, I have to relocate memory. So what I do is suppose my current list has an Then I relocate to times, and so this is going to be some some kind of an optimistic gas act. Future size, right? So if if currently my list is an equals 100 then I would relocate to an equals 200 space for 200 elements and I have to move over or copy over everything from the old memory. This is the old memory to the new memory, and this is important. And once I copy over, I have more space to grow. Now. This, of course, is data of n Okay. But, so you could say the worst case of insert regardless of very insert, whether at the end or beginning, is always due to end. Because, as I said, in the beginning, when you insert an element to the end and you have space to grow, then that's easy. You just attach it to the end. But if you insert an element to the end and you don't have space to grow, then you do have to double the size of the list and copy everything over. So that's data of and in the first case, in the very worst case. But normally it's data of one. Okay, But later in this class, I will talk about amortization, and I will revisit this question when we talk about amortization and we will see that, this read this growing or doubling in size is not happening too frequently does not happen too frequently. And so we will study this a little bit more. And this is just an introductory lecture showing you how data structures are designed, giving you the flavor. So I'm not really going to worry too much about this. But not that this doubling up doesn't happen at every step. So saying that inserting at the end, this data and this case is somewhat misleading. So we can We can be a little bit more clearer what we mean by that. And we could do something called immortalized analysis. We'll talk about that later, but let me go ahead and and talk about more kinds of, data structures. Another common data structure is a dictionary data structure. So unlike a list which simply stores just a list of items and so on a dictionary associates with the key a value. So here it is an example of a dictionary where I want to associate with the key. Hello? my keys are strings. So, Mikey, here in this case is a string and the value is a number and I want to associate with Hello, the value 10 in this line. I want to associate with the world the value 25. And in this case, I changed my mind rather than 10. I wanted to be minus 10. So this is updating the value. Here I am checking if hello is in the dictionary. And if it is, then I'm printing something here I am Iterating over the items in the dictionary, the keys and the value. So I would get key being hello value being my understand key being world again. Value being 25. So these are the operations I want to support for a dictionary. Okay. And the main idea behind the dictionary is associated key with some value. And the key is important. It's unique. So for every key, I can only have a unique value for each key. So each key can either occur. And if it occurs, it occurs exactly once. If it doesn't occur, then it doesn't occur. But you can't have the same key associating with two values, okay? And That's a That's a feature of the kind of data we stole in a dictionary. Right now, the operations are find the value that's associated with the key. Add, remove or replace a key value binding, it rate overall keys and a bunch of other FBI operations. And this is a basic, in build data structure in Python. Correct. Now, how are these implemented? Well, these are going to be implemented using something called a hash table, and we will studying hash table. So this is coming up later in this market, and we will look closer at hash tables and these are data structures that quickly look up the value associated with a given key, and we will see how to implement them. In this. In this module, at least, we'll see the beginnings of how to implement hash tables. Other examples of data structures we will study in this course include heaps, three based data structures, hash tables already mentioned and if time permits will study some spatial data structures for storing spatial data. All right, now, let me talk about data structures and algorithms. Now we saw algorithms are recipes to solve problems or step by step by step recipe to solve a problem. Now, how does data structures relate? Well, algorithms operate over data, and therefore, data structures are intimately tied to algorithms because what we can do is we can Then you want to implement a data structure and you want to implement operations like find, insert delete. We're going to use algorithm designed to make these operations. So these operations are going to be algorithms, and we're going to make those better and faster and more memory efficient. And so and likewise, we will also see that efficient algorithms need to store the data. The data that the algorithm operates need to be stolen efficient data structures. So these are very intimately tied. So algorithms are raised by which we study techniques for solving problems, techniques for solving problems. Okay, whereas data structures are techniques for organizing data, organizing data and operating over. But every algorithm operates over data as well, because algorithms have inputs that come into the algorithm and they need to store their inputs and and somehow efficiently process there. So so, as you see, algorithms and data structures are very intimately tied together. Okay, And with that thought I will conclude this lecture on data structure is the very basics of data structures. And see you next lecture where we will talk more about this. Thank you.
