Data Structures-arrays, queues,trees and graphs etc.

[00:00:01]Welcome to this lecture on data structures and algorithms. Yes, we all have been using data structures daily life in the projects we make whether they computer based or non-computer based. We are using data structures and of course algorithms to operate on them.

[00:00:18]So why not learn a little bit more about them in this lecture user and you are on a social media app.

[00:00:29]You are using a data structure which is called a graph wherein you know that millions and millions of users of that social media app are connected to each other and yes graph is the data structure which is used for storing the information of all those users.

[00:00:50]Now suppose if I'm not talking of the social media app like your WhatsApp or your Instagram but just if you want to search for your phone contacts you know they might be as simply arranged in a data structure called array. So what is a data structure where we store information?

[00:01:12]The data is called information and wherever we store the information in the computer memory is called a data structure. The manner in which it is stored differs from data to data. Like different data stored in a different manner will be called as stored in different data structures.

[00:01:34]And what are the algorithms?

[00:01:38]Algorithms are the steps on how we operate on that data, how we manage that data, how we process the data for our further use.

[00:01:51]So yes, there are tasks to be completed, there are problems to be solved and a step-by-step set of instructions is called an algorithm. We will study about al to tell what is an algorithm in a very simple manner. We can imagine that there are books in the library and if they are organized categorically and alphabetically or by the name of author it becomes much easier to find the correct book or the particular book. So we can say that the data structure is the bookshelf where the books is kept and the searching method is called the algorithm.

[00:02:39]We can also say learning to drive a car.

[00:02:43]You know that there are steps on how to start the engine and how to ride that vehicle.

[00:02:51]The step-by-step manner which you follow is called an algorithm. Similarly, you can use the example for algorithm if you want to create a user account for a website.

[00:03:05]Now, we are talking of linear and nonlinear data structures. That is as I mentioned the data can be stored either in an array which is called a linear data structure or in a graph which is a nonlinear data structure. And yes, there are more linear data structures and more nonlinear data structures. So what does linear data structure mean? When the data is organized in a sequential pattern, it is called a linear data structure. And when it is arranged in a hierarchical manner, in a network manner, it is called nonlinear.

[00:03:46]Our popular linear data structures are arrays or link list or Q where you see the insertion or deletion of the elements happen at both ends and a stack also is a linear data structure.

[00:04:06]Nonlinear data structures will be the trees or graphs and yes heap and with the very popular hash table arrays the very popular data structure.

[00:04:22]One of the basic data structure where multiple variables can be stored in one data structure. Yes, it is a collection of items of the same variable type of the same data type which are stored at the continuous memory location. As you can see, if you are storing marks of students or you are entering the data of books in the library everywhere the arrays can be used.

[00:04:52]So main features of an array are that it contains the same data type. It is a linear data structure and it is continuous. The data is stored in a continuous me memory locations and can be accessed using the index value. All values are stored next to each other in the memory. Also, arrays are known for the fundamental building block of other data structures like your stacks and cues or link list as we can see later.

[00:05:25]Very famous example is of books in the library. If they are stacked properly, if they are put properly, you can always access them using an array indexing. Q's as the name suggest Q's data structure are very very similar to the pattern as what we see the queue in our normal daily life. Q's boarding a bus. Q of people at a hospital counter. Q of people at a ticket ening counter. The pattern is the same. The person who enters the queue first will be the first to leave it also. And the person who enters the queue later will wait for its turn and then leave the queue.

[00:06:15]Same way the Q data structure also follows the rule of first in first out.

[00:06:22]Q's are the linear data structure where insertion of data elements happen at one end and deletion of the data happen at the other end. And these operations are called NQ or DQ. Like you can see on your screen, we have an existing queue of square boxes. And if the green square box has to be added to the cube, it will always be added at the back of the cube and the operation will be called NQ. And if I want to remove the yellow airbox, I will have to remove only from the front.

[00:07:02]The deletion of the element cannot happen from the mid data structure. This operation is also called DQ.

[00:07:10]Yes, we have several examples of Q used in our computer apps.

[00:07:17]Say for example, you are ordering food on a food delivery app and there are multiple requests being processed by the same restaurant. So how does your order gets processed? The people who request the food order earlier will be given preference and the request which comes in later will be processed later. So you can say the request orders are put in a queue and then the order is processed to be delivered. And there are many more examples like that.

[00:07:58]stacks like we have a stack of dishes or a stack of books, stack of mark sheets, another simple data structure. It is also the linear data structure where the last element is inserted at the same end and if we have to make the deletion the deletion of the element also happens from the same end of the linear data structure.

[00:08:34]It is what we call the follow the rule of last in first out or leo.

[00:08:42]Yes, the operation where we insert the element to the stack is called the push and when we want to delete the element we call it the purple.

[00:08:56]Yes, there are other operations also wherein we check whether the stack has any element in it or not. Further on, it can also say that there is a stack overflow or a stack underflow depending on whether we want to add more element to an already occupied stack or we want to delete elements from the stack when it is already empty. The popular example for the stacks are when we are browsing through a website and we click on the back button. Yes, the more back you go, the back pages are put on something which is called the stack data structure. It is very very interesting or even if you're not navigating a website, you are just painting in MS Paint or you're working in MSWord how you are navigating the pages are put on a stack.

[00:10:03]link list. Yes, it is the linear data structure where the elements are not stored in continuous memory location.

[00:10:12]The individual items are called nodes which contain two things. The data and the link or a pointer to the next node.

[00:10:23]That is the pointer contains the memory address or the reference of the next node.

[00:10:30]Yes, the memory is allocated dynamically in link list data structure. And how is it helpful?

[00:10:40]It is C. Suppose we have this example of a train where each train compartment is called a node and the coupling between these compartments are called pointers.

[00:10:55]The first element is called the head and the last is the null.

[00:11:03]How it is beneficial when we are using insertion and deletion. We do not need to traverse the entire data structure.

[00:11:13]We can access them individually through their memory references.

[00:11:21]There are three types of link list.

[00:11:23]Singly link list, doubly link list and circular link list. Yes, as the name suggests, the singly link list will have the traversal in only one direction.

[00:11:38]In doubling link list, the traversal can happen in both direction. That is the node stores the address of both the previous and the next node.

[00:11:50]And in circular nink list the last node points back to the first node or to the head instead of null.

[00:11:59]A very popular usage of cir link list is in our browser history.

[00:12:07]When we are browsing on our computer I am not talking of the individual website. We are browsing on different pages. It may either be Google or YouTube or you can open another tab for chat GPT or maybe some other shopping website. You see this memory data is stored as a doubly linked list where the connections happen either in forward direction or backward direction.

[00:12:38]There are more usages of link list which we will see later.

[00:12:44]Yes, also stacks and cues can be implemented both by arrays or link list.

[00:12:52]That is the memory allocation can be static or dynamic both. This depends on our problem statement.

[00:13:01]Arrays and link lists are different. But insertion and deletion and the data set is will decide which data structure is more required.

[00:13:14]So next time you are designing a app probably a music app where you have to play songs on a request basis. Which data structure do you want to use? Think about it.

[00:13:32]You meet your friends at a social media app and you decide to meet them further at your favorite restaurant. The social media app uses graphs, a nonlinear data structure.

[00:13:48]While going to the favorite restaurant, you use a navigation system or probably Google Maps. Again, a nonlinear data structure at the restaurant. Also, your favorite dish is located under a particular menu, probably north Indian, probably vegetarian or further on starter or something like a main course or a gravy dish. All that is a hierarchical data structure. All information like this is stored in nonlinear data structures. Let us know a little bit more about these nonlinear data structures. The trees, the graphs, the heap and the hash table.

[00:14:43]The very popular nonlinear data structures, the trees, the graphs, heaps and hash tables. Let us see a little bit more about them.

[00:14:54]Let us first see what are trees. Trees as the name suggest have branches and have leaves. The branches have parent a parent node containing information and further the parent will have a child node again containing further information.

[00:15:17]So to say the trees are nonlinear data structure will mean that the trees contain information and the data in the parent node can contain references to more than child one child node.

[00:15:36]That is why they are nonlinear.

[00:15:40]So we also call them a hierarchical data structure. The information is stored in nodes and the relationship between these nodes is in a parent child manner. The parent node can have multiple pointers or multiple references whereas each pointer references have one child node.

[00:16:04]Now we also say that trees do not have a cyclic graph like a structure. Trees are open-ended. Further on when we study graphs we know that the graphs are connected traversal is either a pre-order in order post order and level order. Now what does this mean? That is when we have to search for a particular information a particular node containing a particular data which we are looking for the we use the sorting algorithms and the searching algorithm. And how we traverse the tree, how we visit the particular nodes of the tree depends on the kind of pro problem we have. The methods used for traversing are these the pre-order, the in order, post order and level order. Now what is a pre-order traversal? A pre-order traversal in which the root is visited first and then we visit the left branch of the tree. Further on, once we finish the left side of the tree, we then visit the right side. This is the tree traversal. And you can see on your screen for the example of a tree nodes labeled as A, B, C, D, E, F, and G. And the traversal is happening from A to B, then D, then E, and then we come back and visit the right side, the C node.

[00:17:39]Further on the F node which is the left of the C node and then the G G node.

[00:17:47]In in order traversal we take the left side of the tree traverse it fully and then move to the root and then we come back to the right branch. Again in the right branch we first see the left side and then the right side. So that is the in order traversal.

[00:18:09]The traversal of the tree having the nodes labeled as A B C D E F G. The D will be traversed first. The D will be visited first and then we will further traverse it back up to B or E node and then the root node. Further on, once we visit the A node, we will go to the right side and then visit the F, C and G. F being the left side of the node and C again the root of the node and then G.

[00:18:43]So this traversal we have to see more when we are looking at the code of the trees. Post order the root is visited the last. First we finish visiting the left branch. Then we directly go to the right branch and finish the left side of the right branch. Traversing. If our searching stops, we take the break. But if our particular node is f found, we have to see that the traversal is ended.

[00:19:13]If it is not, we continue searching it further till we reach the root back.

[00:19:19]This is post order. And in level order, we finish searching by level by level.

[00:19:27]That is a popular example of a tree structure is a file system in our computers. All of us see them. All of us witness it. If we have to look for any particular file in our computer system, the path we traverse is called the tree data structure.

[00:19:48]The very popular trees are the binary tree, the marinary search tree, AVL tree, the red black tree and yes of course the heap graphs the nonlinear data structure.

[00:20:03]Here the data structure is represented by nodes and edges. The nodes are also called a vertex.

[00:20:11]Each node can be connected to more than one node. And unlike trees, the nodes can be connected back to themselves as well. That is graphs are not open-ended.

[00:20:24]They're little more complex in nature.

[00:20:26]And because of this complexity in their data structure, they are more flexible for data insertion and data updation, data traversal. That's why they're highly used in the apps we use in day-to-day programming.

[00:20:45]The pointer in the node value can have the reference for more than one node and that's what makes it a interconnected tree structure.

[00:20:58]The common terminology of graphs contains the path, the cycle and the degree. The path is a sequence of nodes that are connected by edges and it is what we look during a traversal during a sorting or a searching algorithm.

[00:21:14]A cycle is a closed path that is the path which starts and ends at the same node. And yes, no node is visited more than once.

[00:21:24]The degree of a node is the total number of edges connected to it.

[00:21:35]Yes. So if you have to visit a city and from city A you have to take a road trip to city B. Let's say from Bangalore to Hyderabad, you cannot expect that array or a link list can help you find the map. You have to use graphs.

[00:21:52]So let us see about their uh traversal.

[00:21:56]how we see the uh how we can visit the nodes of a graph. This happens in two popular ways. The BFS or the DFS. BFS is the breath first search.

[00:22:10]In this we visit the nodes level by level. Suppose we have a four noded graph A B C D and we label them as 1 2 3 4. The traversal happens usually as how we will do it in a queue like a first in first out. First we will visit the node A then visit node B then C at the same level and then D. That's how we visited all the nodes of this graph.

[00:22:39]For the depth first search we first take the left side and visit the nodes as deep as possible. Then backtrack it and then visit the right side. This is very similar to how we've traverse in a stack.

[00:22:56]Common examples of graphs are in social media apps and maps and rooting.

[00:23:07]Heap.

[00:23:09]A heap is a special type of complete binary tree that follows a special ordering rule. That is it is a kind of tree but it has a particular rule wherein the parent child relationship is followed in a specific manner.

[00:23:29]Of course the main purpose is to quickly access the largest or the smallest element.

[00:23:36]A complete binary tree means that every level is completely filled except possibly the last level. As you can see in the picture here, the nodes in the last level are also filled from left to right.

[00:23:51]Also to mention that while heap is con conceptualized as a tree data structure, it is actually stored as an array again for quick access of the elements.

[00:24:05]We have the max heap and the min heap.

[00:24:08]In the max heap, the parent node will always have the larger value than its child nodes. And the min heap, the parent node will have the lesser value as compared to its children.

[00:24:23]The priority Q in a heap is a data structure where elements are processed based on the priority and not the order in which they arrive.

[00:24:36]A hash table is the data structure that stores data in key value pairs.

[00:24:43]There is a key which matches the value of the data and the hash function which converts the data as an index to be retrieved later on that. So instead of searching every element one by one, the hash table uses the hash function to directly calculate where that particular piece of data should be stored or retrieved.

[00:25:10]Thus the hash function is the main important part of the hash table.

[00:25:16]It also makes hash tables as the most efficient data structure when it comes to sorting or searching. Because the traversal is not required for every element because of the key value pair, the direct retrieval of the element is possible.

[00:25:39]So this is one example of a hash table in front of your screen. We are looking about Virat Kohli the famous Indian cricket player and how the quickly the information about him is retrieved and displayed on your screens. It always works with the hash function and we search by the player name which will be the key and the entire data about him can come in front of you. For different players the same function can be used.

[00:26:12]So thus making it very very efficient.

[00:26:15]Other examples of hash table can be the student records in your database or the employee records in an organization.

[00:26:23]Yes, they're very similar to Python dictionaries. But Python dictionaries were made once the hash tables were made. So actually the efficiency of hash tables is because of their key function.

[00:26:45]And yes, before concluding our lecture on the topic of data structures, let us see the interconnection between linear data structures and the nonlinear data structures. The nine, the linear data structures, the Q and stack and of course the heap is connected to the array. Whereas the stack and Q can also be implemented by a link list. The nonlinear data structures the BST the heap the they can be connected with trees and the graphs with a BFS Q and the DFS as a stack. Also we should see a little comparison table for better clarity.

[00:27:28]So when you have an array you can have a fast random access for any record. For link list they are efficient with their frequent insertion or deletion because we don't need to traverse the entire data structure for that. A stack is best used for undo operations or recursion. A Q for shoulduling jobs like a printer job.

[00:27:53]A tree it is a hierarchical data structure and folders in an organization.

[00:27:59]We can use trees very efficiently.

[00:28:03]Heap for CPU shoulduling priority cues.

[00:28:06]A hash table for very fast searching by key.

[00:28:10]Thanks for watching. And this is a graph representing networks and relationships.

[00:28:15]Thanks for watching.