3.3 Stack implementation using Linked List | Data Structures and Algorithm Tutorials

is stack and how to implement stack using arrays. What are what are the different operations on stack right in the previous videos as well as we have discussed the topic linked list all the type of link list as well as how to perform insertion deletion traverser all the operations on link list for those videos you can check out the description box right so I assume that you know the what is stack and what is link list right now we are going to implement stack using link list see we will implement stack using link list Right? So you have to follow the rule of the stack and what is that rule that is leo principle. Stack always follow what? Leo principle last in first out right that thing we have discussed in the previous video right for that video you can check out the s button. So stack is what it is an ordered list or you can say it is a collection where the insertion and deletion always perform from one end only. And how we are going to represent the stack the logical represent is something like this. It is a container which is having one open end right this end. Insertion is also from this end and deletion would also perform from this end. And this end is known as top. So the push and pop operations will be performed always from the top of the stack. And what is a link list? See when I'm saying a linked list it means we are discussing about singly linked list by default. Right? So this is what a singly link list. This is a node in the link list. Two parts are there. One is data part, one is address part. This address part or link part is containing address of the next node. Right? That is 400. Here 100. The last node is containing null because this is not pointing to any node. And head pointer head is containing address of the first node. So when you are going to program the link list then what we have the information we have is what? Head pointer. Only the head pointer right? This is not head node. This is head pointer. This is what you can say head node. The first node, right? We have only the head pointer that is address of the first node. Fine. This is what a link list. Now you have to implement stack using link list. So here we will store the data in the form of nodes as well as we have to follow the rules that is leo principle. And we have discussed the push and pop operation. The two fundamental operations push and pop is going to take order of one. Time complexity is order of one only in the form of stack. So you have to take care of this thing also. So now we can perform insertion and deletion from the one end only. Right? So in link list suppose I'm taking link list. So that end can be the tail or the head. You can insert and delete both from the tail end only also as well as from the head also from the starting also right so two options you have so if you insert and delete the data from the tail here from the end of the link list then see the time complexity would be suppose this is the list and we will we want to insert another node in the list so here you are going to insert suppose I'm taking that approach that from end only I can insert and here only I can delete. Right? So now you cannot directly insert the data here. Why? So because in link list only sequential access is possible. So you have to traverse the list till here. After that you can only insert that thing we have discussed in detail. Right? So for that the time complexity would be order of n for inserting order of n or you can say for this push operation order of n. If there are three node in the list then you have to traverse three nodes. If there are 10 node in the list and after that you want to insert then you will have to traverse all the 10 nodes means it depends on the number of nodes order of n. Second thing if you want to delete from the end only in that case also time complexity would be order of n. So in case of pop also it would be order of n because we cannot directly delete the data from the end. If you want to delete this data then you will have to traverse the list till here. After then you will do what? You will store here zero then this link would be broken after then after that you can free this data fine. So you have to traverse till here. So that also depends on the number of nodes present in the list. This thing also we have discussed in detail when we were discussing the delete operation from a single link list. Right? But in stack see we have discussed these push and pop operation should take order of one. So obviously we are implementing stack. So you should follow these rules. Now second option is you can insert and delete from the beginning of the list. Right? Suppose you want to insert a new node here at the beginning of the list. Then the time complexity would be you just have to update the links. Means now head would point to this node and here in the next part you will store address this one and this will point to this one. Right? So it is going to take order of one only. You no need to traverse the list. It does not depend on the number of node present in the link list. Same if you want to delete the first node. Suppose this is the first node. This node I want to delete. Simply what you need to do? One link you will set here. Head would point to here and you can simply free this node. That's it. This is also going to take order of one. It does not depend on the number of nodes present in the list. Right? So for implementing stack using link list we will follow which approach we will always push and pop from the beginning or you can say from the head only right and here we are taking head and in stack basically we are taking that name top. So here we will take this name as top. We are not taking head we are taking top. And second thing while implementing stack using link list you need to take care is see suppose I have called first pushes push two means I want to insert two. So here we will create a node because we are using link list in the data part we will insert two and at starting I'm taking top is equal to null that is zero or null because we are here considering link list. So head rather than head we are taking top and top is equal to null. So now suppose we will create a new node. This is we have already discussed how to create a node and this new node pointer is containing address of this one that is 100 suppose it is containing. Fine. So now here what you will do here in the next part we will store this top value. Initially top value is zero. So here we will store zero. After that now we have inserted we have pushed one node in the stack. So top the top should point here. So now top should contain 100 right? So suppose top is containing 100 address of this one like this. This is the stack. Now next suppose I'm inserting five. So another node would be created that is five right and suppose address is 200. In that case this new node would contain 200 means new node is going to point here. Fine. So now how you will insert this data here. In that case this newly created node this next part or this link part would contain address of this node. This node we have inserted right. So here you will store 100 from where you can get 100 because top is containing 100. Right? So now see as you can see this is pointing to this node and now you will do what? top is equal to new node that is top would contain 200. So now top is pointing to this node. Third suppose you want to insert eight here I have created another node here I have eight and in that case new node would point suppose the address is 300 so new node is containing 300 and new node would point here. Now what you will do here you will store address of this node that is 200 from where I can get 200 from top. So here I have 200 and this would point to this node. Now we will change this top. Top would contain 300 that is address of this node. And now top is this one and this is what stack right vertically I'm writing the link list. So now as you can see the difference here in the link list always when you will insert new node in that case the previous node would contain here the address of the new node. But in this case the difference is here I have created this new node. This new node is containing address of the this previous node. This is the difference. Fine. We have changed the policy a little bit. And why we have changed this policy to implement stack to follow the rules of stack. Right? Now suppose if you want to represent this stack in horizontal form then this would be the stack in the form of link list. As you can see see top is pointing to this node 8. This node is containing address of this node that is address of this node 200. This node is containing address of this node that is 100. Fine. Firstly we have inserted two. Fine. After that we have inserted five. Means five becomes the first node. And as we have discussed to implement stack to follow these rules the rules of stack we will insert always from the beginning in the link list. We will not insert from the end that we have discussed why we are following this approach because of this time complexity. Now when we will insert eight then eight would become the first node that is why 8 would become the first node. Right? If you will call push again push 10 then here you will insert 10. Now top would point here and this node would contain address of this node that is here 300 and top would point suppose address is 400 so in top there would be 400. So this is how you can implement stack using link list. You will always insert and delete from one end and that end would be the beginning. Now we will write write down the code for this push and pop operations. See here if you write the pop it means after inserting only the three three nodes these three nodes the pop item would be this one eight and now top would become pointing to this one and after that you can free this node right same here suppose I have inserted only the three nodes top is still pointing to here and if you want to delete then always we will delete from the head only from the one and only insert insertion and deletion so when you will delete this thing top would point to here after that you can free this node Right now we will write down the code for this push and pop operations. So suppose in stack I want to push three elements. First is two then three then 10. I have called push three times. Right? And we have passed the value whatever I want to push. Fine. After that I will display the data. After that we will call the peak function. Peak means it would return the topmost element from the stack without removing that element. Fine. Pop means the topmost element would be popped out from the stack. Fine. After that again peak and after that we will display we will call all these functions. Fine. So this is what a stack and we are using the link list. That is why obviously for pushing this data to a node would be created. Fine. So struct node we have defined our own data type for that node. Two parts would be there. Data part and one is link part pointer part or the next part as you can say. Fine. We have taken one pointer that is top also and this top is of type str node means type means here we always write the data type of that variable or that thing whose address this pointer is going to store and this pointer this top pointer is going to store address of the node proper fine right and the data type of that node is struck node strap node we have defined this thing we have already discussed when we were discussing the link list and initially we initialize the top as equal to null means stop is not pointing to any node. Fine. Now we will define this push function. So now here what you need to write here in these arguments what you need to write because I'm passing value two. So obviously you need some variable integer type because the data type is integer to receive this value. Fine that is why I'm taking here int x parameter of this function void portion int x. Fine. Now obviously we are going to create a node. So and how to create a node that thing we have discussed many times when we were discussing link list. So please check out that those videos first. Fine. Here we will use what dynamic memory allocation. So no need to specify the stack size as we have discussed in arrays. In arrays you have to specify the stack size. In that example we have taken five. So here in that case we have inserted only the five elements. But here if you are using the link list means dynamic memory allocation fun we are using. So no need to specify the stack size. This is what the advantage of using link list. Fine. Now and for dynamic memory allocation we will use what malo function. So I guess everybody knows the meaning of this line because we have discussed many times one node has been created and using malo function dynamic memory allocation syntaxes we will take how much bite we want how much bite in memory we want size of str node. The data type of this this node is what? Struck node. Fine. Malo would return a void pointer. That is why you have to type cast this thing because the new node pointer is what pointer to a node. So here you will type cast struck node array and whatever this maloc would return it would be we will store that address into into new node new node. The address of this node 100. This is what how many bytes has been allocated? Eight bytes. Four for this integer data and four bytes for this pointer. four bytes for this pointer in 32-bit compiler. In 16 4-bit compiler, it could take eight bytes. Right? And in typical compilers, the integer is going to take four bytes. Somewhere it is going to take two bytes. Fine. So now here you will store in the data part we will store two. How you will store that thing? How you can access this part? We can access the structure members using the pointer only. This pointer is pointing to this node. So new node arrow under this name of this part is data is equal to x because in x we are going to receive this value two right so here we have two now now the next thing is simple rule is what here in the next part what you will store new node next here I'm going to store the value whatever the value in top is equal to top right in top I have null so here we will store null Fine. Now obviously we have inserted this data in the stack. So top should point to this node. Right? So now in top what you will store address of this node that is 100 and from where you will get this 100. See in new node I have 100. So top is equal to new node and that's it. Again suppose if you call push is equal to three. Three would be passed. X is equal to now three. Fine. Again a new node would be created. A new node would be created. Right? Now this new node suppose address is 200. So now in new node pointer I have 200. Means this is now pointing to this node. Right? New node data is equal to X. In X I have three now. Right? New node next means new node next. This part would contain top. Top is containing 100. So here 100. It means 100 is the address of this thing. So this is pointing to this node. Right? Now top is equal to new node. Top is equal to new node. In new node I have 200. So top is containing 200. Means top would point to this node. Now right again if you call push is equal to 10 in x. Now I have 10. Again a new node would be created. Suppose address is 300. So in new node after creating this this node the address is this one 300s fine. New node data means here we will store x in x I have now 10. New node next is equal to top. New node next is equal to top. Top is containing 200 means it is pointing to this node now. And now top is equal to new node means top is pointing to this node. That is here we will store 300. And this is what a stack. This is what a logical representation of stack. Right? Now suppose if you call this display function, it means it should display first of all 10 then three then two. Right? Because top is binding to this node. Somewhere you will find out that they will display the data from here 2 3 and 10. But here we will implement this logic. Fine. Because from here only we can display. So first of all 10 we will display then three then two. So now how you will display the data? See see in the push operation we haven't checked for the overflow condition. Why? So because in the stack we haven't fixed the size. Suppose we have fixed the size that is three. So in that case we haven't we we are not able to insert fourth data that is why we checked overflow condition. Fine when we were implementing stack using arrays. But here we haven't uh specified the size of the stack that is why we haven't checked the overflow condition. Fine. Now how you you are going to display the data? First of all you will display 10 then three then two where you are going to stop when it becomes zero. The next part of this becomes zero. So you need to take another pointer you can say temp pointer fine because top is always going to point the topmost element. We cannot move this top for for displaying. First of all we will display this data then this then this. So we have to move some pointer. So here we will take another pointer that is temp pointer and initially temp would point to top right because we are going to start from here temp is equal to top it means temp is now containing whatever the top value that is 300. So now temp is pointing to this node right here you can check for underflow condition. If there is no node in the list in that case obviously we cannot print anything list is empty fine so here you can check if top equal to equal to null right in that case here in print f you can say list is empty right in else part what you will do obviously we are going to take a loop so here I'm taking a while loop while temp not equal to null Right? Till then what we are going to print the data first of all. So here what you will write in print f percentage d and temp data. This is how we are going to access this part. Temp data means 10 would be printed. Right? Now I want to print three. So you have to move the stamp in temp. Now I want to store 200. Right? Address of the previous node. from where I can get 200. Here I have 200. So here what I can write temp is equal to temp and then then this name of this part is link. Now temp is equal to temp link means 200. Now temp is containing 200 means temp is pointing to this node. Right? While temp not equal to null. Yes, temp is not equal to null. So again control will enter to this loop print temp data. Temp data is three. Three would be printed. Temp is equal to temp of link. In temp of link I have 100. So in here I will update the temp that is 100. So temp is pointing to this node. Now again check temp not equal to null. Yes temp is 100. It is not equal to null. Again temp of data means two would be printed. Again temp is equal to temp link. In temp link now see in temp of link I have zero. So in temp now I will store zero. It means temp is not pointing to anywhere. Now check the condition temp not equal to null. This condition is not true because temp is now zero and 0 is equal to 0. So control will not enter into this loop. Right? And what you have printed all the data 10 3 and two. So now you can close this else and this display function. Right? This is how we are going to traverse the step or you are going to display the data of the stack. So now next function is peak function. See the coding of this function. What peak function will return? It will display the topmost element. What is the top element of the data? We are just going to see the top element of the data. That's it. Right? We are not going to do top minus minus or anything. Fine. So now suppose we don't have anything in this stack. Then it should print a proper message. Suppose top is equal to is equal to null. It means here you can write print is empty. Right? Else else what you can print? Print f top element is percentage d. And how you will print this element? How you can access this 10 this part pointer to this node is top. So here you can write top data. This is how you can access the data part and that's it. When you will call this peak then it would print n fine. This is what the peak operation is. Now we will see the coding for the pop operation. So now pop means this topmost element would be removed and after that the size of stack becomes here. Now the size of stack is three. So now after that size of stack becomes two. Means after popping this the top should point to this node right and if you don't delete this thing then you can simply do top in top I want to store 200. So in top is equal to top link right and after that top would point to this node but we should not leave this uh node like this the memory is still allocated to this node and memory is very crucial resource. So you have to clean this thing. This is now garbage. Now you have to clean this garbage. So simply you can do you can free this node free and we can use a free function that we have discussed when we were discussing the link list concept and we can do suppose pointer one pointer is pointing to this node temp and we can pass free temp after that this memory would be freed right. If you will not free this memory that is also fine. That is also you have done the popping operation that is also fine. But the better approach is you should free this memory. And for this thing obviously we are going to take another pointer strct node temp pointer so that we can pass this pointer in that free function. Fine. So we have taken free uh sorry struck node temp and now temp should point to top. So temp is now containing that is whatever the top is containing 300. So temp is pointing to this node. Right? Now suppose there is no node in the list in that case underflow condition is there. Right? So here you can check if top equal to equal to null. So here you can print print f underflow right there is no node in the list. else. Now what you can do? If you want to print the popped element, if you want to print that the popped element is 10, in that case what you will do? See, first of all here you can print print f here you can write the popped element is percentage d. I'm writing only this thing and what this thing I want to print. So here either you can access this by temp or by top. It's up to you right because both pointers are pointing to this node. So I'm accessing this by top top data top data right so now this would print 10 after that we can do what after that after removing this because I want to remove this thing now so the stop should point to this node right so after that I can do top is equal to address of this node I want to store that is 200 from where I can get 200 here I have 200 so I can write top is equal to top link link or you can write top is equal to temp link because this node is having two pointers temp and top. So you can access these parts either by temp or top it's up to you. So here you can write top is equal to temp of link that is also fine. Now top is containing 200. So now top is pointing to this node. Right? Now you can free this node. Here I can write free and the pointer still pointing to this node is 10. Right now this is how we have deleted this node. And if you don't want to print the popped element then no need to write down this line. Simply do top is equal to top of link. And here this would be pointing right. And if you will not free this memory free of temp. If you will not take this temp pointer that is also fine. Fine. But you should take this for freeing this memory. Right? because we cannot leave this garbage like this. So now the output of this pop function would be 10 because we have deleted we have print printed this data top data. Now again if you call peak in that case it should print what three only because now after popping one data the topmost element is three. So it should print three and when you will display the function uh sorry when you call the display function then it would display three two. So here 3 and 2 this would be the output right and the output of this display would be 10 32 10 3 and two right so this is how we are going to implement stack using link list so in next video we will discuss some more applications of stack using code as well as we will discuss about Q data structure fine so I'll see you in the next video till then bye-bye take