2.12 Deletion from Doubly Linked List (beginning,end,specific position) | Data Structures Tutorials

Right. So, uh I'll provide you the link of all these video in the description box as well as you can check out this I button. Fine. In this video, we'll see how to delete a data. Delete from beginning, delete from end and delete from a specific position or you can say delete from any given position. Fine. See suppose I assume that uh we have created a double link list having three nodes. Two pointers we have. One is tail pointer and one is head pointer. Head is going to store what? Address of this first node. Tail is going to store address of the last node. This thing we have already discussed in the previous video. Right? How to maintain this tail and head and how to create this uh double link list. Right? Now I want to delete data from beginning. See this node I want to delete in the list from from the list. Fine. So now what you have to update for this? See if you want to delete this node in that case the head will contain address of this node right. So in head you will store 400. Fine. Now head is going to point here. Second thing what you have to update now this would be the first node right. So this link the previous link of this node would contain null. Why? So because we have we will delete this node. So this is going to point where null. See this is I I guess you know the node is having three part. This is data part. This is what containing address of the next node. This pointer is containing address of the previous node. So that is why here also you will store what? Zero. Fine. Means we have detached this node from this list. But still we have to free this space because see this space is still allocated to this node. Although we have detached this node from the list but second task is you have to free this memory because see memory is very crucial part. So we cannot leave it like this. This is uh just a garbage now. So you have to clean this garbage. Now how you can free this memory? You can use a free function. In C we are using free function. And in free function what you will pass a pointer to this node or you can say address of this node that is 200. Fine. So suppose one pointer is there which is pointing to this node and name of the pointer is temp. So here we can pass temp. If there is no pointer then how you can access this node. How you can get this 200. Fine. So one another important point is you have to maintain a pointer to this node. Fine. So you will take another pointer that is temp. Now how to delete this? Now see how to delete this node. See we are going to create a function. You can say void delete from beginning. Fine. And here first of all we are going to take another pointer that is temp. And why we have I have already discussed here. So I'm going to take another pointer that is strct node estric temp. Why I'm taking this str node? we have already discussed many times in the previous video. Fine because this pointer is going to point this node. So here what you will write here always see if if I write int star p it means this is a pointer p and it is a pointer to integer. It means this pointer is going to store address of a integer variable. So here we always write the data type of that variable whose address this pointer is going to store. Now here this temp is going to store what this 200 means address of this node and type of this node is we have already discussed we will define our own data type that is strct node so that is why I'm taking here strct node fine so now see so now we have taken another pointer that is temp is not pointing to this node now still fine now see first of all we will check if there is no node in the list then we cannot delete anything. So you can check what if this head pointer is equal to is equal to zero means null it means here you can print what list is empty otherwise we will do what now see in else part what you will write now first of all we are going to point this pointer here fine so now in temp we are going to store what temp is equal to head that is this 200 the address of this node 200. Now temp is also pointing to this node. Fine. Now we can update this head value and this value. In head we are going to store what this 400. Fine. Now from where I can get this 400 address of this node C this node is containing 400. This pointer the next pointer. And how we can access this node? We can do what? This head is also pointing here and temp is also pointing here. So basically we'll use what head. So here you can write now head is equal to head of next. It means head next value would be assigned to head. Head next value is head. Next means 400 would be assigned to head. Here we will write 400. Now this length has been broken. Fine. Now this head is pointing to this node. Now another thing what you will do obviously we are going to break this link also. Fine. Now here this would be the first node. Now so in the previous node of first node we would store what? Null that is zero. So now how we can access this part. Now pointer to this node is what? Head. We have set this pointer. So how we can access this part? We can write head and previous is equal to null. It means here we are going to store zero. It means this link has been broken. Fine. And if you want you can also store here zero. You can say how we can access this node temp of next is equal to zero. So here also we can store zero and this link would be broken. Otherwise by writing these two lines simply you can do what? Now you can free this memory. Now how you will free using a this free function. free and in free what you will pass address of this node from where I can get this this temp pointer is pointing to this node temp is containing this address so here I can write temp and now this node has been deleted the memory has been freed now this is how you can delete a data from the beginning these four lines code would be there fine now we will see how to delete from end so now to delete this node what you have to do. You need to break these links. Fine. Means you have to store here what? Zero. Means this node is not pointing to any node. Now fine. How we can access this part? See obviously we don't have any pointer pointing to this node because directly we cannot access this part. We we need some pointer uh variable or we need some structure me structure variable. Fine. So that is why in single link list or if in this case also if you don't maintain this tail pointer then you will have to traverse the list till here after that you can delete this data but we have already a tail pointer pointing to this node. Now no need of traversal order of one time take would be taken for deleting this node. See now how we can update this part. See how you can access this part. The address of this node is what? 400. From where I can get 400 here we have 400. Fine. And the pointer to this node is tail. It means tail previous. Fine. We have reached here. Now how we can access this part. Tail previous. And this is what next is equal to zero. This is how you can set. Fine. One more thing you will set what? You will also update this tail pointer. Now tail will contain 400. Right? And from where I can get 400. See here we have 400. So from here I can get 400. I can store here. So simply first of all we will do what and and uh third thing is also you you are also going to free this memory fine because after updating here suppose now tail is containing 400 so now this link has been broken and this link also has been broken fine so now how you can access this node we are also going to maintain a pointer that is temp which is going to point this node and after that we can do free and temp. So now first of all what we will do we will declare another pointer that is temp means we have another pointer temp and temp is not pointing to anywhere. First of all we will check if tail is equal to is equal to0 or head is equal to is equal to 0. It means list is empty. So here what you can print simply list is empathy. Fine. I guess you can all uh write down this thing. Now in else part what you will do. Now we will initialize the temp pointer. Temp is equal to tail. Now temp is also containing 150 means temp is also pointing to this node. Now we can update this temp value. Now temp we can set this temp pointer pointing to this node and after that we can free this node using this temp pointer. Fine. We can change this tail pointer. Now now see how we can do here. Here I want to store zero so that this link I can break this link. Now how we can access this part see this this part of this node fine that is 400 from where I can get this address here we have 400 and pointer to this node is tail also and temp also fine so you can access this node using temp or tail so here I'm writing what tail of tail of previous fine and again double pointer tail of previous means we have reached to this address now this I want exactly I want to reach till this location and now this is What? Next. The name of this part is next is equal to zero. It means here now I have zero. Now this link has been broken. Fine. Second thing we are also going to update this tail. So in tail pointer what we are going to store that is 400 address of this node. Now from where I can get 400 from here. Fine. And how we can access this part? we can write tail of tail of previous that is 400. So here now I have 400. So tail is now pointing to this node. Right? Now I can free this memory. So so here simply you can write free temp because the pointer to this node is temp. How we can access this address? Using temp. And this is done now. Now this node has been deleted. Right? This is how we are going to delete a node from the end of the list. Fine. And this will take time complexity order of one because uh we just updated these links. We haven't done any traversal. And from beginning also it it is it will take order of one because we just in that case also we have just updated the links. Fine. Now we will see how to delete a node from a specific position. Now before going to the third function I want to tell you something. See if you don't get this double pointer concept then what you can do. See suppose we haven't updated this part. Still we have this link pointing to this node and tail is not pointing to this tail is still pointing to this one. Tail is having now 150. Fine. So first of all what we can do first update this tail pointer. So first you will write temp is equal to tail. And after this line don't write this line directly line this line tail is equal to tail. previous means tail is equal to tail previous that is 400. Now it is having 400. So this link has been broken and now tail is pointing to this node. Now we can update this part. How you can access this the node the pointer to this node is tail. Now after this line after this line do not write this line you can directly write tail of next is equal to zero. So now here zero this link has been broken. After that you can write free time. So two is how you can write this thing or this thing also. Fine. So now suppose this is our list. We have four node in our list. And I want to delete this node. The position is three. 1 2 and three. This node I want to delete this one. So now you have to update what you need to update this link and this link because this node will directly point to this node and this node will directly point to this node. So now how we can access this part and this part how we can change obviously we need some pointer using a pointer only we can access these parts and second thing the need of pointer is what obviously uh we want to free that memory fine so I want to use that free function so so I need a pointer pointing to this node fine so that I can free this suppose I want to delete this data and I'm have a pointer I'm having a pointer pointing to this node that is this one so after updating this link and this link This these links has been broken. Fine. Now I can free this node. Free temp. Right. So now how we can set this pointer to this node? You have to traverse the list because only we have this tail value and this head value. Fine. Now we will start the traversing from here because sequential access is possible till this position. Once we reach till position then we are going to stop. After that using a single pointer only I can update this also and I can update this also because in the single node I have address of the next node and address of the previous node. That is why deletion is also easy in doubly link list because in this case we need only one pointer but in singly link list we need two pointers. Fine that we have already discussed fine you can check out that video in this I button. Now see what you will do obviously we'll ask from the user from which position he wants to delete the data and to get the input we need a variable you can say post variable fine and also we are going to take one this I variable I is equal to 1 for traversing fine now see and we are going to take this temp pointer also so how you can declare this strct node estric temp and Now temp is not having anything. So temp is now not pointing to this node. Right? Now see if position is one in that case that case is similar to delete from beginning. Fine. So in if you can write if position is equal to is equal to 1 then you can directly call delete from beginning function. And if position is this one end of this list then simply you can call delete from end. Fine means how many you can count how many nodes are there. 1 2 3 and four nodes and if position is four then you can say it is the you want to delete from the end of the list. So you can call delete from end otherwise you will implement the logic to delete from a specific position. So first of all we will ask from the user using print f and scan f enter the position right and after that we will traverse. So suppose user has entered position is equal to three. So in post variable we have value three and we have one more variable I in that we have one. So now we are going to start traversing till this position right because we need a pointer to this position for freeing this memory. So now here what I can write while I less than post till then we are going to traverse fine. So now at starting what you will do how you will traverse obviously we cannot move this head. So we need a pointer. We have declared one pointer temp and we first of all set this pointer to the first node and then we are going to update this temp. Then we are going to update this temp till we reach to the to the position. So now before uh traverse before start this traversing we need to set this pointer to first node. So you can write after this line after declaring this temp here I you can write temp is equal to head. Now temp is containing 200 means temp is now pointing to this node head and temp is pointing to the first node. Now I will start reversing I less than is equal to post. Then we will move this temp. So in temp now we will store temp of next. It means temp next means 100. Fine. So in temp we are going to store temp next. Now it is having 100. So now temp is pointing to this node. Right? And we will do what? I ++. Now see one iteration we have done one I was one and position is three. One less than three. So we have done temp is equal to temp next. Here now temp. Now I ++. Now I is equal to two. Now 2 is less than three. Yes. Now again we will do temp is equal to temp next. Now temp next is equal to temp is pointing to this node. Temp next is 500. So now here we have 500. So now this temp is pointing to this node. Fine. And I ++ now I becomes three. Is three less than three? No. So now we are going to we are not going to move this stamp. Now we have reached till this position because position is three and we have reached till this 1 2 and three. Now I can update these links and after that I can free this memory. Fine. So now after this while loop what you will write see now how you can access this part here I want to store address of this node after deleting this that is 150 here I want to store 150 right how you can access this part 500 the address of this node is 100 so how we can reach till this node here we have 100 address of this node and we have a pointer to this node that is temp so how we can access this this part temp of previous. So here I can write after this while loop I can write temp temp of previous that is 100 means we have we have reached till this node but in this particular node also I want to reach till this part. So here I can write this part is next. Next next is equal to now here I want to store 150 that is this one from where I can get this 150. See here we have 150 and we can access this node because we have a pointer. So here I can write temp of next because temp next means 150. It means this is now containing 150. And now this is not pointing to this node. Now this is pointing to here to this node one link we have set one link and now we have we are going to set this link. Now see how we can reach till here till this part. See this node till this node how we can reach the address of this node is 150 but directly we don't have any pointer pointing to this node but don't worry we have a pointer to its previous node and from previous node here from where I I from here I can get this 150 fine and pointer to the to this node is temp so here I can write temp next temp next means we have reached till this node but in this node also I I want to reach till this part. So the name of this part is again we will write this arrow and the name of this part is previous is equal to now here I want to store what 100. Now from where I can get this 100 C here we have 100 and I can access this node because I have a pointer pointing to this node. Now temp of previous right temp of previous 100 would be stored here. Now here I will store 100. So this link is no more. And now this is pointing to this node. Right? Now we have set this link also and this link also. Now we can free this space. And how you can free this? Free temp because temp is pointing to this node means from this address 500 from this address we are going to free this memory. Fine. So now that's it. That is how we can delete from any specific position. I hope you can modify this. If I want to ask how to delete a data from a given sorry how to delete a data after a given position or how to delete a data from uh before a given position. Fine. So now the time complexity for this case is what? Now we have traversed till here means one and two nodes. If position is suppose 10 so you need to traverse 10 node. If position is 50, so you need to traverse 50 nodes. It means obviously it is proportional to n the number of uh nodes in the list and if you want to delete from middle then you have to traverse what n by two nodes. So that is why the time complexity in average case is what uh order of n fine so this is all about the deletion from a double link list. Fine. Uh next video we'll see the circular link list and some operations on circular link list. Fine. So I'll see you in the next video. Till then bye-bye.