2.15 Implementation of Circular linked list in C | Data Structure Tutorials

same a singly linked list but the difference is what here the last node of circular linked list will contain address of its first node here 200 would be stored in singly linked list here we will store null right and in that video we have maintained only head pointer so now the problem is if I want to insert a node at the beginning in circular linked list now suppose I want to insert a node I have created a node write this and I want the data is 6 here I've inserted 0 and the address of this node is suppose 500 so we have created a new node pointer and this pointer is containing the center's 500 now I want to store this address at the beginning sorry this node at the beginning what you have to do for inserting it at the beginning first thing you have to update this length here you will store this 200 right so now it is going to point here plus second thing that you have to update this head pointer now head will contain for this address 500 because this is going to be the first node so here you will store 500 so now this link would be broken in now head would point here plus third thing you have to update what see the last node and circularly linked list will contain address of the first node and after inserting new node this would be the first node so you have to update in this pointer also now in this point that you will store what address of this node that is 500 but now the problem is say you can access this part easily you can access this part because this node is having a point a new node so using new node we can access this part because we cannot directly access the structure members as you know now how you can access this part having any pointer pointing to this node no we don't have so how we can access this part how we can reach till this part till this address 400 because we have only two pointers head head is having address this head is pointing to this node and one point is new node new knowledge point to this node we cannot preach till this node directly so now what you have to do you have one solution you have to traverse this this list till here right before updating these links what we will do how to traverse that thing we have discussed in the previous video we are going to take a temp pointer temp ill point to here then temp is equal to temp next temp is equal to temp next and we are going to stop here once we reach here the condition is what here we house what temp next becomes that equal to head because here we have not the condition null condition termination condition we have what termination condition is what this next is containing what the address of the head if next is containing address of the head it means this is the last node so now here we are going to stop and here we are going we are going to have a pointer that is M after that we can we can easily access this part that is temp next is equal to new node right this is the solution another solution is what when we are creating a circular linked list we can maintain a tail pointer roles right and how to maintain a tail pointer as well as a head pointer that we have discussed when we were creating a doubly linked list the link for that video will so I will provide you here in the SCI button you can check out there right so in this video we will see how to create this linked list and maintaining both head pointer and tail pointer at starting only if we maintain this pale pointer means tail would contain 400 so for inserting there's no need to traverse this list we can directly X is this part that is tail next till next is equal to new node and now this this node is pointing to this node and that is fine now another thing is one interesting point about circular link list is what there is no need to maintain this head counter you can maintain only the tail pointer that is also fine right and how we can create the list only maintaining the scale pointer that for that thing the code I will discuss in this video only fine and after we will discuss in the next video how to insert data in circular linked lists only by maintaining the stale pointer as well as both hadn't they now we'll see how to create our circular linked list right and we both we will maintain both head pointer and tail pointer right we have discussed how to create a circular linked list in the previous video also but in that video I have maintained only the head pointer now in this video see I guess everybody knows this coding because we have discussed many times this coding how to represent this node of a circular linked list obviously the we will define our own data type that is struct node structure using a structure that is keyword and this is a tab two parts are there in two data the data type of this is int and this is a pointer to the next node so we are taking a pointer that is next and this will point to next node right so an datatype of that node is struct node that is why here I am writing struct node so you can see it is a pointer to node we have we are having two pointers head and tail right now what creates we are having a function that is create CLL and we are going to define this function now for inserting initially we assume that list is empty we don't have anything in the list if it means head is having 0 and you can say tail is also having 0 but that is fine if head is equal to 0 means no node is it there in the list now to insert the node first of all you how to create that node you have to you know allocate the memory to that node and we will use what dynamic memory allocation in the linked list right why we are using dynamic memory allocation that came also we have discussed when we were discussing introduction to length list you can check out this video now how to use malloc function in C we are using malloc function here you write sizeof struct node the datatype is struct node this memory for this node I want memory so how much memory would be allocated for for this and for meit's for this that is 8 bytes would be allocated right and address of the first byte is 200 so malloc will it and what is 200 so malloc is going to return a void pointer but here this point that is new node pointer is what it is a point node so we have to typecast these things through typecasting means struct notice trick we will write in the bracket and here whatever this will return you will store in this new node and we have asked from the user which data I want to insert suppose a user has entered seven have you can exist this part how you can store seven here address off new node because pointer to this node is new node pointer new node and data pattern here I have stored none now I will insert this part this node in the list right now you will see what initially list is empty so we will write what if head is equal to zero it means there is no node in the list now what you will do you will simply do head is equal to you can say tail is equal to new node because we are maintaining both head and tail here so now head is also containing whatever the value new node that is 200 so head is containing 200 so head is pointing to this node as well as this is the first node as well as the last node so tail is also 200 tail is also going to point here fine but one more thing now in circular linked list the last node would contain address of the first node so in this case this is the last node this is the first node so here we cannot leave it like this here we cannot say that it is 0 so here before closing this if you will write what tail off next it means a love next this part this part will contain address of first node so address so first node is 200 only from where I can get 200 new node is having 200 so here you will write new node this is the extra line you will write when you are creating a circular linked list right now we have inserted first no now I want to insert second node so after inserting first node this is the list now I want to insert this node I have created one more node using the by you know running the same food when I want to insert here I have store 0 see now if head is equal to is equal to null but head is not now it means we have something in the list list is not empty so we are not going to do this thing now what you will do is else part what you will write see now you have to change what this node this point this node will point to this node that is why here we will store address of the next node fine second thing you will update what with the stable good point here because now this is the last node right third thing what you will update this is the last node so here this pointer will contain address of the first node that is here we will store two hundred three things you will have to update fine now how you will write this thing see so now first of all you need to update this pointer we cannot change this tail first of all we will update this thing after that after then we will update this tail pointer because if first at first only you will update this tail now tail is equal to new node that is hundred tail is pointing to here right now how we can access this node although it is the first node so we have a head pointer but suppose it is the second node and this is the third node so head will point always to the first node so we cannot change tail first first of all will change this path so here what you will write tail off next tale of next is equal to hundred I want to store here is equal to a new node right so here now I have hundred so this is now going to point here second thing we are going to update now the stain so now L is equal to new node right in ter also we have hundred now so now tail is also pointing to the snow third thing you have to update this thing now this will contain address of the first node so now here what can I write tail off next I can write L off next as equal to now here I want to store add in here I'm going to show the address of the first node and where I have address of the first node always the head pointer is going to contain this thing so we can write here okay fine here also new note if you write new note that is also fine but here also you can write what head it would be better if you write head because always head is going to contain address of the first node so simply you can write head now see the benefit of this thing right benefit of writing head here is what both in if and else this is the same statement tail next head tail next is equal to head so rather than writing it twice you can write this statement after this else block here I can write after this closing this else block here I can write tail off next is equal to head and no need to write hair and no need to write here so that is also fine because if after if block also this is going to be executed after else block also this statement is going to be executed that is why that I new node it is better to write here head right so now here tail next al next is equal to head means here I am going to store 200 so now this is pointing to this node and that is fine this last node is going to point to the first node this is the circular list right so you can insert as many node as you want simply by writing that logical logic only here you can ID printf do you want to continue you can say press 1 for continuing process press 0 for exit in scanf you can take your choice the users choice and for taking this you can declare you can initialize a variable here choice is equal to 1 right and if user will press 1 then a new node would be created right so these statements would be executed again and again so here before this thing I can write why choice right or if you are not comfortable with this while loop then you can use for loop also right initially we you can take from the user how many nodes the user wants to insert and suppose user interst 10 node I want to insert in the linked list so you can run the for loop from the node to 2 or 10 right and here if you want to check if this pointer has been set properly or not then how you can check here before closing this bracket of this function after this while loop you can check you can write what printf percent is D and what you can write tail off next means tail next this thing and arrow data in printf you can write percent is d and after that you can add this thing it means it should print seven it means you can say this link has been set properly this is a circularly list now right so now this is how you can create a circular list and maintain both head and tail pointer now in this case I have told you no need to maintain head pointer only by maintaining tail pointer you can create a circular linked list as well as you can perform the operations insertion deletion and all other operations so now how to create a linked list only by maintaining a tail pointer we will seem that thing so as you can see here I have only one point to that ass trail pointer and tail pointer is having null it's starting we are not having head so here I will write out tail is equal to 0 fine only few changes would be there remaining part would be same so now we have created this node write the same syntax would be there we have entered data 7 and here I have inserted a 0 now new null pointer is pointing to this node now here you will check if tail is equal to is equal to 0 in that case what you will do we are not having this head pointer right so now if L is equal to 0 it means we don't have any node in the list so now we are going to point tail is equal to this one right we are going to set this link so here you will store 100 right so now we will write what it is equal to it new node new node is having hundreds so tail is equal to a new node so this link has been set second thing now this is the first node also in the last node also so the last node will contain address of the first node fine so here what you need to write this tale of next here I want to store this hundred right so tail next is equal to new node so here I will write till next as equal to new note right now in else part now suppose I have inserted one node and now I have created another node second node and data I have inserted by using this same coding seven six and here I've inserted zero now the new node is pointing obviously to this node suppose address is 500 so here new node we have 500 right and after doing this part here we have hundreds so this is now pointing to itself only right now I want to insert this second node now how you can insert this thing in else part what you will write see here you have to update this thing also because this is the last node and this one would contain it so the first note that is here you will store hundred right and the scale would be updated tail would point here now right as well as you how to update this link this this node this link would contain address of the next node that is here we will update 500 so these three things you have to do but here you have you have to take care of one thing because see here we will insert address of the first node in the previous node we are we were maintaining head pointer so we can get the address of the first node always in the head pointer if we don't have to take care of anything we know that the head is going header country is having address of the first node but here we don't have any head node so you have to take care of that thing so first of all we will update this pointer here I want to store address of the first node right and address of the first node is hundred from where I can get this hundred here I have hundred before updating this thing so here what you will write how you can access this part new node next and here I want to store address of the first node that is hundred here I have hundred how you connect since this part the pointer to this node is ill so tail off next heel of next now here I have hundred and now this is now pointing to this node right now we will update what we will update this thing have you can access this part tail off next so here I will right tail off next is equal to address of the next note that is 500 a new node I have 500 here I can write new node so now here I have 500 and now this link is there third thing we have to update this Trail pointer because this is the last node now so here one third thing you will right now tail is equal to new node in tail we have new node that is 500 so now tail is pointing to this mode and that is done now suppose we have created third node and I want to insert third node here right so if tail is equal to is equal to 0 this condition is not true because tail is not now having address of the snowed last node right so now we are going to enter into the else part so in else part what you will write new node next what we have written new node next means new node next here and store tail of next tail is pointing to this node tail next is hundred see here I guess you have noticed that in the tail next pointer always we will get address of the head node right so no need to maintain the head node because from here I can get the address of head node but before updating this part we will update this thing because this is the only way we can get the address of the first node so first of all we will take this address and we will write that address here that is why you know next is equal to tail next till next is hundred so here I have 100 right now this is the last node and this is now pointing to this node right now we can mean we can update this thing this this will get contain address of the next node so in tail next tail next we are and we are having we will assign new moon that is 150 so here 150 so now this is pointing to this node third thing you have to update talos so tail is equal to new node that is 150 so now tail is not pointing to here tail is now to the snowed and this is the circular link list here we are maintaining only the tail pointer see as you have noticed in the previous case you have we will update at this point that if L is equal to if there is no node in the list if head is equal to 0 then also we are going to update this link if head is not a zero then also we're going to update this link so that line we have written after this if and else block but here I cannot write this line till next is equal to new node till next is equal to new node after this else look why so because see in this else block before this line this line is going to be executed and if you write this line after the else block in that case what will happen when control will enter into the else block then first of all this line will be executed right after that tail is equal to is equal to tail is equal to a new node so after that suppose here I want to insert this thing L is equal to new node means 150 now tail is pointing to this node right and we haven't updated this thing till next is equal to new node method means we haven't updated this thing right this is we haven't said this pointer so now after that if you right tail next is equal to a new node it means a next you are fixing this node right and that is not correct because we want to access this part we want to insert here that base of the next node that is why I am writing here in the else part only this line right same we will apply this while loop and if you want to print this thing after this while loop tail next and data tail next this and data is equal to the 7 would be printed so see it's not like that this is the only way you can create a circular linked list maybe you can apply your own loads you can you can create a circular linked list right now if we have only a tail pointer then how you are going to traverse the circular linked list so this is the circular linked list we have created we have maintained a tail pointer here and now I want to traverse the list I want to display the content that is 1 2 & 3 but here I don't know from where the list is going to be started because we have a pointer to the last node only we don't have any pointer to the first node right how we can come to know that which is the first node see I have told you in this case always the tail next right L of next means 150 this is going to be stored the address of the first node in the circular list right so till next we have 150 so from where I can come to know that the address of the first node is 150 that is this one right so we will take another pointer m and we will assign temp is equal to L of next so we are going to start from here now so here I will take another pointer that is M and you can also check if L is equal to is equal to zero it means here you can print list as empathy in else part what we will do first of all we will assign C we will write what M is equal to L of next so here we have another pointer temp which is going to contain whatever the value in tail next in tail next Intel we have 200 so using this pointer we can access we can reach till this address till next means here that is 150 so in temp we have 150 it means this is the first node we are pointing with the first node now right so now we are going to print this data and we will move this stamp here then we will print this with this one then we'll molted we will move temp here and then we will print this data where the termination condition is what where you want to stop this while loop see the only thing is we don't have any null condition the only thing is here the tail next is having the address of the first node always right so when the temp next once we reach here when once temp become the spot so now the temp next means 150 right temp next now is same as tail off next that is 150 and we know that the tail next is always containing the address of the head node it means we have reached to the last node so in the while loop what you will write while temp of next not equal to tail off next till then we are going to move we are going to print the status so here you can write printf percentage D temp of deta and you will move the stamp temp is equal to M next so now you can check the one you move this while loop see it starting temp is equal to tail of next that is 150 campus pointing to this node so now temp of next not equal to tail next temp next means F of next means one hundred hundred is not equal to 10 X because tail next is 150 so the condition is true so we will enter into the this loop we are going to print the data temp of data that is 1 will be printed now M is equal to temp next in temp next we have hundred so now in temp we have hundred we are going to move the stamp now now temp is pointing to this node again check temp next temp of next is 200 200 is not equal to tail next tail next is 150 yes condition is true so again in 10 to the loop print temp of data that has to be printed and now temp is equal to temp next that is 200 so here we are store we will store 200 so now temp is pointing to this node right now check the condition temp of next now temp next means 150 and not equal to tail next tail next is also 150 but this condition is not true it means now if amp of next is equal to tail off next it means we have reached till the last node to the last node right so now if you are not going to enter into the loop the this the control will go out from the loop and whatever the statement or then here that would be easier to it now the problem is we have displayed only 1 in 2 we are left with 1 this data so now after this what you can write you can write printf % is D and temp of data right so now temp is pointing to this node temple data means three now three would be printed and now you can close this display function right so this is how you can traverse circular length list if we have if we have maintained only one pointer that is tail pointer right so we have discussed all the options of creating a circular linked list by maintaining head only by maintaining both head and tail and by maintaining only the tail pointer then how and how to display the circular linked list right and if you here don't use this while loop then you can write this dua loop because if you don't want to print this at the last node separately then what you can do rather than using a while loop you can do what you can use do while loop so here don't use this while loop here right would do fine and in do first of all the this data the statement would be executed and after that the condition would be checked so after here you can write Y and now what you can write M not equal to tail off next in that case no need to write this line after this loop in this case if you use this why do I loop then 1 2 3 would be printed so here I am not going to trace out this do I loop you trace out you will trace out this do I loop is it working properly or not is the output is 1 2 3 or not without writing this line here fine and tell me in the comment box it is working properly or not right so as in the next we you know till then nobody take