2.20 Insertion in Doubly Circular Linked List | Data Structure & Algorithm Tutorials

Right. In this video, we will see how to insert a new node in a doubly circular linked list. Insertion at beginning, insertion at end, and insertion at any specific position. Right? See this is what a doubly circular link list. Every node is having three parts. Data part. This pointer is containing address of the next node and this previous pointer is containing address of the previous node. Right? Plus here I'm maintaining also tail pointer and head pointer. Head is containing address of the first node. tail is containing address of the last node. Plus one more thing is see the next pointer of the last node would contain address of the first node. Right? And the previous pointer of the first node would contain address of the last node. Right? To make it a doubly circular link list. This list is having property of both doubly and circular. Right? You can see this this link is birectional link. Right? So now we will see first of all we will see how to insert a new node at beginning of this list. I want I'll create a new node right. I'll allocate the memory dynamically using maloc function and here I will insert that node at beginning. Right? So here I assume that you have created this list means you have called that create doubly circular link link list function and you have created this list in this list we have three nodes right that we have discussed in the previous video you can check out that video right and now I want to create I will create a new node and I'll insert that node here see now how we will write that thing see I hope everybody know how to represent this thing in coding so this is how we are going to repres Present this node right for this node we will define our own data type. This we have discussed many times in the previous videos. Struct node is the name of that data type. This complete is the name strct node. Three parts are there. Data part. One pointer is next pointer. One pointer is previous pointer. Right? So these pointers will contain address of the node. That is why here we will I'm writing strct node. Because here we will write what the data type of that thing whose address we are going to store in this pointer. Right? we are maintaining two uh pointer head and tail. So suppose we have created this list by calling that create function and now I'm going to define this function in insert at beginning. So now this node obviously we will have to create a new node right. So for that thing we will take a pointer new node. See this thing already we have discussed many times in the previous videos. Right now we will allocate memory to this node. How you will allocate a dynamic memory allocation using malo function right see so the syntax of malo is you'll write that maloc function in the bracket you will write how much size you want size of the name of that data type data type name is a strct node right and malo will return what see now this memory has been allocated how many bytes 12 bytes four for this for integer four bytes for four bytes for this pointer four bytes for this pointer four bytes for pointer in 32-bit compiler eight bytes In 64-bit compiler 12 bytes. So this block is of 12 bytes and this 500 is what address of the first bite. So this maloc will return this pointer to the starting address and maloc will return what? Void pointer and this pointer in this pointer we are going to store this address. Now but this pointer is what pointer to node. So you have to type cast this thing. So how you will type cast? The syntax is is you will write that data type array and this address we are going to store in new node pointer right. So now suppose address is 500 and we have stored this in five this new node. So now new new node pointer is pointing to this node. Fine. Now we will ask from the user which data he wants to insert right using print f and scan f. And how we will store that data? See we cannot directly access these structure members. So in data part I want to store now how you will access this data part. The pointer to this node is new node. So using new node address of the pointer name here you will write that arrow operator means how you will uh write this thing in your when you will write a C program hyphen and that angular bracket right and here the name of which part I want to access data part. So here I will write data. Suppose user has entered here seven. You can insert null or null. But that is of no use because obviously we will we we are going to update this pointer and this pointer because in this doubly circular link list no pointer is null pointer. Right? Now see how we will insert this thing here. Now we will check if list is empty. In that case what you will do? See now we will write a condition. If head is equal to is equal to zero. It means there is no node in the list. Fine. And this would be the first node. This would be the last node in the list. Right? Both head and tail would point to this node. Fine. Now here you will write head and tail would point to this node. That is in head and tail we will store address of this node that is 500. And this 500 is a new node. Fine. And plus now this would point to itself because the last node is containing address of the first node. And this previous pointer of the first node would contain address of the last node. But this is the first node. This is the last node. Right? So here also 500 and here also 500. In case when list is empty, there is no no node in the list. Right? So now how you will access this thing both head and tail and all the three pointers new node is pointing to this node. So you can access these data these parts using any of these nodes. It's up to you right here. Suppose I'm writing new node previous is equal to tail new node next is equal to head. See it is not compulsory that you will write these two lines here. Right? Here you can write head of next is equal to head. Head of previous is equal to head. Tail of next is equal to head. Tail of previous is equal to head. because all the three three pointers head, tail and new node would be having that same address that is 500 right so it's up to you how you will write this thing now else suppose I have now three nodes in the list and now I want to insert this node here fine now what you will do see here what you need to update this this would be the first node right so now the next pointer would contain address of Next node that is 200 right. So now how you will access this thing new node next. So here what you can write new node next equal to from where you can get this 200 in head we have 200. So here you can write head. So now here I have 200 means now this is pointing to this node. Next link. Now this would point to the previous node. So this previous pointer would contain address of the previous node. So this would be the pre previous node now. So here how you can access this part head of previous. So here what you can write head of pre is equal to address of the previous node is 500. From where I can get 500 in new node I have 500. So here I can write new node. Right? So now here I have 500. Right? So now this is pointing to this node. Right? Now you have to set three more things. Now this this previous pointer of the first node because this would be the first node now would contain address of the last node right. So now how you will access this thing new node previous. So here I can write new node pre. Now address of the last node is 100 from where I can get this 100 in tail I have 100. So here I can write tail. Right? So now here I have what? 100 means now this node this this pointer this pointer is pointing to the last node. Next thing this pointer see now the last node the next pointer of the last node would contain address of the first node. So this address that is 500. This should contain how you will access this thing tail of next. So here I can write tail of next equal to address of this that is 500 from where I can get 500 in new node I have 500 right. So here you will update what here you will write 500. So now this is not pointing to this node. Right? And this is also not pointing to this node anymore. Fine. So now you can see here we have set this link. This link this birectional link. Now this is pointing to this node and this 100. So this is pointing to this node. So you can see this link is birectional. Right. Next thing last thing you need to update what? Head. Now head would contain address of this node because this would be the first node. Now so head is equal to new node because address of the newly created node is in new node pointer. Fine. Now head is containing 500. So head is not pointing to this node. Now head is pointing to this node. Right? So I guess we are done with our insertion at beginning. See now here it is not compulsory that you will write all the lines in this order. Fine. See but in some point you have to take care like this here at first of all you can update these nodes the new node. New node next new node pointer means these two pointers. So here you can write new node next is equal to head. After that new node previous is equal to tail like this rather than head previous is equal to new node. After that you can write head previous is equal to new node. But what you need to take care is this head is equal to new node. This you cannot update first here because if you have updated head is equal to new node at starting here means head is now pointing to this node. Now how you will access this thing fine because we have bro we have broken this link and this node is also not pointing to this node because we haven't set this link uh right so we cannot update head here this you have to take care these uh points you have to take care after updation of this thing head previous is equal to new node after that you can update this head node head is equal to new node right but it is not compulsory that you will write all the lines in this order as I have written. Fine. Plus one more thing what you can do. See here new node previous is equal to tail. Here also new node previous is equal to tail. New node next is equal to head. New node next is equal to head. Right? Both the lines are same. So what you can do before if and else here after taking this data here you can write both the lines. this new node previous this new node next here before if else not after else you can trace out this algorithm this uh program by writing these two lines here rather than if in if an else block fine plus second case is you can trace out this thing by writing these two lines after else block you will find out the difference you'll find out the mistake automatically fine you can write down these line before if else not after if else Right. So now we will see how to insert a node here at the end of the list. So now we will define the function insert at end. Right? This node we have created using these lines only. User has entered the data eight here. Right? Now we will insert here. What you need to change in this code. See if head is equal to zero means there is no node then this would be fine. Right? All the three lines would be fine as it is. In else part you need to change. First of all, we will set these pointers. Now, this would be the last node, right? So, now the previous pointer of this node would contain address of the previous node, right? Because after inserting this tail would point to this node, means tail is equal to new node. But before updating this tail, what you need to take care, you have to update this thing because here I want to insert address of the this node, previous node. And from where I can get this 100 in tail, I have 100, right? So before updating tail first set this link new node previous here what you will write new node previous here you will store what address of this node that is in tail I have this address. So now here 100 right this is pointing to this node now now this would point to the next node. So here tail next tail of next would contain address of this node the next node because this would be the next node after this node 700. So from where I can get 700 in new node I have 700. So now here I have 700. So now this is not pointing to this node. Now this is pointing to this node. Now we have set these two links. Now you have to set what? This link and this link. Right. A new node next here what you will store the next pointer of the last node would contain address of the first node in doubly circular address of the first node is 500. Right? Now here we don't have 500. This new node is pointing not to this. Now the address of this first node is always in the head pointer. So here you will write head. Right? So here I will write 500 means this is now pointing to this node. We will draw this link after setting this link. So now this first node previous node of first node would contain address of the last node right. So head of pre head of pre the address of last node is in new node pointer. So here I will write new node. It means now here I have 700 right. So now this is also pointing to this node and this is pointing to this node. So we can set this link right like this. This link is birectional. This and this right to make it a doubly circular. Fine. Now last thing you need to update this tail pointer. Now tail would point to this node right? In tail we will store 700. So from where I can get 700. In new node I have 700. So now in tail I have 700. So now tail is pointing to this node. And that is done. This is how you will insert a data a new node in the last of the doubly circular link list. So I hope you got this coding. The diagram is little messed up but I guess you are getting my point. Fine. How you will insert the data at beginning at end at end. So now we will see how to insert a new node at any specific position. So now we will insert this node right. And suppose position is three. Any position you can take. Position three means 1 2 3. Here I want to insert you can say before this after this. Right? Here three and after that this would be fourth node. Position one means here at the beginning only. Right? Now if I give position five, it means there is no position five. So it should print some proper message that is invalid position. Right? Now see how we will insert this thing. Now suppose position is valid. We have inserted position is three. So this node I want to insert here at position 3 1 2 and three. Now what you need to update? See here the previous node of this previous pointer of this node would contain address of the previous node. That is address of this thing right that is 300. We will set this link plus the next pointer of this node would contain address of the next node that is 100. We will set this length plus the next pointer of this node would contain address of the next node that is this one. This would be the next node that is 400. Here also you will store 400 because the previous pointer of this node would contain address of the previous node. Right? So now you have to update four pointers here. Now see how we actually update these links. See to update to insert this node here obviously we need to reach till this position now till position minus one because we need some pointer pointing to this node. If any pointer is pointing to this node then only we can access this pointer this pointer and this pointer this pointer we can access using the new node pointer only. So we need some extra pointer you have to traverse the list till that position. Suppose in my list I have 15 nodes and I want to insert at position 10. So first of all I have to reach till position 10. Now or you can say till position 9, position minus one. After that only I can insert there because here we cannot directly access any node in the list. We have to reach we have to traverse the list. You can access only sequentially at starting. In this case we have only what this head pointer and this tail pointer value. Right? Now see we will take another pointer you can say temp pointer right now we will ask from the user for the position. So for that case also you have to take another variable in that variable we will store the position right and for traversing we are taking another variable that is I and I'm initializing this I with one right plus one more thing now suppose position is five then this program should print a proper message that this is invalid position right now you have to find out the length of the list right you have to count the number of node in the list here the length is 1 2 and three so valid positions are 1 2 and three only right if position is less than one position is greater than this three greater than the length then it should print invalid position right so here I'm also going to call a function that is get length function and that function would return this length of the list total number of nodes in the list right and that thing also we have discussed when we were discussing the implementation of single link list or if you want me to make a video on that case also how to find out the length of the list you can tell me in the comment box. Right? So for for uh storing that length of the list I'm taking a variable you can say l right now first of all I ask from the user for the position. So this is how using print f and scan if I have asked from the user for the position and suppose user has entered position is three right and we have a variable I I is equal to one in i we have one only fine now we will call a function you can say get length and that value I'm I'll store in this variable that is l so here I'm calling that function get length you have to write down the proper code for calculating this uh value right the length of the Now get length function would return three. The length is three. So in L variable I have value three. Right? Now I I'll check for the position. If position is less than one or position is greater than this L, it means here you will print a proper message that that is invalid position in print f. else if you can say if position is equal to is equal to 1 means here only I want to insert insert insertion at beginning. So here I will call that function insert at beginning and that we have discussed already right you will directly call this function else if position is valid and position is not one like in this case position is three then what you will do so now we will allocate memory to this node because here we have only declared this new node pointer we haven't created this node right so now we will allocate the memory using that malocope function and the fun that uh syntax I guess everybody know how to write down that thing and we will ask from the user for the data which data he wants to insert using print and scanf I guess everybody know the syntax and suppose user has entered minus one now I want to insert this node here now first of all we will traverse this list till position minus one till two so now I have taken the temp and we will initialize the temp right and temp would point here because from the First node only we are going to we are going to start out traversing right. So the stem should contain address of the first node. So now after this only after this declaration after this line in POS I and this L before taking the position here only you can say what temp is equal to head. Here you can write this line. Now temp is pointing to this node. Right? Now we will start a traversing. We will apply a while loop while I less than position minus one. Till position minus one we are going to traverse till then we are going to move the temp. So temp is equal to temp of next and what I ++. So here you can see I value is one position minus one position is three that is two I one less than two. Yes temp is equal to temp of next temp is pointing to this node temp next is 300. So this 300 would be stored here now. So now temp is pointing to this node right 300 I ++ now I becomes two. Now again check the condition two less than position minus one two less than two. No. So now we are going to we are not going to move the stamp. We are going to stop. We will not enter this while loop. We will the control would go out from this while loop. Right? As you can see we have reached till position two. After this I want to insert. Right? So now the coding I will write here. So now after this while loop what you will write how you will insert this thing here. See first of all it's better to uh create these new links rather than updating the previous links because for updating this you have to break these links. So rather than breaking the already set links first of all set the new links. So update these links here new node previous and new node next. So in new node previous what you will store here address of the previous node that is this node 300 from where I can get 300 in temp I have 300. So here temp means this is pointing to this node. Now set this link means how you will access that thing the pointer to this node is new node. New node next is equal to here I want to store address of the next node that is 100. From where I can get 100? Here I have 100. And pointer to this link is temp. So you can access this using temp next. Temp next. So here I have 100. So this is now pointing to this node. Right? Now update these links. See how you will access this thing. Here I will store address of the next node that is 400. So temp of next is equal to new node. Fine. Now here the previous pointer of this node would contain address of the previous node that is this node that is 400. But how you will access this part of this node. Is there any pointer to this node? We don't have any pointer to this node. Right? See don't consider this tail pointer because suppose in uh list I have 15 nodes and now I will I'm inserting at position three. So tail would point to the that 15th node. Right? We cannot access this node using tail. So here don't consider this tail. We cannot access this using this tail. Right? Now see how we will access this thing. We don't have any pointer direct to this node but address of this node is 100 and here I have 100 right this pointer this node is still pointing to this node right we haven't broken this link so now can we access this part yes we can access using temp pointer temp of next so here what you can write temp next it means we have reached temp next means 100 means we have reached till this address once we reached till this address right then you can access this part this part or this part any of the three three parts just by writing again an arrow and name of that part name of this part is previous now here I want to store address of previous node that is 400 so from where I can get 400 in new node I have 400 now here I have 400 so this link is no more and this is now pointing to this node now you update this thing temp of Next temp of next here you will store address of the next node that is 400. In new node I have 400. So now here also I have 400. So this link is no more and this is also pointing to this node. Right? And this is done. This is how we are going to insert a node at any specific position. Just you need to take care of this thing that if position is one then you call that insert at beginning function. Right? In that case we cannot write down these lines. These lines will not work. And now in main function you can call all these function. First of all create function. Then you can call display function. Then you can call insert at beginning. Then insert at end. Insert at position. Right? Write down the name of those these function. Right? And after that you can again call the display function. Right? So that's all about insertion. In next video we will see how to delete a node from a doubly circular linked list. So, I'll see you in the next video. Till then, bye-bye.