2.11 Insertion in Doubly Linked List(beginning, end, specific position) | Data Structures

We have discussed the introduction of doubly link list. What is doubly link list and how to create a doubly link list as well as how to display the content of a doubly link list. I'll provide you the link of those video in the side button. You can check out there before going to this video. You must check out those videos. Right? See in the previous video we have created a doubly link list. Right? Like this one head pointer is there. This is the node. Each node is having two pointers. One is pointing to the next node and another pointer the previous pointer is pointing to the previous node. Right? It means this pointer is going to contain address of the next node and this pointer is going to contain address of the previous node. Right? And this is what the data part three parts are there basically. Right? We have already discussed how to represent this node when you are going to write down a C program. Right? And see in that case we haven't uh maintained a tail pointer in uh this double link list. It is you know very useful to maintain a tail pointer. Why? So that thing also we will discuss. Now what is a tail pointer or you can say a last pointer. See this head pointer is going to contain the address of the first node right or you can say the head node. So the tail pointer is containing the address of the last node like this. So in this case we have a pointer to the first node of the list also and to the last node of the list also. Now what is the use of this tail pointer? Why we are going to maintain this pointer? See when you are going to insert any node in the last suppose I want to insert at end and I'm not maintaining the stale pointer. Right? In that case what we will do? We cannot directly insert here. We have to traverse the list till end right because sequential access is possible and we have the information what you have we have just this head pointer we just have the address of the first node right that is why you have to traverse the list till end after reaching till this end now you can insert here right if the tail pointer is not there and if you maintain while creating the list If you maintain the tail pointer in that case you don't need to traverse the list till here. Why? So directly you can insert one node here because we can access this node using the tail pointer right we have the address of this last node. So simply you can update these links right how we are going to update these links that also we are going to discuss when when we will uh discuss this function insert at end right. So in this case the insertion in doubling link list at end will take time order of one if you maintain the stale pointer. If you don't maintain the stale pointer in that case you have to traverse the complete list. It means it will be order of n and same with deletion. If you want to delete this last node and if you maintain the stale then time complexity would be order of one. And if you don't maintain the stale then the time complexity would be order of n. The delete operation also we'll discuss in next video. So these are some advantages of maintaining the stale pointer. But the drawback is what? This is going to take some memory space. Right? You have to store the stale pointer. Four bytes if 32-bit compiler is there and 8 bytes if 64-bit compiler is there. If you don't maintain this then only if three nodes is there then this this this node and the head pointer you have to store but if tail pointer you are maintaining then you have to store this also some memory space would be required to m to store this tail pointer also and you have to maintain this also if you are going to create a list in that case you have to maintain the stale pointer at starting if list is having only one node then head is also 100 tail is also 100 if you have inserted second node then head is 100 But tail is now 200. If you have inserted this node then tail becomes 250. So you have to maintain the value of the stale pointer also. Right? Now how to we have already discussed how to create a link list. But in that case we haven't maintained the stale pointer. If you are going to maintain the stale pointer then how you are going to create the dlink list. I'm quickly write down the code for that thing. This is what we have declared our own. We have defined our own data type that is struck node for this node. You can say the data type of this node three parts are there. One is data part and two are pointers and these are pointers to node. That is why here data type is strct node. So here we are maintaining what? Two pointers head and tail. So we are going to declare two pointers strct node estric. One is head and one is tail. Right? These pointers are containing address of see head is containing address of this node. Right? So here that is why I'm writing we are writing the address of those thing or that that variable whose address this pointer is going to store. So that is why here I'm writing struck node because data type of this node is what struck node. Now how we are going to create the list? We are going to define a function you can say create double link list. Right? So first of all we are going to create a node. Right? First of all, we are going to create these type of nodes so that we can store these values and these pointers and memory. How in the memory is to be allocated? Dynamic memory allocation that we have already discussed many times. So I'm going to write down that thing here. Right? First of all, what you will do? You will declare a pointer struck node type and this is how you can assign the memory dynamically to this new node. See this this thing this syntax we have already discussed many times right right maloc is the function for dynamic memory allocation how much size you want size for this node right so here you write size of the data type data type is struck node and malo is going to return a pointer to the starting address of the allocated space or you can say meloc is going to return a void pointer and this pointer is what pointer to a node so that is why you have to type cast this pointer type cast means you are going to write here struck node estric and whatever this fun this will going to return you are going to store that address in this new node pointer so after executing this line one node has been created means memory has been assigned to that node so here suppose I'm taking that we don't have anything in the list the list is empty right so you can say we have created a node address suppose is 100 and this new node is a pointer that is going to contain the address of this newly created node fine say this node is having how many bytes? Four for this, four for this and four for this. 12 bytes. And this 100 is what address of the first bite. Right? So it will melo will return this address. So now this address we will store in this new node. Find new node is pointing new node pointer is pointing to this node. At starting we assume that head is equal to zero. It means we don't have anything in the list. And we have just declared this tail pointer also. Fine. Now we are going to insert this newly created node in the list. Now first of all we are ask we will ask from the user what data I want to insert here. So this is how you can ask from the user using print fence scan if the data I want to insert here. Enter data and how you will insert the data here. How you can access this part of this node. This part you cannot directly access this node. You can access this using a pointer. We have we have one pointer pointing to this node. So new node new node and this arrow operator and which part you want to access data part. So the data address of new node and data. So here suppose I have inserted five. And now here you will insert zero and zero first of all. So how you will in uh access this part that pointer to this node is new node new node arrow and name of this pointer is previous. So is equal to zero. New node arrow next is equal to zero. Fine. Now I want to insert this node in this head pointer. Now how you will insert this thing? See first of all obviously you have to update this head value here you will store what 100 it means after that this is going to point here fine and the next there is no next node so this is fine it will be zero there is no previous node so this is also fine that this would be zero now one another thing you have to do we are maintaining this tail pointer also so in tail also you are going to store this 100 so now tail is also going to point here. Now this is done. Fine. Now how we will write this thing into this code? We have just updated head value and tail value. So here what I can write head is equal to tail is equal to here you will store 100. From where we can get this 100 address of this is stored in this pointer. So here I can write new node. See but this is the case when head is equal to zero. It means when list is empty. If suppose we have inserted this data one node and I want to insert second node right and second node the address of second node is 200 in that case the new node will contain 200 right and if in that case you will do head is equal to tail is equal to new node means both head and tail are going to point that new node that is 200 is going to store in head and tail now you are going you'll lose the reference to this node so this should not be a case so before writing this you will write if condition if head is equal to is equal to zero in that case only you will write this thing that is fine but if head is not zero then in else part what you will do now this is suppose the list now I'm I'm I want to insert a second node in that case what we will do now suppose we have created one more node address is 200 this in this new node now 200 is going to store we have asked from the user using this new uh print f and scanner If the data inserted is six and here is 0 and 0. Now I want to insert this node into this list. So now if head is equal to zero but head is now 100. So this condition is not true and tail is also 100. So now we are going to enter into else part. Now in else part what you will do? See what you are going to update here this part also and this part also. Here you will store what address of previous node that is 100. And here you will store address of next node that is this 200. Fine. After that this link would be established and this link would be established. Plus one more thing you are going to uh update this tail also. Now tail is going to point here because this is the last node. So in tail you will store address this that is 200. So here you will store 200. Right? Three things you are going to update. Now see now first of all this was zero. So how you can access this part both using head pointer and tail pointer because before updating this tail pointer is containing 100. So I can write here tail next tail of next here you will store this one where we from where you can get 200 from this new node because new node is containing 200 is equal to new node. So here we I can write 200. So this link is established now. Now how you can access this part? The link to this node is pointer to this node is new node. So how you can access this new node and the name of this part is previous. Here you will store 100. From where you can get 100 using this tail or you can say using this head. So here I'm writing what? Tail. Right? I'm not writing head because see we cannot move this head. When you will insert the third node then obviously the address of second node we are going to store here and tail is containing address of the first node only right. So here we are going to write here only the tail because we can move this tail only. We cannot move this head. So now this is containing 100. Now remaining part is you are going to update this tail. Tail is equal to new node. From here we can store here 200. Now tail is pointing to this node. Right? Now the same logic you can apply. After this it will ask you do you want to continue and if you press one then another node would be created and inserted. If you press zero then no extra node would be created and only you can call after that you can call the display function. So that thing we have discussed how you will write here you can write print f do you want to continue in scan f you can take the value from the user and you can write down a while loop here before this line before this line because if you if you will insert one in that case only new node would be created. So before this line you can write down what while and choice right choice is a variable you can take in this function only int choice is equal to one right and here also print f do you want to continue in scanf you can write percentage d address of choice this is we have discussed already here the main moto is what how you can uh maintain this tail pointer so I hope you got the concept now we are going to insert at beginning how you'll write this function So now let us take this case. We have these three node in the dl link list. Head is containing 150 and tail is containing the address of the last node that is 200. We have created this list by calling the create dl function. Now I'm going to insert a node and at the beginning of this list fine so this thing we have already discussed many times. We have created this node that is new node. We have allocated the memory using the melo function dynamic memory allocation and the address is 500. So this new in new node pointer we are going to store what 500. So now this is pointing here. Now we have taken input from the user using the sprint f and scanf enter data and we have user has entered what the six value is six. So we are going to store the value here in the data part. So how you can access this part address of new node pointer is new node arrow operator and name of this part is data. Fine. And here we will store zero and zero. See here you can store in the previous pointer obviously this is the first this is going to be the first node. So in the previous node null would be there. So here I can store new node previous is equal to null. But we are going to update this pointer. So if you you'll not store this new node next is equal to zero. That is also fine. You can only write new node previous is equal to zero. Now how to insert this node into this list. Right? We assume that list is not empty. So we are not going to write down that condition. If head is equal to is equal to null in that case head is equal to tail is equal to this new node only one node is there. I'm here assuming that we have three node in the list. So how you can write? If you want to write you can write down that condition also in else part you can write whatever I'm going to write here. So now which link you are going to update. See you have to update this link. First of all, this is going to contain address of this node. Because this is now the first node, right? So here you will store what? Address of this node that is 500. Here you will store 500. So how you can store this? This 500. Here how you can access this part. The pointer to this node is head. Yes, we have a pointer. So we can access all the three parts. So here what you can write head of previous this part is previous is equal to from where I can get this 500 this address in the new node we have 500 so it's equal to new node. So now this is now containing 500 fine. So now this is pointing to this node. Now again you have to set this link. This node should point here. So this node should contain address of the next node that is 150. Right? So here you will store what? 150. How you can access this part? The pointer to this node is new node. So here I how you can access new node. This part is next. Name of this pointer is next. Is equal to from where I can get 150 value in head pointer is 150. So is equal to head. Now this is pointing to this node. Now you have to update one more thing that is head. Now head is containing address of this thing that is 500. So here you will store 500. So now head is pointing to this node. This is the first node. Now from where you can get this 500 from this new node head is equal to new node. Right? So this is how you can insert. This is done. Now this is how you can insert this insert at beginning. No need to uh change the tail value. Right? Now next thing is how you insert how you will insert at end. So now the situation is something like this. After inserting at the beginning we have now four node in the list. 1 2 3 and four. And now I want to insert a node at the end right here. This node I want to insert here. So I hope you got that this coding would be same. Here I have just updated the name of this function that is insert at end. Same we have created this node dynamically we have allocated the memory address is suppose 400. This 400 would be stored in this new node pointer. We have taken the data from the user. We have here we have put seven and here we have put zero and zero. Now how to insert this data here. See if you don't maintain the tail pointer suppose tail pointer is not there. Now how you can access this part because for because for inserting this node here you have to update what? You have to update this part. Here you will store what? 400 rather than zero. Here you will store 400. Right? But we cannot access this part because we cannot directly access the structure uh values or you can say the variables. You need some pointer pointing to this node. But here we don't have any pointer. That is why if tail pointer is not there then you have to traverse till here. Like we have discussed in single link list using a temp pointer. Temp is pointing here then here then here and then finally temp will reach here. After that using temp we can access this part. But here and in that case the time complexity would be what order of n because you are traversing the complete list. But here we have maintained a tail pointer already. Right? So no need to traverse the list. We can access this part directly using the tail pointer. Right? So no need to write down the while loop for traversing. Simply you will write. So how you can access this thing? The pointer to this node is tail. So here you can write tail of next. The part of this the name of this part is next is equal to from where I can get 400. The address of the next node in the new node pointer is 400. So here I can write new node. So 400 would be stored here now. So now this pointer is pointing to this node. One another thing you have to take care the previous node of the newly created node here you will store what previous of the sorry the address of the previous node that is 200. Right? So how you can access this part? The pointer to this node is new node. So here I can write new node and the name of this part is previous is equal to from where I can get 200. Tail is containing 200. So here I can write tail. So now this is also pointing to this node. One one more thing see you have to update this tail also because here the last node is this one. So tail in tail you should store address this 400 from where I can get 400 from the new node. So here I can write new node. So now tail is pointing to this node right and this is done. See this tail is equal to new node. Please don't write this here at starting. If you write tail is equal to new node here means tail is equal to new node means now tail is containing 400. So this is pointing to this node. So now how you will access this part because you have already changed the tail value that is 400. So now we don't have any pointer to this node. So we cannot access this part. So better you change this pointer this pointer first after that update the tail value. Right? So now next thing is how you can insert any at any specific position. So now we will insert a node at a specific position. Now suppose user enter that I want to insert a node at position three. It means 1 2 and three. After this here I want to insert before this and after this because position third is here only after these two nodes. Right? So now first of all you will check if position is in negative or less than one then you can say invalid position. If position is greater than the length of the list it means also that is invalid position right and how to calculate the length of this uh list using the predefined function that is length function you can use and you can calculate the length and store that length into a variable you can say l or you can say ln or you can say length variable and in if condition you can check if position is less than one and position is greater than length it means that is invalid position in else part what you will write that thing here I'm going to write so first of all in this function what you can write you can ask from the user enter the position and in if statement you can write if position is less than one or greater than the length then you can say invari position right here in this function you can declare this uh variable that is int posine and suppose if position is one it means position one means here at starting only you want to insert fine so here you can write else If position is equal to is equal to 1. In that case you can simply call that function insert at beginning. Fine. If you have created all these function in the same program or you can write down here if you are not creating in the same program then here you can write down that code insert at beginning. And now in else part. So now if suppose position is three user has entered position is three means 1 2 and three here after this node and before this node. So you have to create a newly new node uh you have to assign a memory using maloc function we will here we will put seven here we will put a zero and zero how we are going to create that this thing you have I have already discussed many times. So I'm going to write down here simply that thing. So now see this is how we have created this new node. We have taken the data from the user that is seven. If you don't insert here seven and seven that is also sorry 0 and zero that is also fine because you have to update this thing also and this pointer also right now how you can insert this thing at position three we cannot directly insert here you have to traverse the list till here so we are we we are traversing the list till position minus one means till this second node right so how you can traverse using a while loop so here what you will write while and using a variable Suppose I'm taking a variable I. I less than position minus 1. Right? Position is three. So 3 - 1 that is 2. Till here I want to traverse the list. So here you have to declare this I variable also in this function void insert at position. After this when you are going to declare this post here also you can declare int i is equal to 1. You can initialize this also to one. Suppose I is one. From here I want to start. So now see I value is one at starting. I value is one position is suppose three. So now how you will traverse this list till here. See we cannot move this head. So we are going to take one another pointer right pointer to a node. So here you have to declare one another pointer. Suppose here I can declare struck node new node and one more pointer you can say temp right and at starting temp is equal to head. temp is also pointing to this one that is 150. So temp is also pointing to this node. So here in else part after declaring the temp here what you can write temp is equal to head. Right? Now you can move the stem. Now see I less than position minus one. I is one position minus one that is two. So one is less than this. Right? How we will move this thing? First of all then we will move the stamp is equal to here. It means now temp is going to store address of the next node that is 100. From where we can get this 100? Here we have 100. So here what you how you can write temp is equal to temp next because this part is what temp of next. So now temp is containing what? 100 and temp is now pointing to this node and we will do what? I ++ right now in I ++ now I becomes 2. Now check 2 less than position minus one. Two less than two. No. So we are not going to move this temp. Now see we have reached till that position till position minus one because after this only you are going to insert now position is three 1 2. So here I want to insert this node. Right now we have reached till this position. Now we are going to write down the code how to insert this node here. See I'm going to rub this thing. See this is just you you have defined your own data type. This thing you will write outside of these function and outside of the main function that is globally because we are accessing these this thing in all the functions. Right? So now you have to update four links. One is this. This will contain address of the next node. Next is this newly created node that is 500. One is this. This will contain address of the previous node that is 500. One link is this. This will contain address of the previous node. Now previous of this node is this one that is 100. And here you will store address of next next node that is 200. So four links we are going to update. Now first of all it is better to maintain to better better to update these links. So here what you will store address of the previous node. Address of the previous node would be 100. So from where I can get this 100. See the temp value is now 100. Right? So simply what you will write how you can access this part new node previous. So here what I can write new node previous is equal to temp. Now we have updated this link. Now update this link. Here you will store address of the next node that is 200. So now from where I can get this 200. See here the tail is also containing 200. But always that is not case. Suppose I have 10 node in the list. So tail will contain address of the last node. So we are not considering the stale now. So from from where I can get this 200 from here. Now how you can access this part? Here you will store 200 means it will point to here. So first of all how you will access this part? See new node next. So new node next. Now how from 200? How you can access this part? This 200 how you will get this thing link of this node is temp. So here you can write temp of next. So now this link has been set. Now you can update this and this. So now here you will store what address of next node that is 500. Here also address of previous node that is 500. So here also 500 and here also 500. And from where we can get 500 that is new node. But the main point is how you will access this part and this part. See how you can access this part? Simply pointer to this node is yes we have a pointer that is temp. So how you can write temp of next is equal to new node. So now this link has been set. Now we have 500 here. So this link has been broken and this is now pointing to here. Right? Now how you can access this thing because we don't have any link to any uh pointer to this node. Right? Just don't consider now the stale pointer I'm considering that suppose I have 10 node in the list and tail is pointing to the last node right so now how you can access this part see the address of this node is 200 right how you can reach till 200 see here we will have 200 right and how you can access this part the link of the pointer to this node is new node so here what you will Right? New node and this part is next. It means we have reached till here till 200. Right? Now at this pointer also we are going to insert we are going to access this part means previous part. So here again multiple arrows you can write and the name is this previous. Right? Now we this is how we can access this part. So here you will uh store 500 that is the value of this new node right. So now here 500 is there this link has been broken and now this is also pointing to this. See I'm not saying that this is the only method you can update these links right maybe uh after this temp is equal to 100. So you can at this point only you can write down you can take another pointer that is temp one or you can say next node and at next node you can store this 200 from where you can get 200 because before updating here we will have 200 right so in next node we can write next node is equal to temp of next so now next node is pointing to this node right so you don't have to write these multiple pointers you have a pointer to this node also You have a pointer to this node also. Right? After reaching after this while loop here you can write maybe you can say next node is equal to temp of next. Here you have to declare one another pointer that is estric new node. In that case you have to take two pointers. But see the concept of two pointers basically we use in singly link list. But here only the single node is having previous node address and next node address. So no need to maintain two pointers using uh single pointer only we can insert any node in any spec at any specific position and one third method is also there to access this part right before updating this before updating this 500 here value is 200 right so how you can access this part here you can write temp next temp here you can write temp next and after that again arrow and then previous and there you can store new node. So third way is also there right? If you go to this point then you can write down in the comment box what is the third way how you will write that thing. So now we will insert a node after any position. So now the function is insert after position. Here the coding would be uh same except few changes. See after position means suppose now position is three 1 2 and three. So after third here I want to insert. It's not like at third 1 2 3 here I want to insert in that case here I I will insert fine so here I can take that case suppose suppose position is two means one and two so after this after two here I want to insert same thing see at starting I'm considering this this and this three nodes and this is the newly created node and this node I want to insert here so now everything would be same now what you have to change same you will enter the position you will ask from the user if position is you will position is valid or invalid. If invalid then you will print invalid position in else part see you will not write this case else if position is equal is equal to one if position is one means one so after this one here I want to insert this is not a case of insert at beginning right so this you will not write in this case after position case after this invalid you will write directly else and now you you are going to create a new node like this you will ask from the user what data he want to insert so now in while loop what you will write the condition suppose whose position is two here I'm taking the case where position is two see position is two this case after this here I want to insert right so now we are going to traverse the list till this position right so here you will insert I less than position only not position minus one because in that case if you insert insert at position position is suppose three means 1 2 and three here I want to insert so you have to traverse till two means position minus one but here after position I want to insert so you have to traverse till that position not position minus one if you if position is two and you will traverse till position minus one then how you can insert this node here right so you have to reach till here so I is less than position now and this this coding would be same if you don't use this another pointer simply You can write this thing here. So here I'm not going to explain this thing. I recommend you to please practice the operation of these d link list and tell me after writing the same code and this change whether insert after position function is working properly or not. See I recommend you to please write down this code with your own hand. Please type each and every line. It's not like that copy the code from the net and just simply run the program and yeah it's done because if you want to remember the things for a long amount of time for a long period of time then it's better to type each line with your own hand. So here now what about time complexity? See if you want to insert at beginning then order of one. If you want to insert at end if tail pointer is there then order of one. Right? If you want to insert at any specific position then it depends on the then you can say it is proportional to the number of elements in the list. You can say if you want to insert in the middle then how many uh node you have to traverse n by two half node. So in that case it is order of n. So in next video we'll discuss how to delete a node from a dlink list. Right? So I'll see you in the next video. Until then, bye-bye. Take care.