2.14 Circular Linked List in Data Structure | Creation and Display | DSA Course

linked list in data structure. Fine. So I'll provide you the link of that playlist in the description box as well as in this I button and this playlist is containing all the videos of linked list. Fine. So now first of all what is a circular link list? See this is what you can see a singly linked list. Fine having four nodes. Each node is having two parts. One is data part, one is address part and this part this pointer is containing address of the next node. That is address of next node is 150. Right? Here 300, here 100. Right? See, it's not compulsory that the addresses would be in ascending order or descending order. Any random address, any random location can be you know dynamically allocated to these nodes. Right? And we have a head pointer head is containing address of the first node. Right? Now to make it a circular link list, you just have to change it a little bit. And what is that change? See in the last node see the pointer is containing zero null. It means it is not pointing to any node. Now for to make it a circular list what we will do here we will store address of the first node. Now address of the first node is 200. So here we will write 200. It means this is now pointing to first node in the list. to make it a circle and as you can see this is now a circle. So this is a circular link list right in this uh list we cannot say which is the last node because see this was the last node because it was having here null but here we have the address of the first node. So it is a circle like this in a circle we cannot say from where the circle is going to start and where the circle is going to end. Right? So now see how to implement this link list this circular link list how to create the link list and how to display the content of this link list right it is same as singly link list only one is this difference you have to implement you have to change in that create function right so now see how you will write that code same for this node how to represent this node same as we represent in single link so this is how we are going to represent this node struck node we have defined our own data type two parts are there data part and one is the next or you can say this this pointer is next pointer which is containing address of the next node and I have declared one pointer also that is head pointer say this pointer is containing address of this node right if you don't write this like this you can write here semicolon and here you can write strct node this data type asterric head head pointer right and I hope everybody is aware about this thing why I'm writing here struck node ar next I have uh discussed it many times in the previous videos right because here see suppose if you write a str p it means this is pointer to int this pointer is containing address of a variable and the address type of that variable is integer so here we will write what the address of that variable whose address this pointer is going to store so that is why here this next pointer this is going to store this address and this address is of this node So data type of this node is struck node we have already defined. So that is why here I'm writing the data type of that node that is struck node. Fine. Now now we will uh define a function how to create this link list that is create a circular link list. Fine. It is same as singly link list. I have discussed the code for singly link list in the previous video. I I'll provide the link of that video in the side button. You can check out there. First of all we consider what the list is empty. you don't have any uh node in the list. So you can say head is what? Zero. Head is equal to null. So here I can write head is equal to zero. Now to insert these nodes first of all you have to create these nodes. You have to dynamically allocate the memory to these nodes. Right? Obviously we are going to allocate the memory for storing this integer type data and this pointer variable. Fine. So how we allocate the memory? Dynamically we are going to allocate the memory using Melo function in C and I hope you know the syntax of Melo function. We have already discussed many times. How we will write here we will basically write what that Malo keyword and in bracket we write size of size of a keyword how much size you want size for this node. So here you will write the data type of this node that is strct node right and malo is going to return what the the starting address pointer to the starting address of that allocated block right see suppose initially we don't have anything in the list like this head is containing zero and if you write this malo malo means memory has been allocated how much memory for this truck node four bytes for this and four bytes for this four bytes for this pointer in 32-bit compiler and eight bytes in 64-bit compiler. So now eight bytes eight bytes has been allocated. This is the block of eight bytes. And suppose the address of this is the address of starting bite is 200. Right? So this block has been allocated. Now melo will return what the pointer to this uh node you can say the address the pointer to the starting address of this node that is melo what this 200. So we are going to store this 200. Fine. So we are going to create another pointer. Here we are going to declare another pointer. You can say new node and in new node we are going to store this address. But malo basically returns what? A void pointer. And this pointer is what? It is a pointer to node. So you have to type cast this one. Whatever this malo will return and how you will type type cast this thing here. You will write strruct node a string. And now we can store this value in this pointer new node pointer. So here I can say now here I have a new node pointer and this is containing 200 means this is pointing to this node. Fine. Now we will ask from the user which data I want to insert using print f and scan f. So this is how we can take input from the user using print f and scan f percentage d address of where I want to store uh that value. Suppose here seven I want to store user has entered seven. So how we can access this part? The name of this part is data. We cannot directly access the structure member. So we need a pointer. Pointer to this uh node is what? New node. So address of new node arrow data. This part I want to access. So here the value is to be stored. Fine. Now initially we store here the pointer. In the pointer we store what? Null. So I can say how you can access this part. The pointer is new node arrow and this name is next is equal to zero. Now I want to insert this node into the list. How you will insert because list is empty. So now directly what you can do in head we will store what this 200. It means now head is pointing to this node. Now this is a list. Right? So directly I can write here what head is equal to new node. Fine. But this is not done. That is fine if you insert first one node. Now if I want to insert a second node in that case suppose this is a node. So now see this now the new node would be pointing to this node. Suppose address is 150. So now new node is going to store 150. New node is pointing to this node. Right? And if I write here head is equal to new node means head is going to contain now 150. So head this will this link would be broken and head will point to this node. So we are going to lose a reference to to this node and that we don't want right because obviously we want to insert second node fine. So you cannot directly write this thing. What we can write one condition if head is equal to is equal to null means if head is equal to zero at starting if there is no node in the list that in that case head is equal to new node that is fine. else. What we can do now? Else means I'm going to create I have created this second node. I have created this node. New node I have uh stored 150. And now I want to insert this node here. So now what you have to do obviously here you will update what? Here I will store 150. After that only it is going to point here. Now how I can access this part? See pointer to this node is head.ad head. next. So I can write here suppose head next is equal to new node. But now this is also not correct. Right? Now this is fine. We have inserted 150 here and now this is pointing to here. Now if I want to insert a third node in that case what happens? Now if head is equal to null but head is containing 200. So this condition is not true. So control will go into else part. In else what we I have written head of next means head of next this part this part in this part we we are going to store new node means new node after creating this node new node will would contain 300 right so now new node would point to this node so now head next here I'm going to store 300 it means you will lose this link and this node will directly link to this node. So using this logic also you can insert only two nodes. So this is not a correct logic. Now here what I will do see you have to take one another pointer that is temp because we cannot move head for accessing in in this case after inserting two nodes I want to insert this one. So I I'll put here rather than zero I want to in store here 300 so that I can establish a link to this node. But how I can access this part of this node because we don't have any pointer pointing to this node. Head is pointing to the first node. New node is pointing to the newly created node. So how we can access this node? So we need to maintain another pointer. You can say temp. So here you can have another pointer that is temp right and if head is equal to is equal to null head is equal to new node or here al here here only we will store temp also containing whatever the value in new node. So after uh inserting this first node we have one another pointer that is also having this 200. So this is also pointing to this node. Now I can move the step. How I can do this? See now in else part what I will write? See suppose I have inserted this one and I want to insert this second node. Note third node. I want to insert second node. Now how I can access this part using temp. We will use temp now because we cannot move this head. So temp next. So here I will write what temp of next is equal to here I want to store address of this node 150 from here I can get 150 in new node pointer we have 150 right and now here I have 150. So now this there is a link between this and this as well as we will do what in temp now we are going to store whatever the value in new node fine. So now in temp also we are having 150. So now temp is pointing to this node. Now see if you want to insert this third node in that case if part is not true. So we are going in else part we are going to enter into else part. In else part what we will do temp next using temp which node I can access this node. Temp next means here here I will insert new node. So after creating this node now in new node I have address of this node right that is 300. So now here I will store 300 and temp is equal to new node. So temp is containing whatever the value in new node that is now 300. So now temp is pointing to this node and if you want to insert fourth node that is also fine in else part temp next temp of next means this one here I will store whatever the value in new node in newly created node fine and after that we will move this temp right now suppose I I want to stop here I don't want to insert any extra node now one more thing you have to do to make it a circular list here you will store what this address of this node. Fine. So after this else part what you will write see how we can access this part the pointer to this node is you can say temp temp of next is equal to I want to store here this 200 from where I can get this address in head we have 200. So here I can write head. So now it is having 200 fine. And now this this pointer this node is pointing to this one. And now this is a circular link list. See as you can see. So only this line you have to add in this code of single link list creation to make it a circular link list. And now you can write the same code. You can write here print f. You'll ask from the user do you want to continue? You want to insert another node type one for continuation and zero for exit. And here you can write scanf percentage d and address of one variable you can take that is choice. And you can you can take here in this uh function only you can declare after this function you can initialize a variable choice is equal to one. Right? And if choice means if user press one it means a new node would be created. Another if again user press one another new node would be created. It means these lines from this line because this is the line where dynamically this memory would be allocated means new node would be created. So these lines would be in loop. So here I can write before this line I can write while choice and in the bracket fine. So here you can write after the sales print f one press one for continuation and zero for exit. So here scanf you can add percentage the address of choice and after that you can close the while loop and you can close this function create cl right this is how you can create a circular link list. This see this is not the only way to create a circular link list. Sometimes somewhere you find out that they will maintain the last node not the head node. That is also fine. You can maintain a last node means the tail node point to the tail node not the head node. And see if you want to cross check that we have created a circular link list or not then what you can do here after this print f and scan f after maybe this while loop you can do what you can print what see here this is the last node and after inserting three temp would be pointing to the last node right now temp is pointing to this node. So in print f what you can print temp next temp next means this thing right 200. So 200 means we have reached till this node and the data of this node is seven. So again arrow and data. So this should be printed what? Seven. Right? It means we have created a circular link list. So now we will see how to display the circular link list. So now for traversing this list from here to here or you can say for displaying the data obviously we need a pointer because we cannot move this head. We need another pointer. Right? So now this is the function we we are going to define this function and here I want to take another pointer that is temp using temp we are going to traverse right here suppose I have temp first of all what we will do if we will check if head is equal to is equal to null it means there is no node in the list so here you can write what print t list is Empty right else in else part what you will write now see first of all we will point this temp to this node that is we will we are going to store 200 in this temp now from where I can get this 200 in head we have 200 so here I'll write what temp is equal to head so now how you can print this data see this pointer is this node is having a pointer temp and head also but we will use temp because we are going to move this temp of data. So how you can print? Suppose it print f I can write what percentage d and temp data. This is how you can access this part of this node temp. And the name of this part is arrow data part. Fine. So now this will print what? Seven. But now we we we want to print six also then one also. So now we have to use a loop and from where till till where I want to print till here. So now in single link list what we have done while temp not equal to null because in that case here null it was the last pointer but here this is not a case here we don't have null. So what condition you will write in while loop. So before this line before printing what you will write you you will write a while loop. While now the condition is what? See I can write what this I can write a condition on this part. Here we have 200 and 200 is what? Address of this first node. It means we have reached to the last node. If I write here 200 fine. So you need to write something like this. So suppose at some time temp reach to here. So I can write temp next not equal to head because head is containing this address not equal to head till then we are going to print this and after printing we will do what we will move this temp is equal to temp of next. Now here also one problem is there. See what is that problem. At starting while temp is equal to head means 200. While temp next not equal to head. Temp of next is 150 and in head we have 200. So this condition is true. Fine. So we will enter into this loop and we will print temp of data. Temp of data means seven would be printed. Right? Now temp is equal to temp next. In temp we have temp next. Temp next we have in temp next we have 150. So here we are going to store now 150. So now temp is pointing to this node 150. Again while loop temp next. What is temp next? That is 300. 300 not equal to head. Yes. Condition is true. Again we will enter into into this loop. We will print temp data. Temp data means six would be printed. Again temp would be moved. Temp next is having 300. So now temp is having 300. So now temp is pointing to this node. Now again while loop temp next note equal to head. Now what is temp of next? temp is pointing to this node and next part is this one that is 200 but 200 not equal to 200. So this condition is not true now. Fine. So we cannot enter into this loop because in temp next we have 200. So now we are going to do what? We are going to exit from this loop. Right? But now we have printed only seven and six one I want to print. Right? And using this I cannot print this thing. So after this you will write one more line that is print f percentage d. How you can print this one? Because temp is pointing to this node after this while loop. So here I can write temp of data. Temp data means one would be printed here. Right? So after this while loop you will add one more line to display all the content of this list. So this is how we are going to display you are going to traverse you can say the circular link list. Only one difference is there only one difference this and second one is in the Y loop we are going to change the condition we cannot write down that condition of null because we don't have null in the circular link list fine somewhere you'll find out that they will maintain only the last node and using the last node they will traverse the list so that also we'll discuss later in the videos so this is all about how to traverse a circular link list and how to create a circular link list. So in next video we'll see how to insert a data in a circular link list. So, I'll see you in the next video. Till then, bye-bye.