2.4 Linked List implementation in C/C++ | creation and display | data structures

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 a singly linked list basically when we say linked list then we are talking about singly linked list right so we are going to implement singly linked list here fine plus you should know what is dynamic memory allocation and how to use the Mellow 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 structure variable also plus pointer also fine so now first of all we will see the logical view of a linked list I am going to create a linked list here I am just going to draw a linked list here having three nodes only so this is you can see a logical view of a linked list having three nodes this compute is known as a node what is a linked list how to represent this I have already discussed I will provide you the link of that video in the cyber and 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 address of next node right that is why here I am going to show two hundred here I am going to store three hundred hundred two hundred three hundred are random addresses those addresses are in hexadecimal 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 means it is having null fine this is just a logical representation of linked 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 head pointer head 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 linked list right and we are going to create a linked list having three nodes you are going to create this one and that we are going to display the content of the nodes that is 5 4 & 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 user-defined data type that is structure that we have already discussed now how to write on that thing see you are going to write struct keyword then this tag that is node this complete is what now our data type we 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 this 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 your number as you can as you wish fine now next s your 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 struct noddle that is why I am going to write here struct node estwick 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 struct 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 address of this node fine so how to declare this pointer see we will write what struct node astrick and suppose the pointer name I am going to take head why I am writing this struct node here because see here you will write what always we will write if you write int star P it may 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 off and 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 struct node if you don't write don't use type def fine in C++ you can simply write this node that is fine but here I am 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 word 0 or you can say null now we are going to create a node fine now you will write something such that memories to be allocated for this node so now here we are going to use what a dynamic memory allocation that is malloc function in C language they are going to use malloc function in C++ you can use new keyword fine now how you can use malloc function see the syntax is what you simply write mellow and in break it 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 break it you will write what C data type of this node is what struct node so here you will write data type that is struct node fine so how much memory is to be allocated sizeof struct node sizeof struct node the data type is struct node in this struct node we are having one variable data that is of integer type that is 4 bytes and one is pointer in 32-bit compiler 4 bytes is to be allocated in 64 8 bytes so 6 4 plus 4 that is 8 it's complete block of eight bytes would be allocated dynamically now see this malloc is what what it is going to return my locus 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 a memory block fine so malloc is going to return what pointer or you can say it is going to return a void pointer so now what this malloc is going to return C it is going to create a node in the memory a block of how many how many bytes eight bytes right here for for this and four for this and suppose address of this is hundred I am going to take see this this complete block is humming how many bytes eight bytes and the address so first byte is what hundred so that is why I am taking about addresses hundred so it is going to return what hundred address starting address of this blow now we are going to store this hundred this is an 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 strict new node this is what another pointer variable one is head and one is what we are going to take new node whenever 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 my loop 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 they dress the malloc function is going to return we're going to store that address into this new node pointer that is pointer to node but it is going to return what void pointer to show you how to typecast this one fine so for typecasting here you will write what struct node Asterix because we are dealing with a pointer to no fine and that dress we are going to store in new note address the type is this this is what a pointer to node so the type is what struct node s string fine so now this is how the we are going to dynamically allocate the memory now this block has been allocated of eight bytes and a new node now we have hundreds 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 are going to take the input from the user so the data type is int so we are going to use percentage D and now C you cannot directly write here hash in this address of and data we cannot directly access the members of this structure fine you if we are accessing the members of this structure using what using this pointer then what is the that centex brace off C using this pointer variable we are going to access this node fine because we have just to the address of this node so how you 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 node operated you can also use but here I am using this arrow method because this is what easy to use now suppose user has entered what this file so here you will write what fine and in this here now we have only one node so here you can insert one now on 0 so here you can insert a 0 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 structural member see this this address part also we can access using this pointer so you are going to use the name of that pointer then arrow prater 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 linked list fine initially see what we have done head is equal to zero see initially you can see here we have head and it is going to contain zero now next thing is you have to point this to this right 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 it new node so simply you can write head is equal to new node so here now hundred 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 as equal to new road so simply here you can write head is equal to new node fine the standard will be stored here and this is going to point here now fine now suppose you are going to insert one are you going to create another node and you are going to insert here but in that case head is not null see in this case at starting his head is equal to null that is why we have simply done this thing if head is equal to mod 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 n is equal to North null then what you will do now suppose we have created one more node using this code also fine we are going to if we are going to write down that thing also how this program is going to run again how the score 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 for we have enter for is going to store here and in the next part here we are going to store what 0 right so now we have created one more node and they 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 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 you 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 to move fine so simply how you can access this part this structure because this node is having datatype structure so you cannot simply except this one how you can access using arrow Prater fine using pointer the pointer of this node is what head pointer so you can write here head this arrow Prater in see when you are writing a program then you can simply write - and that angular bracket fine and then name of this pointer is water next next is equal to what here you are going to store 200 that is whatever is in there new node is equal to new node so now we 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 nine and here we have zero and now the new node now the new node is going to contain 300 so now then you know what 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 to 0 now if head is equal to 0 but head is not 0 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 C head off next is equal to new node now head off next head off 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 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 M one more pointer now see what is the role of this temp C we cannot move this head pointer we cannot change the ED this value of this head pointer because if you are 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 can change the value of this M 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 off sorry head pointer is going to contain address so first node fine so for tray were saying the list obviously we need one an 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 another pointer that is kept fine now you have to modify your according 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 0 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 note that is hundred now temp is also pointing to first note 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 template so temp of next is equal to new node that is 200 fine when we were creating when we're inserting this second node fine press 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 are creating this second node that is here so now MP is going to contain 200 right so now temp is going to point here fine and new node is also having two hundred now when you are going to create this third node suppose we 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 no this condition is not true right so in else path in else part you write temp of next is equal to new node now temp is having two hundred 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 three hundred so here you will insert three hundred so now it is going to point here to the newly created node fine so this is fine now first no 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 the stem 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 am going to run 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 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 1 then you are going to create another node fine again this code is going to run if user press 0 it means where you are not going to create another node now we 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 printf do you want to continue for taking input you are using scanf address sorry percentage D address off now suppose we are we are going to take one variable of choice and here we are going to store the choice of the user either 0 or 1 0 means we are not going to continue one means he wants to continue he wants to create another node now you have to be clear this choice variables so here you can declare int choice right now if user press 1 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 into choice and before this line in the program you will write while choice I don't have enough space that is why I am writing here something like this fine while choice and you will thus break it and after this after this bracket you will write that 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 note you can say you are going to print the values 5 then this 4 then this 9 we cannot move this head pointer so that is why again now at last impose here so again you are going to initialize this temp from here right so in temp first of all you are going to store temp is equal to head now in temp we are having hundreds so now temp is pointing here so now you are going to print 5 4 8 9 so here you write a while loop while M not equal to none fine till then you are going to run this loop and you will print this value this value that is a data so now we can not directly print this 5 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 5 so simply you will write printf after that you will write M this temp an operator and name is what data name of this variable is what data now this is going to 0.5 sorry this is now going to print this 5 right now we are going to print this for but we cannot directly print this for 5 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 M temp next M phase one hundred so temp is going to point here M next means 200 so now 200 is going to store in M 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 4 it is going to print now 4 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 in or not now yes temp is not null condition is true now again print temp of data that is 9 would be printed first 5 then 4 then 9 would be printed now temp of next temp of next means 0 0 would be a sign here temp now tempo is going to contain 0 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 tempis is 0 so now simply you are going to exit so here you can write get CH and this comes this this coder 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 write down this coding into those functions and you can call those functions into this main function but 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 in two choice and into count and in this while loop you can write down one more step that is count plus plus you can initialize the count at starting in town tis equal to 0 fine here only and here count plus plus and after this while loop you can to the scum value printer percentage DL count so the 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 in the next video till / take

Channel: Jenny's lectures CS/IT NET&JRF

Views: 545,306

Rating: 4.8793907 out of 5

Keywords: linked list, linkedlist in data structure, implementation of linkedlist in c, jennys lectures, jenny's lectures, CS/IT, NET&JRF, jayanti khatri lamba, ugc net computer science preparation, gate, GATE, it, cse youtube channels, engineering, c programming, what is array, linked list implementation, what is linked list, linked list operations in data structures, code, technical, ds notes, study material, ugc net syllabus, cs, it youtube channels, IT, data structures and algorithms

Id: 6wXZ_m3SbEs

Length: 29min 1sec (1741 seconds)

Published: Tue Aug 13 2019