2.4 Linked List Implementation in C/C++ | Creation and Display | DSA Tutorials

video is for this topic is you should know the basics of link list. What is link list? How to represent a link list or you should know the what is singly link list. Basically when we say link list then we are talking about singly link list. Right? So we are going to implement singly link list here. Fine. Plus uh you should know what is dynamic memory allocation and how to use the melo function in C language. Right? As well as you should have the knowledge of pointers plus structure. what is structure data type in C language how to access the structure members right using that uh structure variable also plus pointer also fine so now first of all uh we will see the logical view of a link list I'm going to create a link list here I'm just going to draw a link list here having three nodes only so this is you can see a logical view of a link list having three nodes this complete is known as a node what is a link list how to represent this I have already discussed I'll provide you the link of that video in the side button you can check out there in the last node in the address part see two parts of a node are there this one is data part this node this part of the node is going to store actual data and this part is going to store address of next node right that is why here I'm going to store 200 here I'm going to store 300 100 200 300 are random addresses the addresses are in hexadimal form this is just for your understanding purpose so see in The last node address part is going to contain a zero because it is not going to point any node further. Right? So it it it means it is having null. Fine. This is just a logical representation of link list. Now how we are going to map this logical view in programming? How to write a C program? Right? Initially we don't have any node. Fine. And this is what a headpointer. Headp pointer is going to store address of first node. Always we are going to have in program when you are writing a program in that case you have to maintain what this head pointer. Now see first of all we don't have any node in the link list right and we are going to create a link list having three nodes. We are going to create this one and after that we are going to display the content of the nodes that is five 4 and 9 right? We are going to see that in coding. So now first of all we have to create a node. Fine. Now how to create a node using a userdefined data type that is structure that we have already discussed. Now how to write down that thing? See we are going to write strct keyword then this tag that is node. This complete is what now a data type. You are going to define your own data type. Fine. Data type of this node. Now this node is going to contain two parts. One is the integer part and this one is what is going to contain address and for address we are going to take what pointer variable always. So first part would be int. Suppose we are going to take data or a or b or number as you can uh as you wish fine. Now next is for pointer this pointer now the data type should be this pointer is going to store address of next node. Fine. And the type of this is what struck node. So that is why I'm going to write here strct node estric and suppose the pointer name is next you can say link or as you wish fine so now this is what you have just defined your data type it's not that you have you have created this node no not now the memory has not been allocated this is just what you have defined your own data type right that is a strct node fine now What you will do? You have to maintain this head node also because this is what the main thing this is going to have the address of first node then you can traverse the list. So this is the main thing. So now you have to this is what a head pointer because it is going to store address of this node. Fine. So how to declare this pointer? C we will write what strct node estric and suppose the pointer name I'm going to take head why I'm writing this strct node here because see here you will write what always you will write if you write int star p it means this pointer is going to store address of integer variable right this is pointer to int so this is what this this pointer head pointer is going to store address of a node and the data type of this node is what? Struct node. So here we always write down the data type of that variable or that thing whose address this pointer is going to store. Fine. So in C language we are going to write strct node. If you don't write uh don't use type def. Fine. In uh C++ you can simply write this node that is fine. But here I'm discussing C language. Fine. Now we have created this head node. Initially suppose we don't have any node in the list. So initially what head pointer will store head is going to contain what? Zero or you can say null. Now we are going to create a node. Fine. Now you will write something such that memory is to be allocated for this node. So now here we are going to use what? Dynamic memory allocation that is malo function. In C language we are going to use malo function. In C++ you can use new keyword. Fine. Now how you can use melo function C. The syntax is what? You simply write me Melo and in bracket you will write what the size how much memory you want. Right? So how much memory we want here? The size of this according to the size of this node. Fine. So here you will write size of and in bracket you will write what? See data type of this node is what? Strruct node. So here you will write data type that is strct node. Fine. So how much memory is to be allocated? Size of strruct node. Size of str node. The data type is struck node. In this truck node we are having one variable data that is of integer type that is four bytes and one is pointer in 32-bit compiler four bytes is to be allocated in 64 8 bytes. So 6 4 + 4 that is 8 bytes complete block of eight bytes would be allocated dynamically. Now see this melo is what what it is going to return. Melo is a method or a function which is going to return a pointer to the starting address of that memory block because memory block of eight bytes has been allocated. Fine. So it is going to return a pointer to the starting address of that memory block. Fine. So Melo is going to return what pointer or you can say it is going to return a void pointer. So now what this Melo is going to return? See it is going to create a node in the memory a block of how many how many bytes? Eight bytes right here four for this and four for this. And suppose address of this is 100. I'm going to take see this this complete block is having how many bytes? Eight bytes. And the address of first bite is what? 100. So that is why I'm taking what address is 100. So it is going to return what 100. Address starting address of this block. Now we are going to store this 100. This is a address. So we need what? A pointer variable to store this. Fine. So we have to create one another pointer variable. That is here we are going to create a string new node. This is what another pointer variable. One is head and one is what? We are going to take new node. When whenever we are going to create a new node, we are going to take this one. The address of that node we are going to store in this pointer variable. Fine because Melo is always going to return what? Pointer to the starting address. And it is going to return what? Void pointer. See this new node. You can say here we are we are going to take. This is what new node. This is just a pointer. Now whatever the address the melo function is going to return we are going to store that address into this new node pointer that is pointer to node. But it is going to return what? Void pointer. So you have to type cast this one. Fine. So for type casting here you will write what? Str node array because we are dealing with a pointer to node. Fine. And the address we are going to store in new node. Address the type is this. This is what a pointer to node. So the type is what? Str node. A string. Fine. So now this is how we are going to dynamically allocate the memory. Now this block has been allocated of eight bytes and a new node. Now we have 100. So it is going to point here. So now we have created a node but we don't have any data here. So you can ask from the user for the data and for how you will write using scan if you're going to take the input from the user. So the data type is int. So we are going to use percentage d. And now see you cannot directly write here hash this address of an data. We cannot directly access the members of this structure. Fine. You we if we are accessing the members of the structure using what using this uh pointer then what is the that syntax address of see using this pointer variable we are going to access this node fine because we have just the address of this node. So how you will write the pointer name new node then you will write what this arrow symbol and now you will write that name of that variable the name of that structure member that is data this is how you can access the members of a structure using pointer fine using dot operator you can also use but here I'm using this arrow method because this is what easy to Now see suppose user has entered what this five. So here you will write what five and in this here now now we have only one node. So here you can insert what null or zero. So here you can insert zero. So here you can write what this new node arrow operator and for this part this is what the pointer pointer name is next. So here you can write next is equal to zero. So this is how we are going to access the structure member. See this this address part also we can access using this pointer. So we are going to use the name of that pointer then arrow operator and then the name of this part is what we have taken what next for this this part. So next is equal to zero. Now see now we have created this node. We have inserted the data. Now we are going to put this node in the link list. Fine. Initially see what we have done. Head head is equal to zero. See initially you can say here we have head and it is going to contain zero. Now next thing is you have to point this to this. Fine. So now you have to store this address into this head. Fine. Now how we are going to store this address is there what in this pointer that is in new node. So simply you can write head is equal to new node. So here now 100 is there and this is also going to point here. Now new node is also here and head is also here. So now the list is having only one node that is this one and head is going to contain address of this. So how we can write this? Head is equal to new node. So simply here you can write head is equal to new node. Fine. This 100 would be stored here and this is going to point here. Now fine. Now suppose you are going to insert one and you are going to create another node and you are going to insert here. Fine. In that case head is not null. See in this case at starting case head is equal to null. That is why we have simply done this thing. If head is equal to not null then what you will do? So here you will write one condition before this. If head is equal to is equal to null then you can do this thing then that is fine. else if head is equal to not null then what you will do now suppose we have created one more node using this uh code also fine we are going to we are going to uh write down that thing also how this program is going to run again and again how this code is going to run again and again see suppose again this line is going to execute new node is equal to this thing then in that case again one node is going to create it fine and suppose address is now 200 so now 200 is Now going to assign in this new node. So now in this new node we have what? 200. So this is now not going to point here. Now now suppose this is our new node and this is now going to point here because we have created one more node. Now now we are going to enter the data. Now suppose four we have entered. Four is going to store here and in the next part here we are going to store what? Zero. Right? So now we have created one more node and we are going to insert we are going to insert this node in the list also because here we have only one node in the list head and this one. So here we are going to store this new node. So you have to update the pointers. Now in this case head is equal to not null. Head is going having 100 the address of the first node. So this we cannot do now. Fine. If you don't write this condition and you simply write head is equal to new node then in this case also now head is going to contain head is equal to new node. So head is going to contain now 200. Fine. So this is this link is going to be destroyed and now head is going to point here. But that thing we don't want fine because we are going to insert this now here. So you cannot destroy this link. So simply you cannot write this thing. That is why we are going to write this condition. If head is equal to null then you can write this thing then it is right. If head is equal to not null then what you will do now? See. So now to insert this newly created node here in the list. What you will have to update? We are going to store address of this this newly created node here that is 200 here. It means now this is now going to point what? Here. Fine. So in the list we have this one and this one two node. Fine. So simply how you can access this part this structure because this node is having data type structure. So you cannot simply access this one. How you can access using arrow operator. Fine using pointer. The pointer of this node is what? Head pointer. So you can write here head. This arrow operator in C. When you are writing a program then you can simply write hyphen and that angular bracket. Fine. And then name of this pointer is what? Next. Next is equal to what? Here you are going to store 200. That is whatever is in the new node is equal to new node. So now you are thinking that this is now done. Fine. Now list is having these two nodes. Fine. Now the problem comes when you are going to create one third node. Now suppose the program has been executed again and one another node has been created. This one when this line is to be executed one another node has to be created. Suppose address is 300 and in this we have suppose 9 and here we have zero. And now the new node now the new node is going to contain 300. So now the new node is going to contain 300. So this is now going to point here. Now right we have inserted the data and this also we have initialized zero. Now if head is equal to zero but head is not zero then we are going to here into else part. Now how we are going to insert this newly created node here after this. Now in else node whatever you have written see head of next is equal to new node. Now head of next head of next is what this one because this head pointer is having 100. So we can access this. This is pointer to this node. So head next. Head next means this one. So now here we are going to store new node. The new node is going to contain 300. So here we can insert. Now according to this we are going to insert 300. So that is why this link has been destroyed. And now this is going to point here. But this is not actually done because this is first second then and after that we are going to insert this third node. But according to this coding we have lost the link to this node. Now this node is not in the list. So now this you cannot write. So the solution of this problem is what? You have to take one extra another pointer. Here we are going to take one pointer that is temp. One more pointer. Now see what is the role of this temp. See we cannot move this head pointer. We cannot change the this value of this head pointer because if you're going to change this value then you will you will lose the link or reference to this first node that we cannot afford. So we cannot change the value of this head node. This is going to be permanent. Fine. Now this temp this pointer this this value you can change. Suppose at first temp is going to point here. Next it is going to point here. Next is it is going to point here. So you cannot you you change the value of this temp uh pointer when you are going to traverse the list then we are then also it we are going to traverse using this temp only because we cannot change this head value. See this new node pointer is what it is just going to contain the address or the pointer to the newly created node. Fine. And head node is going to contain address of sorry head pointer is going to contain address of first node. Fine. So for traversing the list obviously we need one extra pointer. We cannot change this head node. We cannot use this new node pointer because this is only going to have address of newly created node. That is we are going to create this. We are going to take the another pointer that is temp. Fine. Now you have to modify your cording a little bit. See here you cannot write this line. Here what you will write temp of next is equal to new node. Right? And here it's starting if head is equal to zero head is equal to new node as well as we are going to initialize this temp. Temp is also going to point here. So head is equal to temp is equal to new node. Right? So now head is also going to point here plus one extra temp is also there. Extra pointer is also there. Another pointer temp. Temp is also going to continue node that is 100. Now temp is also pointing to first node. Both head and temp. We cannot move this head. We can we can move this temp now. Right now here we can write temp of next because this node is having two pointer. This one this one. So you can access this node using this temp pointer. So temp of next is equal to new node that is 200. Fine. when we were creating when we were inserting this second node. Fine. Plus plus what you will write here temp is equal to new node. Now we are going to move this temp. Temp is equal to new node at this time. At this time temp was 200 right when we were creating this second node that is here. So now temp is going to contain 200 right. So now temp is going to point here. Fine. And new node is also having 200. Now when you are going to create this third node, suppose you have created this third node. Now new node is going to contain 300. When the third node is going to create because new node is equal to this one. So now new node is going to point here. This is now our newly created node. Right? So how you can insert this node here after this node? See now you can see this line is correct. If head is equal to null this condition is not true. Right? So in else part in else part you'll write temp of next is equal to new node. Now temp is having 200. So using this temp you can access the both the parts of this node. Right? So temp of next means this one. So here you will write new node. Value of new node is 300. So here you will insert 300. So now it is going to point here to the newly created node. Fine. So this is fine. Now first first node, second node and third node. Right? That is why we are taking this third pointer variable. I hope now you have the idea why we are taking these three pointers. Now we are going to move this temp. Fine. Now temp is going to create. Now temp is going to have this new node that is 300 value is now 300. Now temp is not going to point here. Now temp is going to point where to this one to the third node in the list. Fine. And if we create another node obviously simply now temp next. Temp next means here here you can insert the address of newly created node. Fine. So this is now the proper logic. This is how you will write this. So now we have created these three nodes. So I'm going to rub this thing now. So now this is our list. Temp is pointing here. New node is also pointing here and head is pointing here. Now see uh now you want to implement a program something like this. You want to ask from the user do you want to continue? If user press one then you are going to create another node. Fine. Again this code is going to run. If user press zero it means you are going you are not going to create another node. Now you are going to print these values. Fine. So for that what you will write after this what you will write? You will ask from the user print f do you want to continue? For taking input you are using scanf address sorry percentage d address of now suppose we are we are going to take one variable choice and here we are going to store the choice of the user either zero or one. Zero means we are not going to continue. One means he wants to continue. He wants to create another node. Now you have to declare this choice variable also. So here you can declare int choice right now if user press one it means again this code is going to run fine. So now we we have to write this code into while loop. Fine. So where you will write this while loop here before this new node because if user press one then one another node is to be created. It means that another node is to be created using this line. So before this line you will write while and in bracket you will write choice. So after this line int choice and before this line in the program you will write while choice. I don't have enough space that is why I'm writing here something like this. Fine while choice and you will this bracket and after the after this bracket you will write you will write this line new code is equal to this one. So now this while loop you are going to close here. Now using this code you can create as many node as you want. Now next thing is you want to print you want to traverse the list. How you are going to traverse from here you first of all or you can say you are going to print the values five then this four then this nine. We cannot move this head pointer. So that is why again now at last temp was here. So again we are going to initialize this temp from here right. So in temp first of all we are going to store temp is equal to head. Now in temp we are having 100. So now temp is pointing here. So now you are going to print 5 4 and 9. So here you will write a while loop while temp not equal to null. Fine. Till then you are going to run this loop and you will print this value. This value that is data. So now we cannot directly print this five. You cannot directly access this data. You can access this this member of the structure using this pointer. Fine. So now you are going to print this five. So simply you will write print f after that you will write temp this temp arrow operator and name is what data name of this variable is what data now this is going to point five sorry this is now going to print this five right now we are going to print this four but we cannot directly print this four fine so we are going to move temp now here right So now temp is equal to temp next. See temp of next the value is going to store in temp. Temp next. Temp is what? 100. So temp is going to point here. Temp next means 200. So now 200 is going to store in temp. So here you will store now 200. Now this is going to point here. Right? Again condition while temp is equal to not null. Temp is now 200. So it is not null. So now print temp data means temp data that is four. It is going to print now four. Again temp of next. Temp of next is 300. So now 300 is going to store in temp that is here you will store 300. So now temp is going to point here. So now temp not null. Yes temp is not null. Condition is true. Now again print temp of data that is nine would be printed. First five then four then nine would be printed. Now temp of next temp of next means zero. Zero would be assigned here. Temp. Now temp is going to contain zero. So now while temp not equal to null. Now this condition is not true. Now we are not going to print here because now temp is what? Null. Temp is zero. So now simply you are going to exit. So here you can write get ch and this comp this this code you are going to write in void main main function. Fine. Or you can simply create a function of create node or display. Fine. And you can uh write down this coding into those functions. And you can call those functions into this main function. Or you can directly write down this coding in the main function. And if you want to print how many nodes are there in the list, then you can take a simple variable that is count. You can declare here int choice and int count. And uh in this while loop you can write down one more step that is count ++ you can initialize the count at starting int count is equal to zero. Fine here only and here count ++ and after this while loop you can print this count value. Print f percentage d and count. So this three would be printed because here in this case we have three nodes. So this is how you can create node and traverse the list. I hope you got the concept. In next video we'll discuss how to insert newly created node in the list at beginning also at any position also and at end of the list. Fine. So I'll see you in the next video. Till then bye-bye. Take it.