2.16 Insertion in Circular Linked List | Data Structure Tutorials

linked list why so because the last node is containing address of the first node right so this thing the creation we have already discussed how to implement the circular linked list in the previous video you can check out that video in this I button as well as how to traverse the list but you can see how to display the content of this list that also we have discussed in that video in this video we will see how to insert a data in our circular linked list insertion at the beginning insertion at and and insertion at any specific position so first of all you will see how to insert a new node at beginning of the list see we are not having any head pointer so we don't have any idea which node is the first node but here still we can find out which is the first node the address of the first node how as we know in circular linked list always the last node is containing address of the first node this this would be the address of the first node and we have a pointer to the last node that is tail pointer so you can say tail off next this is what address of the first node right so now to insert a node at the beginning first of all obviously we're going to create a node and how to create a node that we have already discussed this is how you can define your own datatype how your opens have to represent a node this thing we have already discussed many times here I'm maintaining only the tail pointer so now I am defining a function insert add big knee fine so obviously we are going to create a new node for inserting that not here so for that what that method the dynamic memory location will be used and so in that case you will have to declare a pointer that is new node pointer and this new node pointer is going to store address of that newly created node and how to allocate a memory to newly created node using malloc function and whatever the malloc function will return that address we are going to store in this new node pointer so I guess the syntax we have discussed many times in the previous video so this is how we have created at this this new node and user has entered the data that is 7 and here in the next part we have inserted 0 which means it is not pointing to any node and this point there is a new node this node is containing this address that is 600 fine this concept we have discussed many times so now I want to insert this node here at the beginning of this list right so now first of all you can check if the list is empty in that case what you will do how you will check we don't have any head pointer we have only tail pointer so here you can check if L is equal to is equal to 0 it means there is no node in the list and then this node would be the first and last node in the list right so how you will insert this thing also we have discussed how we will do this thing suppose there is no node we have only tail pointer and tail is containing 0 and we have created this node so what you will do this would be the first node so now tail would point to this node only and this is the last node also so here you can say in tail we will store what this this address that is new node so now in tail 600 would be stores are not there good point here one more thing in circular list the last node would contain address of the first node so this is the first and last node so this node this this will contain address of itself so now here you will store 600 so now how to exit this part new node next or you can say the scale of next tale of next is equal to new node right this is how you can insert the very first node or you can say if Lester is empty then you can write down the DS line else if list is not empty now suppose this is the case we have 4 node in the list and if I want to insert this node here now what you will do now view you have to update what first of all here in this address part this address this pointer should contain address of the next node that is hundred Harry I want to store hundred right and tail would point now after inserting this payload point here so here you will store address of this that is 600 now here how we will come to know that which node is the first node and what is the address of the first node because obviously before that first node I want to insert this one right so I will store that address here only one way is there the last node next pointer is containing address of the first node right so first of all update this thing how to X is this part you can say new node next here I can write new node next is equal to tail off next how you can it says this part pointer to this node is print tail off next now see here now L of next is containing hundreds so here I have stored 100 now this is pointing to this node now this become the first node but this is not done yet you have to change this part also because last node is going to contain address of the first node that is 600 so here what you will write in tail of next we will store the 600 from where I can get 600 in the new roll pointer we have 600 now that is done now this is pointing to this node right here now I have 600 right and now the system that is the insertion at the beginning of circular linked list and now if you want to check that you have inserted correctly or not then what you can do the same funda here after this else before closing this this function here I will close this function before this closing this function you can write you can print what printf percentage D what you can print C tail next tail off next means this side plus 600 means we have reached till this address and data tail of next data is 7 so it should print 7 because this is now the you can say the first node so it should print 7 right this is how you can change now we will see how to insert data at the end of the list so now suppose we have created this node having gate at 10 right and address is 700 so this address the 700 edges should be stored in new node pointer and now I want to insert this node here insert @n so in this code what you need to change see here I have changed what insert edy and same we are going to declare one new node pointer using malloc dynamic memory will be allocated to that node that this would be stored in new node pointer we will ask from the user using printf and scanf write the data and all and if tail is equal to zero and then then this same line would be written find same what would look there but there is a difference in else Python right now in else part what you will write see now if you insert this paw this node here three things you need to update first thing is now this is going to be the last node so here the last node should contain address of the first node that is 600 this is our first node right so here you will update what here you will write 600 right second thing now this node is containing address of the next node that is here you will update 700 third thing you will update what now this this is the last node so in tail pointer also we are going to store what is the address of the last node that is 700 three things you have to a bit but you have to take care which pointer you need to update first see here I want to store address of the first node right this one 600 and there is only one way to get address of the first node this because we are not maintaining any header pointer right so this is now address over the first node that is 600 because last mode is containing address of the first node and this is the last node right now so before updating this pointer you need to take out this address and store here because if you update this thing first if you if you have written like this tale of next is equal to new node means you have inserted here 700 means this node is pointing to this node now now there is no way you can get to the address 600 from where you will get 600 right so now first of all update this thing and have you'll update this thing how you can access this part new node next so in else part you will write new node and next is equal to tail off next to that is here now six-hundred we have stored 600 right so now the thing is now this node is pointing to this node right this sign would be safe sacred the second thing what you need to update this one so how you can write this thing tail of next tale of next is equal to which address I want to store this address 7 700 so from where I can get this address in new node pointer is equal to new node so now here I have 700 right so now this is not pointing to the first node this is pointing to the last node right third thing you need to update now before closing this else here what you will write now you need to update this spell pointer also now tail would be containing address of the last node so here third line what you will write L is equal to new node in new node we have 700 now tail is also containing 700 now tail is pointing to this node right and now you can close else blow write these three lines you have to write in else no right same as inserted beginning just this line you have to add extra fine and if you want to check you want to cross out and after this else you can obviously print in printf you can write print a percentage beyond this thing tail next data right so tail mixed means 600 so data at 600 is seven so seven should be printed so this is how you can insert at end position now we will see how to insert at any specific position so now I want to insert at this node a newly created node at position suppose 3 means 1 2 & 3 here after this before this one right so here in this case see if position is 1 in that case 1 means here only you want to insert 1 means at the beginning only so in that case if position is 1 you can call that function insert at beginning right or second thing you will check position is valid or not suppose in this case position is 6 now is there any position 6 one here is position one here is position to position 3 position 4 but no position there that is six so that should print invalid position fine so you will check the length of the list length of the list is four one two three and four so if position is less than zero or greater than this four then it should print invalid position right now maybe you can say mommy position is five then also I can insert here it means we can call insert at and so you can implement that concept also but here I'm considering what if position is less than a 1 and greater than this length it means that position is invalid right so now obviously we are going to create this node we need a pointer that is new node and as well as we will ask from the user at which position he wants to insert right to store that position also we need another variable you can say position right and suppose user has entered position is three means one two and three here I want to insert so I have to reach till this position now so you have to traverse this this list so for ever single so we need another pointer to node because this new node is containing address of new node one pointer tail is containing address of the last node we cannot move the string so we need we need another point that you can say temp pointer for this traversing to reach till this position right so now we will ask from the user for the position like this using printf and scanf suppose user has entered here we have a position variable and user has entered position is three for Trevor single so we need one another variable that is I suppose we are initializing I is equal to one now first step is calculate this length and for that you can create a function in the in this program only get length function and that function will return the length of this list and that we can call that function in this function only that is in created position only and we can suppose get length is a function that will return the length of this list and we are going to store that in variable L so here I am going to declare one variable el oso right and we also check now if our position is less than zero or position is greater than this el it means here you can print invalid position in print f you can write invalid physicians right this how to calculate this length of this list that code is very easy if you want me to explain how to calculate the length of death of the list then you can comment being in the comment box I will provided that that video also fine now we will check now if position is this it means invalid a position we can not insert if position is seven we cannot insert that is invalid position again we check else if position is equal to equal to 1 in that case means that starting only I want to insert so insert add beginning that function you can call now suppose position is valid and position is not one position is now three so now we have to reach till this position till three so we will try it trace out this we will traverse this linked list till position minus one that is built to here after that I can insert here at third a position right and have you will to traverse this way I wanted really discussed many times in the previous video also so now in else part now we are going to create this node now we are going to allocate a memory to this node see here I have declared only a pointer we haven't allocated any memory to this because if position is not valid then no need to create this node if position is one then already that insert at the beginning function would be called now you can allocate the memory using malloc function right so now this is how we have allocated the memory to this node dynamically allocated to the memory using malloc function right ended is a pointer pointing to this node we have asked for the data from the user the user has entered seven and here in the next part we have stored 0 now I want to insert this here now we need to traverse right so here I'm going to write hit I guess this is everybody know how to write down this code so I am going to rub this now see we will traverse the list so for traversing we need to which is the first node we need a pointer to the first node but we don't have any head pointer here so now how we can come to know that which is the first node see in the till next we know that we always have an address of the first node right so here what I can write another pointer I have taken that is temp so here M in temp I can store what tail off next right so here I have temp pointer and what is the value of tail of Nyx see tail of next is having hundred so now this is pointing to this node means now we can say temp is pointing to this first node right so you can say temp is now I had pointer now we can reverse so we will write a while loop while this I we have taken one variable that is I is less than position minus one till then we will move this temp temp is equal to temp off next right and we will do I plus plus and we will close this while loop now as you can see my value is what one it's starting we have taken one now C 1 is less than position minus one position minus 1 is 2 so 1 is less than 2 yes now temp is equal to temp next so what is the temp next temp off next means 200 so that would be stored in M now M becomes 200 now temp is pointing to this node right and I plus plus now I becomes 2 now again to less than position minus 1 that is 2 2 less than to know that condition is not true so we are not going to enter into this loop we are not going to move this temp now see we have reached till position minus 1 because after this only I want to insert now position third here only right so now what do you need to update you are going to update two things now first thing is what we will update this link this node is now containing address of the next node that is here I want to store 250 right and this is going to contain address of the this node that is 150 here I want to store 150 right so these two links I want to establish this one and this one and we are going to break this thing this is how you can insert so now which link you will update first see first we will update the right link this one this one because if you updated this link first suppose you have updated here 250 how to access this part amp of next is equal to new node that is here we have 250 now so now here I want to store 150 enough room where I can get 150 from here only I can get 150 but this link we have updated already so first of all before updating this set the right link first so update this thing so how you can update that link that is new node next say new no order next means in this this part I mixes in this part here I want to store 150 150 address of next node from where I can get 150 here I have 150 so how you can access this part using this M pointer temp of next right now here I have 150 so now this is pointing to this node now you can update this thing so how you get it says this part temp off next temp off next what I want to store here 250 so the address of this node because this is going to be the third node now from where I can get 150 in new node I have 150 right and after that you can close this inserted position function right so the first of all else after that this one this function fine so now here I have 250 so this link is no more now and this is now pointing to this node and now you can call these function into that main function inserted beginning inserted end and insert at any position fine as well as create a linked list and hit display link list that two functions we have already discussed in the previous video right so this is how you can insert in a circular linked list and if you maintain both head pointer and tail pointer then I guess it is very easy to insert any data in the circular linked list insert at beginning also at end and at any position fine so I guess no need to explain that code fine so now I will see in the next video in next video we'll see how to delete data from a circular linked list fine so till then bye-bye taking