2.13 Reverse a Doubly Linked List | Data Structures & Algorithm Tutorials

And we have discussed how to reverse a singly link list. Do uh check out those videos. I'll provide you the link in the description box. You can check out there the complete series on link list in data structure. Fine. You can check out in the description box. So now this is a doubly link list. It is having four nodes and I want to reverse this double link list. See I don't want to swap the nodes like this. this node and with this nodes seven would go here and six would go there like this I I'm not going to swap the nodes what I'm going to do is I'll just reverse these links fine that uh processor we have already discussed in singly link list how to reverse a singly link list fine so now how we will reverse these links see we are having a head pointer and a tail pointer without tail pointer also we can reverse this link this double link list fine Now see what I want to do is see the this next pointer of this node is containing address of the next node right and the previous pointer is containing address of the previous node there is no previous node that is why it is null. So after reversing what I want to do. So now in the next node in the next node I will store the address of the previous node not the next node. After reversing it means see in the next pointer of this node address of the next node is there. But after reversing I want the next pointer of this node contains address of the previous node. Means it should contain zero and see this previous pointer of this node is containing address of the previous node. No previous node that is why it is containing null. But after reversing what I want this previous pointer will contain address of the next node that is 150. So here there should be 150. This is what reversing means. Swap these values. Fine. And finally swap this. Tail would point here and head would point here. Fine. Same here. See this node how we will do the previous pointer of this node is containing address of the previous node. But after reversing I want what? This previous pointer should contain address of the next node. That is I want here what? 500. The next pointer should contain after reversing the address of the this this previous node that is 200. So here 200 right this is what the reversing means. This is what I will I will implement. Fine. So simply what what we are doing we are swapping these values 200 here 500 here 0 here 150 here this 150 here and this 400 here this is what we will do here we will write what zero so this zero would be here and this 500 would be here after reversing fine so now how we will do this thing C here obviously we are not going to move this head fine So we will take what another pointer. Suppose I'm taking a temp pointer and temp is pointing to this node. Suppose temp is pointing to this node and temp is containing both this 200. Fine. So now how can we do swapping? Suppose here I write how we can access this part temp of next is equal to here I want to store what I want to swap these values. So this value zero I want to store here. So how how we can write temp of previous means the temp of previous value zero now would be stored here rather than 150. Fine. Now it means this link has been broken. There is no length like this. Fine. Now here I want to store what? 150. This this address of this node. But now from where I can get this 150 because see we have already broken this link. So here we have now zero. So we have don't have 150. So from where I can get this 150. So that is a problem. Now if you if you will say ma'am we are not going to implement this 150. We are not going to update this 150 first. We will update this node first. Right? So rather than writing this line what I can do you suppose if you write temp of previous now temp of previous will contain the value this this value 150. So here I can write temp of next it means here I don't have zero now I have 150 right now here I want to store what this value zero but here we have already updated that is 150 so from where I can get this this value fine it's not like that we simply write temp of next is equal to zero and that is fine no because here I cannot write suppose at some point of time temp would be here. So I cannot write here zero. We are our main motor is what? We are going to swap these values. So now we cannot do this thing. Now what we can do? We we have to store this this point this address also. We need some another pointer. So now we are taking one more pointer. Suppose I'm taking one more pointer here that is I'm taking the name next node. Right? And I'm not taking temp. I'm taking what? current you can take any name temp 1 as you wish fine and when I assign this current is equal to head means now current this pointer is containing this address at the same time after that we I I'll assign what next node in next node I will assign 150 from where I can get 150 so I'll write next node is equal to here from here I can get 150 that is current of next now next node is pointing to here. Now you can update this thing. Right? Now if suppose you write current of next is equal to current of previous means you have updated this thing. Here we have zero. Now here I want to store this value that is address of this thing 150. Now from where I can get 150 because this thing we have already updated. From here I can get 150 because I have set a pointer to this node already before updating before breaking this link. Right? So now I can write current previous is equal to next node and after that we will move this current and next node would be this node now. So you have to maintain what two pointers. Fine. So now I'll write the code see. So now this thing I hope everybody knows we have discussed many times. What is this? We have defined our own data type. The data type of this node that is struck node. Three parts are there. One is data part and two are next and previous pointers. Right? And we have already we have declared here two pointers that is head and tail. So here I can write ar head estric tail or if you don't write here simply you can do semicolon here and after that here you can write this data type struck node estric head and ar tail fine after that you can call that function create dl that we have already discussed and you create this uh dlink list and after that we will call a function that is reverse of this dl. So now I I I'll define this function that is reverse dly link list right. So now in this case now for reversing this list for reversing these links we need two extra pointers right. So here we will declare these two pointers and how to declare I think the syntax you already know because we have already discussed the syntax many times in the previous videos right. So now I have these two nodes sorry these two pointers current and next fine now see if you can write down a condition if head is equal to is equal to null it means there is no node in the list list is empty so we cannot reverse this list else in else part what you will write I'm writing that thing only I'm not going to write that if condition I guess you can write that condition that is very easy fine and we have discussed we have already uh written that condition many times in the program fine The first step is we are going to point this current here. So here what I want to store that is 200. So now from where I can get this 200 head is containing 200. So here after this what I can write this current is equal to head right now this is pointing to this node only. And before updating before reversing before swapping these values I'll maintain I'll set a pointer to this node also so that if we lose this if you break this link we can easily get this address fine for updating these values for reverse for swapping these values. So here here I will write what this next node is equal to here I want to store 150 from where I can get 150 here the pointer to this long uh this node is current although we have head but we are not moving this head we are we will move this current so that is why I'm using this current and next right so 150 would be stored here now what I can do now we can swap these these values. So now what you will write? See how you can access this part. Current of next. So here I'll write current of next is equal to here I want to store whatever the value here in this pointer. How we can access this pointer current previous. So here I'll write current previous. So now we have updated this link and we have here zero because the in current previous we have value zero and that would be stored here in the current next. So now there is no this link is no more now right and now here I want to store what 150 here we have we had 150 now so this this this after reversing this previous link should contain address of the next not the previous that is what reversing. So from where I can get 150? In the next node we have 150. That is why we need this next node. So here I can write what? Current of previous is equal to next node. Right? So now here I have 150. Right? It means now this is pointing to here. Right? And this is pointing to here null. So we have reversed these links. Right? Now come to this node. Fine. Now we will move this current. Right? So now current in current uh pointer I want to store 150. From where I can get 150. In next node I have 150. So here I can write current is equal to next node. Right? Now current is also having 150 this pointer. Now this pointer is also pointing to this node. Now the current node is this one. Now I want to swap these values. See this previous pointer this previous pointer is pointing to this node. But I want this pointer should after reversing this pointer should point to the next node. That is why I I want to reverse this link. This link I want to break this link and I want that here. I I I'll store 500 right this value and here this this pointer is containing address of the next node but I want this uh pointer should contain address of the previous node that is 200. So here I want to swap these lengths now. So we will repeat the same step right so these steps I'll write in a while loop till we reach here right. So now here I will write before the these line after this line while and you will write what this current pointer not equal to null. Till then we are going to repeat these four steps. Please don't write this step in while loop because again we will enter into Y loop then again current would be head. So again current would point to this node. But I want I don't want this thing because we have done with this node. Now we are at this node. We will deal with this node then with this node then with this node till we reach to the this null. So here I'll write current node equal to null. Fine. Now see we have done one iteration. Now in current we have next node that is 150. Now 150 is not equal to null. Fine. Again we will enter into this loop. Now next node is equal to current of next. Now in current of next we have current is pointing to this node. current next we have 500. So that would be stored in next node. So now this next node is pointing to this node. Now we can update this this link and this link. Current next current of next is equal to current of previous that is here I will store 200. So now there is this link is no more and now 200 means here. So now this is pointing to this node right? So now this this will point to this node the previous one we have reversed this link right now this one here current of previous means current previous that is here is equal to next node next node we have 500 so here I will store 500 so this link is no more now this is pointing to this node right now we are done with this node also we have swapped these values now we'll do what current is equal to next node now we will move this current in next node we have 500 so now here we will have 500 so now this is pointing to this node so I'll write here again while loop current not equal to null yes current not equal to null again we will enter into this loop now next node is equal to current next so in next node we will store what current of next that is 400 so here I'm writing this one now next node is containing now 400 right so now next node is pointing to this node. Now we are going to swap these values. Same current next is equal to current previous. So here 150 this link is no more now. And this this is now pointing to this node. Right? And this one current of previous current of previous current is pointing to this node. Current previous here we will store next node. Next node we have in next node pointer we have 400. So now this is this this this is now pointing to this node. Right? Now we are done with this. We will move now current is equal to next node. Now in current we have 400. So now current is pointing to this node only. Right? And next node is equal to current next. In current next we have zero. So in next node we have zero. It means now next node is not pointing to any node. Now see we will swap these values. Current next is equal to current previous. Current next means here we'll store this current previous value. Right? So now this is now what pointing to this node 500 this address and current previous is equal to next node. Current previous this value is equal to next node. In next node we have zero. So here we will store zero. So now this is pointing to zero. Right? Now current is equal to next node. Now current in current we have zero because current is equal to next node. Next node we have zero. So now current is also not pointing to this node. Now again 0 not equal to zero but this condition is not true. Right? So we will not enter into this loop and we are done. We have reversed these links. But now still we have something left. We have to swap these pointers also. Head would be here and tail would be here. After that reverse operation would be completed. Now how you are going to swap these things? See how you can swap two variables. I guess you know easily after taking third variable you can swap these values right. So now obviously we have two extra pointers current and next node. So we can use these pointers. So first of all what you will do? You can do what in current we will store head value. So after this while loop after this closing you will write what current is equal to head. It means in current we have now this 200. So it means current is pointing to this node. Right? Now I can update this value. Now I can write head is equal to 10. It means head is containing now 400. So now head is pointing to this node. Address is this one. So now here this is now head. Right? And in tail we should store this 200. Right? And from where I can get 200. In current we have 200. So here I can write current. So now this becomes tail pointer. So now this is pointing to this node. Right? Now this is done. And if you want to check that this is done or not. So before these line before reversing this head and tail before these lines you can print what the data head of data. So it should print six and the tail arrow data it should print seven right and after these line after reversing head and tail it means head is equal to here now and tail is here now. So after these line if you print print percentage D and if you write head arrow data then it should print seven after reversing and print f percentage d tail arrow data then it should print six before reversing head data is six tail data is seven after reversing these lines head data is seven and tail data is six. So this was the iterative approach to reverse the doubly link list using recursion also we can reverse the list fine and after reversing you can draw it something like this. See it if you'll print this before reversing then it will print 6 5 1 and 7 after reversing if you will call the display function that we have already discussed many times how to traverse the double link list. It is same as single link list right? Then what it should print? 7 1 5 and 6 in reverse order. 7 1 5 and 6. So this is how we can draw this double link list after reversing. Right? So in next video we will implement a circular link list. We'll write a C program. Fine. How to uh create a circular link list and how to display the content of a circular link list. Right? So I'll see you in the next video. Till then bye-bye. Thank you.