2.19 Implementation of Doubly Circular Linked List| Creation and Display | Data Structures

ular link list right what is doubly circular link list for that this thing we have already discussed the introduction of this uh list when we were discussing the types of uh link list so you can check out that video here in this I button fine see this is what a doubly circular linked list in this video we will see how to implement this list or you can say how to create this list and how to traverse this list or you can say how to display the content of a doubly circular length list see as the name suggest it is having the property of both doubly and circular link list. So as you can see here, see this is what a doubly linked list. Each node is having three parts. One is data part and one is pointer. This is pointing to the next node. This pointer is containing address of the previous node. Right? Now how to add the properties of circular link list? In circular link list what we have discussed the last node would contain address of the first node. As you can see here the next pointer of this last node is containing address of the first node that is 500. Fine. So there is a link like this this to this node. Plus one extra property of this list is what? Why we are this is known as doubly circular link list. Here the previous pointer of the first node would also contain address of the last node. Right? the previous pointer of first node. See here the 600 is there and 600 is address of the last node and here the next pointer of the last node would contain address of the previous node. Right? So in this list we don't have any null pointer. Right? So this is what a doubly circular linked list. Now in in this case we have maintained both head pointer and tail pointer. Head is containing address of the first node. Tail is containing address of the last node. If you maintain only head node then also you can create this list. See this this link is birectional right? Rather than creating two links here I made this birectional link. So this to this also and this to this also fine now we will see how to create this list right how to represent this node of the list that thing I guess we already discussed when we were discussing doubly circular length list right so initially we assumed that list is empty we don't have anything in the list right it means you can say head is equal to null at starting right see how we will create this list so this is how we are going to define our own data type that is how to represent this node strct node three parts are there data parts next pointer and previous pointer right how much memory would be allocated four bytes for this four for this and four bytes for this pointer would be allocated four bytes because in 32-bit compiler if 64-bit compiler is is there then eight bytes would be allocated so total 12 bytes block is there right we are maintaining two pointers head and tail right this is what we will uh define a data type globally outside of all the functions so Now we are going to define this function that is create dynamic this doubly circular link list right. So obviously first of all we think that we we assume that the list is empty. So for inserting the nodes we have to create this node right it means you have to allocate the memory to this node. And how we are going to allocate the memory we use what dynamic memory allocation in linked list. Right? Why we use dynamic memory allocation? That thing we have discussed when we were discussing introduction to link list. You can check out that video here. And how we allocate the memory dynamically using malo function. So I I guess everybody knows how to write down that syntax. We have discussed many times. Right? So at starting I write here head is equal to null. It means there is no list. We don't have any list. Right? Now I'm going to create a node and the pointer of this node. This this sorry the address of this node I'm going to store in another pointer that is a new node pointer. I have created a new node pointer the this this new node is pointer to node that is why I'm writing here data type is struck node right so now what you will do how you will write this so this is the situation now we have created a node we have allocated the memory to this node using maloc function right maloc size of how much size for this struck node for this node so that is why here in bracket we'll write node 12 bytes will be allocated address of the first bite is 500 so malo would return what pointed to the starting address of this node but maloc will return void pointer that is why you have to type cast this thing because this new node in this new node I'm I'm going to store this address and this node is what pointer to node right so here you will write strap node array we are going to type cast this thing and whatever this will return in new node I'm going to store this right now I'm I'm going to ask from the user for the data right which data I want to store here so this is how we are going to store the data right print f enter data scan fet isd where I want to store data here. So how you can access this part of this node? We cannot directly access structure members. You need a pointer to this node. Pointer to this node is new node. Address of new node and name of this is data part. So here I'm writing arrow data part. So suppose user has entered seven. Right? Here you can store zero and zero means null and null. But no need to store here because we are going to update both the pointers. Right? So you can leave it like this. Now at starting we check what if head is equal to empty. It means sorry if head is equal to null it means there is no node in no node in the list right so then how you are going to insert this node in the list see now both head and tail would point to this node because this is the first node this would be the last node only right so here what I will write head is equal to tail is equal to new node plus now see both this tail is also pointing to this node and head is also pointing to this node. But now you have to insert here also something and here also something. Now what we have discussed the next pointer of the last node is containing address of the first node. Right? So this pointer would contain this is only the last and first node. So here we have to insert 500 address of itself. Right? And here also the previous pointer of first node is containing address of the last node. Right? And this is first and last node. So here also you will store 500. Now this would be the doubly circular link list. So now how you can access this part? See tail new node and head all the three pointers are pointing to this node. So you can access it using any pointer. Suppose I'm writing here head of next equal to head that is also fine. If you write tail of next equal to tail that is also fine. If you write new node next equal to new node that is also fine. Right? And now head third thing head of previous this thing is equal to head. Right? So now this is done. If there is no node in the list else if we are having some node in the list. Suppose one node is there and now I want to insert a second node. This node I have created a second node and user has entered suppose six here. Right? So now in that case this new node suppose address is 600. So in new node now this new node is having 600 address right? So new node is pointing to this node there we are going to run this code again right this one again we are going to create this thing and whatever this will return we are going to store in new node pointer right now I want to store this node in this list now in this case head is not null. So now how many pointers you need to update here you need to update I guess five things. See this this would contain address of the next node. The next pointer means 600. Second thing this would contain address of previous node that is 500. Third thing now this would contain this would be the last node. So this would contain address of the first node that is here also 500. You need to store plus you need to update this thing also because the previous pointer of the first node would contain address of the last node that is here you will store 600. Plus fifth thing is now tail would point to this node because this is to be this is now the last node. Right? So now how you will write down that thing. See in this case also you need to take care which line you need to write first. Right? See now here I need to store 600 address of the next node. Right? 600. So how you will access this part? Tail is pointing to this node. Tail of next. So here I can write tail of next. See we obviously here head is also pointing to this node. So you can ask can I can we write head of next? No we cannot write head of next because after inserting second node if you you will insert the third node in that case here you need to store address of this node right and how you can access this part because after that tail would be pointing to this node using tail of next. We cannot move this head will head will always point to the first node. So better to use tail node right rather than head. We cannot use head. Tail of next here 600 I want to store from where I can get 600 in new node I have 600 right. So now this is pointing to this node. This is not pointing to itself now. So now this node here we will store address of the previous node. Right? The previous pointer of this node will contain address of the previous node. Right? How you can access this part? New node preu. So here I will write new node preview because pointer to this node is new node. What I I will I want to store address of previous node that is 500. So in tail we have 500. So I will write here what tail. See here also we will not write head because head is also containing 500. But we will not write here head because head will also head will always contain address of the first node because but when we will insert third node in that case we need address of the previous node means this node. In that case tail would be pointing to this node. So we use here tail right. So here I have now 500. So now we have set two links. Now you need to update two links more. See this last node. This is the last node now. So this node would contain address of the the next point of this node would contain address of the first node to make it a circular list. Right? So now how you can access this part here? I will write new node next. Address of the first node we will always find in head pointer. So here I will write head. In head we have 500. So 500. So now this this is pointing to this node. Right. Plus you need to update this thing also. The previous pointer of the first node. How you can access the first node? There is always a pointer that is head. So here I can write head of pre address of the this this node last node. So here what you will write new node right because in new node we have 600. So here I can write what now it will contain 600. So now this is pointing to this node. So I'm making this a birectional link right this and this. Now another thing you need to update. Now tail would point to this node. This would be the last node. So in tail we will store 600 from where I can get the address new node is containing 600. So here so now this is having 600 and tail is pointing to this node. So this is as you can see we have inserted this node successfully. Now suppose if you want to check out these lines are working properly or not. Here you can create another node third node. Suppose user has entered data minus one and this is what the address is 700 and so in new node we have 700 now. So new node is pointing to this node right now I want to insert this node in the list. This node in the list right. So now if head is equal to null that is not true. So we are going to enter into else part. Now see tail of next in else we have written tail of next means tail of next tail is pointing to this node that is this one is equal to new node. In new node we have 700 that is now this is pointing to this node that is fine. New node previous new node previous here I will store tail in tail we have 600 so 600. So this is the address of previous node. So that is also fine. This is pointing to this node. Third thing new node next new node next. This data sorry this part is equal to head. In head I have 500 that is 500. This is now pointing to this node right this node. Fourth line head of previous means head is pointing to this node. Head of previous means you are accessing this part is equal to new node. In new node I have 700. So here 700. So this would point to this node. So I making so I'll make the link birectional. Right. F fifth tail is equal to new node. Tail is equal to new node. In new node I have 700. So here now tail is pointing to this node. So now after this you can write down that same while loop while uh sorry here you can write print f press one for continuation and press zero for exit. So here you can write scanner percentage d and uh the user choice you can take out in a variable you can say uh choice here you need to initialize the choice is equal to one. Right? If user press one the data the again node would be created right. So now for creation these lines after that these lines should be executed again and again. So we will write this code into a while loop while the variable is choice and after that you will start while loop and here you will end this while loop right. So before closing this while loop you will write what? Print f press one for continuation zero for exit scan a percentage d address of choice. Right? Now if you want to cross check that we have created this list or not then see here I'm saying the next pointer is containing address of the first node. So can we print using this pointer the data of first node right? So before closing this create function you can write what print f percentage d and here you can write see tail sorry the pointer to this node is now tail is pointing to the last node. So here I can write tail of next Right. I will access tail of next. So and data again pointer and data. So it should print what? Seven. Using this tail I'm I'm printing this first node. Right? As well as you can print using head using the first node. Can we print this data? So again you can write here head of previous. See this previous is containing address of the last node. So second thing what you can write here head of pre it means 700 means we have reached till this address and again arrow data it means minus one it should print minus1 and it should print seven. So this is how we have created a doubly circular link list. Now we will traverse this list means we are going to display the content 7 6 and minus one. How you will write down that code see. So this was the list we have created. Now I want to define a function that is display. how to display the content of this list. Right? So obviously for displaying or for traversing we need a pointer that we can move because head will also head will always point to the first node. Tail will always point to the last node. We cannot move these pointers. So here we need a third pointer you can say temp pointer and initially this temp would point to the first node means in temp we are going to store head. Right? So now this is what a temp pointer in temp we have head that is 500. So temp is pointing to this node to the first node. Right? Now you will check if the list is empty or not. So here what you can write if head is equal to zero. Head is equal to equal to zero means you can print list as empty. There is no data in the list. Otherwise in else part what you will write now we will print this head data and move the stem. Print this head data and we will move the stem till what? Till we reach to the last node. So what is the termination condition? When temp would point to this node it means temp becomes equal to tail. Right? Because tail is containing address of the last node and at some point of time temp will also contain address of this one that is 700. It means we have reached till the last node then we are going to stop right. So now in while loop what you will write while temp not equal to tail in that case we will move until we will move. So temp is bonding to this node. So first of all what you will print the data print f percentage d temp of data and after that we will move this temp right now temp will point to this node that is 600 we will store in temp. So in temp we will store temp is equal to temp of next temp of next. Now see the working of this while loop at starting temp is 500 temp is not equal to t is 700 condition is true. So we will enter into this loop print of temp data. Temp of data is seven temp is equal to temp next. Now see in temp next we have temp of next 600. So in temp we will store 600. So now this is pointing to this node. Right. Now again check temp not equal to tail. Temp 600. Tail is 700. Yes is true. We will enter into this loop again. Again print f temp of data that is six. Now temp is equal to temp next. In temp next we have 700. So here now we will store 700. So now temp is pointing to this node. Now check the condition temp not equal to tail. Temp is 700. Tail is also 700. Means we have reached to the last node. Right? But the condition is not true now. So we will not enter into this loop. Control will not go into this loop. Control will go out from this while loop here. But now the output is only seven and six. We need to print this data also. Right? So here after this while loop you will write one more line that is percentage d and how you can print minus one. See temp is pointing to this node. So temp of data here you can write one more line after that close is this else statement and after that this function display function. So this is how we are going to display the data. But if you're if you don't want to print the last this this data separately then what you can do rather than this while loop you can use do while loop right here you can use do because these statements would be executed first in dowh loop and after that condition would be checked right after that you can write this while condition that thing do while loop also we have discussed when you are that implementing the circular link list. So how to write down do loop that also you can check out in the side button for that video. Fine. See here in the termination condition if you don't write this thing then you can also write a second termination condition. See temp of next temp of next when temp of next becomes what this tail of next tail of next is always containing address of the first node. Right? So it means we have reached to the last node. So while camp of next not equal to tail of next till then we are going to move otherwise we will stop. Right? this condition you can also write. So this is the implementation of a doubly circular linked list. Fine. In next video we will see the insertion operation in doubly circular length list. Fine. Insertion at beginning, at end and at any specified position. So else in the next video. than YK.