DSA From 0 To HERO 🚀 | Complete Beginner Roadmap

追加: 2026-05-12

[00:00:00]In this lesson and in this series of lessons, we will introduce you to the concept of data structures. Data structure is the most fundamental and building block concept in computer science. And good knowledge of data structures is a must to design and develop efficient software systems.

[00:00:21]Okay, so let's get started. We deal with data all the time and how we store, organize, and group our data together matters.

[00:00:32]Uh let's pick up some examples from our day-to-day life where organizing data in a particular structure helps us. We are able to search a word quickly and efficiently in a language dictionary. Uh because the words in the dictionary are sorted. What if the words in the dictionary were not sorted? it would be impractical and impossible to search for a word among millions of words. So dictionary is organized as a sorted list of words. Uh let's pick up another example.

[00:01:04]If we have something like a city map, the data like position of a landmark and road network connections, all this data is organized uh in the form of geometries. We show uh the map data in the form of these geometries on a two-dimensional plane. So map data needs to be structured like this so that we have scales and directions and we are effectively able to search for a landmark and get route from one place to another. And I'll pick one more example for something like uh daily cash in and cash out statement of a business what we also call a cashbook in accounts. It makes most sense to organize and store the data in the form of a table schema.

[00:01:45]It is very easy to aggregate data and extract information if the data is organized in these columns in these tables. So different kind of structures are needed to organize different kind of data. Now computers work with all kind of data. Computers work with text, images, videos, relational data, geospatial data and pretty much any kind of data that we have on this planet. How we store, organize and group data in a com in computers matters because computers deal with really really large data and even with the computational power of machines, if we do not use the right kind of structures, the right kind of logical structures, then our software systems will not be efficient.

[00:02:31]A formal definition of a data structure would be that a data structure is a way to store and organize data in a computer so that the data can be used efficiently.

[00:02:46]When we study data structures as ways to store and organize data, we study them in two ways. So I'll say that we talk about data structures as one we talk about them as mathematical and logical models. When we talk about them as mathematical and logical models we just look at an abstract view of them. We just look at from a high level what all features and what all operations define that particular data structure. Example of uh abstract view from real world can be something like the abstract view of a device named television can be that it is an electrical device that can be turned on and off. It can receive signals for satellite programs and play the audio video of the program and as long as I have a device like this I do not bother how circuits are embedded to create this device or which company makes this device. So uh this is an abstract view. So when we uh study data structures as mathematical or logical models, we just define their abstract view or in other words we have a term for this. We define them as abstract data types.

[00:03:57]An example of abstract data type can be I want to define something called a list that should be able to store a group of elements of a particular data type and we should be able to read uh the elements by their position in the list and we should be also able to modify element at a particular position in the list. I would say store a given number of elements of any data type. So we are just defining a model. Now we can implement this uh in a programming language in a number of ways. So this is a definition of an abstract data type.

[00:04:33]We also call abstract data data type as ADT. And if you see uh all the highle languages already have a concrete implementation of such an add in the form of arrays. So arrays give us all these functionalities. So arrays are data types which are concrete implementation. So the second way of talking about data structures is talking about their implementation.

[00:04:57]So implementations would be some concrete types and not an abstract data type. We can implement the same ADT in multiple ways in the same language. For example, in C or C++, we can implement this list ADT as a data structure named linked list. And if you have not heard about it, we will be talking about them a lot. We will be talking about link list a lot in the coming lessons. Okay.

[00:05:21]So let's uh define an abstract data type formally because this is one term that we will encounter quite often. Abstract data types are entities that are definitions of data and operation but do not have implementations. So they do not have any implementation details. We will be talking about a lot of data structures in this course. We will be talking about them as abstract data types and we will also be looking at how to implement them. Some of the data structures that we will talk about are arrays, linked list, stack, Q, tree, graph and the list goes on and there are many more to study.

[00:06:03]So when we will study these data structures, we will study their logical view. We'll study what operations are available to us with these data structures. We'll study the cost of these operations mostly in terms of time and then definitely we will study the implementation in a programming language. So we will be studying all these data structures in the coming lessons. And this is all for this introductory lesson. Thanks for watching.

[00:06:33]In our previous lesson, we introduced you to the concept of data structures and we saw how we can talk about data structures in two ways. One as a mathematical and logical model that we also call that we also term as an abstract data type or add and then we also study data structures as concrete implementations. In this lesson, we will study one simple data structure. We will first define an abstract view of it. We will first define it as an abstract data type and then we will see uh the possible implementations and this data structure is list. List is a common real world entity. List is nothing but a collection of objects of the same type. We can have a list of words, we can have a list of names or we can have a list of numbers. So let us first define list as an abstract data type. So when we define abstract data type, we just define the data that we'll store and we define the operations available with the type and we do not go into the implementation details. Let us first define a very basic list. I want a list that can store a given number of elements of a given data type. This would be a static list. The number of elements in the list will not change and we will know the number of elements before creating the list. We should be able to write or modify element at any position in the list and of course we should be able to read element at a particular position in the list. So if I ask you for an implementation of such a list and you have taken a basic course in programming a basic introductory course then you'll be like hey I know this an array gives us all these features all these operations are available with an array. We can create an array of any data type. So let's say if we want to create a list of integers then we declare the array type and as integer and then we can give the size as a parameter in declaration. I can write or modify element at a particular position. We the elements are a z a1 and are accessed something like this. We all know about arrays and then we can also read elements at particular position.

[00:08:50]The element at iat position is accessed as a i.

[00:08:55]So array is a data structure that gives us implementation for this list. Now I want a list that should have many more features. I want it to handle more scenarios for me. So I'll redefine this list here. I do not want a static list, a static collection with a fixed size. I want a dynamic list that should grow as per my need. So uh the features of my list are that I'll call my list empty if there are no elements in the list. I'll say the size of the list is zero when it is empty. And then I can insert an element into the list and I can insert an element at any position in the list and in an existing list. I can remove element from the list. I can count the number of elements in the list and I should be able to read or write or rather read or modify element at a particular position in the list and I should also be able to specify the data type for the list. So I should be able to while creating the list I should be able to say whether this is a list of integers or whether this is a list of string or float or whatever.

[00:10:03]Now I want a data structure which is implementation of this dynamic list. So how do I get it? Well actually we can implement such a dynamic list using arrays. It's just that we will have to write some more operations on top of arrays to provide for all these functionalities. So let us see how we can implement this particular list using arrays. Let's for the sake of simplicity of design uh assume that that the data type for the list is integer. So we are creating a list of dynamic list of integers. What we can do is to implement such a list. We can declare a really large array. Uh we will define some max size and declare an array of this max size. Now as we know uh the elements in the array are indexed as a z a1 a2 and we go on like this. Uh so what I'll do is I'll define a variable that will mark the end of the list in this array. So the if the list is empty we can uh initialize this variable or we can set this variable as minus one because the lowest index possible is zero. So if end is minus one the list is empty. At any time a part of the array will store the list. Okay. Okay. So let's say initially when the list is empty this pointer end is pointing to index minus one which is not valid which does not exist. And now I insert an integer into this array. And let's say if we do not give the position at which the number is to be inserted the number is always inserted towards the tail of the list towards the end of the list. So the list will be like we will have an element at position zero and now end is index zero. So at any time end marks the this variable end marks the end of the list in this array.

[00:11:55]Now if I want to insert something in the list at a particular position. Let's say I want to insert number five at index two. Then to accommodate five here at this particular position. We will have to shift all the elements one unit towards the right.

[00:12:13]All the elements starting index two. We need to shift all the elements starting index two towards the right. Okay, I just inserted some elements into the list. Let me also write the uh function call for these. Let's say we went in this order. We inserted two, then we inserted four and then we inserted in the end we are inserting five and we will also give the position at which we want to insert. So this insert with two arguments would be the call to insert element at a particular position. So after all these operations, after all these insertions, this is what the list will look like. This uh arrow here marks the end of the list in the array. Now if I want to remove an element from a particular position, let's say I make a call to something to the remove function. I want to remove the element two. So I'll pass the index zero here. I want to remove the element at index zero. So to do so all these elements after index zero will be shifted one unit towards the left or towards the lower indices and two will go away. Now this in end end variable here is being adjusted after each insertion that we are making.

[00:13:18]So after this insertion end will be zero. After this 1 2 3 and so on. After this remove end will be four again.

[00:13:28]Okay. Looks like we pretty much have an implementation of this uh list in the left that is described as an abstract data type. We have a logic of calling the list empty when we have this variable end is equal to minus one. We can insert element at a particular position in the list. We can remove element. It's just that we have to perform some shifts in the array. We can count the number of elements in the list. It will be equal to end + one. The value in the variable end plus one. We can read or modify element at a position. Well, uh this is an array. So, we can definitely read or modify element at a particular position.

[00:14:07]Uh if we wanted to choose the data type, it was just choosing the array of that particular data type. Uh this looks like a cool implementation except that we have one problem. Uh we said that the array will be of some large size, some max size. Uh but what is a good max size? We can always exhaust the array.

[00:14:24]The list can always grow to exhaust the array. There is no good max size. So we need to have a strategy for the scenario when the list will fill up the whole array. So what do we do in that case? Uh we need to keep that into our design. We cannot extend the same array. It is not possible to do so. So we will have to create a new array, a larger array. So when the array is full, we will create a new larger array and copy all the elements from the previous array into the new array.

[00:14:57]And then we can free the memory for the previous array.

[00:15:01]Now the question is by how much should we increase the size of the new array.

[00:15:06]This whole operation of creating a new array and copying all the elements from the previous array into the new array is costly in terms of time and definitely a good design would be to avoid such big cost. So the strategy that we choose is that uh each time the array is full we create a new larger array of double the size of the previous array. And why this is the best strategy is something that we will not discuss in this lesson. So we will create a larger array of double size and copy elements from previous array into this new array.

[00:15:40]This looks like a cool implementation.

[00:15:43]The study of data structures is not just about studying the operations and the implementation of these operations. It's also about analyzing the cost of these operations. So let us see what are the costs in terms of time for all these operations that we have in the dynamic list. The access to any element in this dynamic list. If we want to access access it using index for read or write then this will take constant time because we have an array here and in array elements are arranged in one contiguous block of memory. Using the starting address or the base address of the block of the memory of the block of memory and the index or the position of the element we can calculate the address of that particular element and access it in constant time. Big O notation that is used to describe the time complexity of operations. For constant time, it is written as in terms of big O. The time complexity is written as big of one. If we wanted to insert element, if we wanted to insert element at the end of the array uh end of the list, then that again will be constant time. But if we uh would insert element at a particular position in the list then we will have to shift elements towards higher indices. In the worst case we will have to shift all the elements to the right when we will be inserting at the first position. So the time taken for insertion uh will be proportional to the length of the list. Let's say the length of the list is n or in other words we will say that insertion will be big O of N in terms of time complexity. If you do not know about big O notation do not bother just understand that inserting an an element at a particular position will be a linear function in terms of the size of the list. Removing an element will again be big O of N. time taken will be proportional to the current size of the list. N is the size of the list here.

[00:17:46]Okay. Now, inserting an element at the end, we just said that it will happen in constant time. It is not. So, if the array is full, then we will create a new array. Uh let's call inserting element at the end as adding an element. Adding an element will take constant time if the list is not full. But it will take time proportional to the size of the list size of the array if the array is full. So adding in the worst case will be big go of n again as we said when the list is full we create a new copy double the size of the previous array and then we copy the previous array the elements from previous array into the new array. So, prime of AC what looks like the good thing with this kind of implementation?

[00:18:32]Well, the good thing is that we can access uh elements at any index in constant time which is the property of the array. But if we have to insert some element in between and if we have to remove element from the list then it is costly. If the uh list grows and shrinks a lot then we will also have to create a new array and have all this thing of copying elements from previous array into new array again and again. And one more problem is that a lot of time a lot of the array would be unused. The memory there is of no use and definitely the use of array as a dynamic list is not efficient in terms of memory. This kind of implementation is not efficient in terms of memory. This leads us to think can we have a data structure that will give us a dynamic list and use the memory more efficiently. We have one data structure that gives us good uh utilization of the memory and this data structure is linked list and we will study about the link lists in the next lesson. So that's it for this lesson.