How to insert a new node in a linked list in C++? (at the front, at the end, after a given node)

hi everyone and welcome to my channel in this video i want to talk about linked lists and i want to show you three different ways to add an element into a linked list which means to insert a node into a linked list so i want to show you how you can insert a node at the front of a linked list at the end of a linked list and then also how you can insert a node after a specific node so that is what i will be talking about in this video and then if you are not familiar with linked lists at all if you don't know how to implement your own linked list if you don't know what our main characteristic what characteristics what i mean advantages and disadvantages of linked lists i would recommend you to watch my first video related to this topic which i will link here and in the description as well so make sure to watch that video and in that video i showed you how you can implement your own linked list using c plus programming language which is this code here so if you don't understand some of this code here make sure to watch that video and then i will also paste this code in the comment and i will pin that comment so that you can use this code if you want so now i will just go very quickly over this code so that you are familiar with what it is doing but again if you need to understand what every single line of code is doing make sure to watch my first video related to linked lists so here i have created a class called node and that class represents one element of a linked list so one node and that node consists of two parts the first part is value of that node and then second part is a pointer to the next node so that is this class here and then here i have created three nodes actually i have created three pointers to three nodes so first second and third and this head this is actually just a name for the first node so it is head of a linked list which means that it is the first node of a linked list and then here and here and here i have assigned values to first and second and third node and then i have also linked elements of my list so here i have set that my head element is pointing to the second element and then my second element is pointing to the third element and then third considering that it is the last is pointing to null so that means that it is not pointing to anything which means that it is the last element of a linked list and i have also implemented a function called print list which receives head element which means the first element of this list here and if you look at the implementation of print list function you will notice that it uses while loop in order to traverse every single element of that list and in each iteration it is going to write out the value of that specific element so the value of that specific node and then it will move to the next node and it will continue doing that so it will continue moving to the next node until it comes to the node which is equal to null and at that point it will no longer enter into this while loop which means that we will leave this function here and after executing this function here we will successfully print out all of the values that are stored inside our linked list so if i run this program okay you will see that we have one two three which are the elements of our linked list so again if you need to understand this code in more detail make sure to watch my first video related to linked lists it will be in the description and now i want to show you three different ways on how you can insert an element into this list here so the first way to insert an element into a linked list will be to insert it at the front of a linked list so i will do that using a function so let's create that function and let's create it here so it will be of return type void and i will call it insert at the front like this okay and let's collapse this print list function so that i have more space to work now let's see what this insert at the front function is going to receive so what kind of parameters will i pass to this function here well this is how the invocation of this function is going to look like so i'm going to say insert at the front and then what i want to pass to this function here is going to be the address of this head node pointer so i will say please pass the address of my head and then i also want to pass the value that i want to add the value that i want to insert at the front of my list so let's say for example that will be minus 1 because this list here so this list here as you can see from my class is storing integer values so here i am passing the address of my head node and then i am passing integer value that will be added at the front of my linked list now this here means that we need to receive these two parameters inside this function here so considering that here i am passing an address of a pointer that means that here i will need to receive a pointer to a pointer so i will need to receive a node pointer to a pointer which i will call head okay so that is the first parameter and then the second parameter is just an integer number so here i will say int and let's call that parameter new value like this okay so these are two parameters that this function needs to receive in order to insert a new node at the front of a linked list so there are three steps that this function here needs to perform in order to do that in order to insert an element at the front of a linked list so let me very quickly type out those three steps so i will write them here and then we will implement those three steps together so here are three steps that we need to implement in order to insert an element at the front of a linked list the first step is that we need to prepare a new node and i will show you how you can prepare a new node in a couple of moments and then this second step says that we need to put it in front of our current head which means that we need to put that new node in front of current first node of our linked list because we are trying to add it at the front of our linked list and then third step says move head of the linked list to point to new node why well because this newly added node is now going to be the head of our linked list and what previously was the head of our linked list is now going to become the second node of that list so let's implement these three steps and let me show you how you can describe these three steps using c plus code so in order to prepare a new node you will do the following you will create a node pointer which i will call new node like this and i will allocate memory for that note so i will say new node okay and then considering that we have passed a new value which means the value for this node here we have passed that as parameter to this function what i will do is i will say that my new node the value of that node will be equal to this value here okay so that is the code that we will type for this first step and with this code here we have prepared our new node now this second step says that we need to put it in front of our current head which means that we need to say now that our new node will point to our current head so i will say that my new node dot next will be equal to our head node pointer and as you can see here i am assigning assigning a headnote pointer because this here is pointer as well as you can see here so i am assigning a pointer to a pointer and with this line of code here i have said that now my new node is pointing to my current head of my linked list and then in this third step here what i need to do is i need to say to my linked list hey this newly added node is now going to be your head so i have added an element at the front of a linked list and that element is now going to be your head so i'm going to say now that my head pointer will be equal to my new node and again this here is a pointer and my new node is created as a pointer so this here will work okay so with this code here i have successfully inserted an element at the front of a linked list and in order to test this function here i will return to this part here and and as you can see i have already invoked this function so i have said insert at the front and then i have passed address of this head node pointer and i have passed an element which has the value of minus one so if i run my program now let's see what we will get well as you can see it indeed it has successfully inserted an element at the front of our linked list which previously was one two three and now we have minus one at the front so let's stop this program and let's try invoking this function one more time so i'm going to say now please insert minus one at the front of my list and then insert minus two at the front of that list so if i run my program again as you can see we will get minus 2 minus 1 and then 1 2 3 which means that this function here has done its job so indeed it inserts an element at the front of a linked list so again how this function inserts an element at the front of our linked list well it prepares a new node here and then it says that that new node will point to the current first element of our linked list because we are trying to add a new node at the front and then after doing that we now need to say that at the head of our linked list will be that newly added node so if we had a list which was one two three in this first step here i have prepared a new node and then in this second step i have said that this new node is now pointing to my first node what previously was the first node of this list and then in this third step i now say to my linked list hey this is now your head it's no longer this element here but it is this element here so now my linked list looks like that first second third fourth so minus one one two three okay so let me collapse this function here and then i will also delete these two invocations because i want to show you how you can implement a function that is going to add an element at the end of a linked list so now i want to show you how you can insert a node at the end of a linked list so in order to do that i will implement another function which i will call insert at the end like this and this function is going to be very similar to this function here and it will receive the same parameters as this insert at the front function so i'm going to copy this parameter list and paste it here okay now this insert at the end function needs to perform four steps in order to insert a node at the end of a linked list and i will very quickly write those steps here and i will be back so that we can again implement those steps together so here are four steps that we need to implement in order to insert a node at the end of a linked list so the first step is that we need to prepare a new node that will be added at the end and then second step is a check so we need to make sure that this list is not empty because if it is empty that means that this node that we want to add at the end will actually be the first node and the last node and the only node in that list which means that that new node will become a head node of that list and then if this step here is not true so if this list already has elements we will proceed with these two steps so in this third step we will need to find the last node why well because in this fourth step we need to make that last node point to our new node that we want to add at the end so we will need to insert that new node after last node which means insert it at the end so let's implement this first step here let's prepare a new node so i'm going to say that i want to create a node pointer which i will call new node and i will allocate memory for my new node like this okay and then considering that i passed a value for my new node here i will use that value in order to assign it to the value of my new node so i will say that my new node value will be equal to new value okay and then another step is that considering that we want to add a node to the end of our linked list that means that that will be the last node so it will point to null so we can do that part here as well i can say that my new node dot next will be equal to null like this so with these three lines of code i have successfully prepared my new node that will be added at the end of my linked list now this second step here says that we need to check if our linked list is empty so that means that if our current head pointer is equal to null we will say that our current head pointer will become our new node which means that if this list here is empty so if it is null the head of our list will become this newly created node so it will become the first and the last and the only node of that list and if this here is the case we don't need to do anything else because we have successfully added that node to our list so here i can say return oh i can say return okay so with this code here i have checked if that list was empty and if it was i added a new node to my linked list and that new node had become the new head of that list and also the last element of that list and the only element of that list so that is what this code here is doing but in case that the list already contains elements so in case that it is not empty we need to perform these two steps in order to add a node at the end of that list so this third step says that we need to find the last node so how do you do that how do you find the last node of a linked list in this situation we have a list that has three nodes first second and third so how can i find this third element who knows where this third element is the answer is that the second node knows where the third node is why well because the second node is storing a pointer to the third node and then who knows where the second node is the answer is that the first node knows where the second node is why because the first node has a pointer to the second node okay so in order to access to the third node you need to traverse first second and then third so how will you access this last element how will you find this last element the answer is you will start at the first node and then you will ask hey are you pointing to any elements or are you pointing to null and then if this element here says i am pointing to a node you will move to that next node and then you will ask that next node hey are you pointing to any node or are you pointing to null and then this element here will say i'm actually pointing to a valid node so you will move to that next node which is third node and then you will ask this node as well hey are you pointing to any nodes or are you pointing to null but considering that this node here is the last one it will point to null so that is how you will know that you have come to the last element of your linked list so let's do that and let's implement this logic using a while loop so what i want to do first is i want to create a new node pointer which i will call last and initially i want to say that my last node will hold the same value as my head node pointer so i will start at the first node and then what i want to do is i want to move to the next and the next and the next and the next and so on until i come to the one that is pointing to null and in order to do that i will use while loop and i will say inside this while loop that it is going to iterate while our last next is different than no okay and in each iteration what i want to do is i want to say that my last will be equal to whatever my last next is pointing to so i will move my last element to the next and the next and the next until i come to the one which is pointing to null and at that point i will know that my last is storing the address of my last note so with this we have successfully found the last node of our linked list and then this fourth step here says that we need to insert a new node after our last node which means that now i need to say that my last node so my current last node dot next will now be equal to my new node like this okay so we have now successfully added a new node after our previously last node so in the list that has three elements first second and third i have successfully added this new node here so now what previously was last element is pointing to our new node okay so let's test this function i am going to invoke it here i'm going to say insert at the end like this and this function is going to receive the address of our head node and then it will also receive the value for the new node that we want to insert at the end so let's say that will be for example number four okay and if i run this program as you can see it says one two three four so this new element has successfully been added at the end of our linked list and if i try to add one more for example number five and run my program again as you can see now we have a list that has one two three four five elements okay so that means that this function here indeed is adding or inserting elements at the end of a linked list so how do we do that how do we insert a node at the end of a linked list well in the first step we need to prepare that node so i'm going to allocate the memory for that node and then i will say that the value of that node will be the value that i want to add at the end of my linked list which i have passed as this parameter here and then considering that this node will be the last node i can say that it will point to null and then in this second step i need to check if this list is empty because if it is empty that means that this new node will actually be the head node so it will be the first node and the last node and the only node so that is what this code here does but in case that this list is not empty we proceed with these two steps so in this third step we need to find the last node and we do that by moving to the next node until we come to the one which is equal to null and at that point we have the address of that last node stored inside this last node pointer and then in this fourth step considering that here we have successfully found our last node what i can do is i can say that now my last node will point to a new node that i want to add at the end which is this node here so that means that we have successfully added a new node to our linked list at the end of that list so let's collapse now this insert at the end and let's also delete these two invocations here because i want to show you third way to insert an element into a linked list so third way to add a node to a linked list which is going to be to insert it after a specific node so what i want to do is i want to create a third function also of return type void and i'm going to call it insert after okay now this insert after function will have to receive two parameters in order to be able to insert a node after a specific node the first parameter will be that specific node after which i want to add a new node so i will call that parameter previous or previous node and i will put it here i will say node pointer which i will call previous like this and then the second parameter will be the value for my new node so i will paste it here it's the same parameter as these two previous functions received and then this function also will have to perform three steps in order to insert a node after this node here so let me again write those steps here on the screen and then we will implement those steps and we will see how we can insert an element insert a node after a specific node so here are three steps that you need to implement in order to insert a node after a specific node the first step is that you just need to check if this previous node is null so you need to make sure that someone has not passed no value for your previous node okay and then this second step is that you need to prepare your new node and then the third step says that you need to insert new node after your previous element so how does this third step work well imagine the following situation you have node a and node b and your node a is pointing to your node b so how do you add a new node after your node a well the answer is that now your node a needs to point to that new node and then the new node will point to your element b okay so instead of your linked list going like this a b it will go like this a new node and then b okay so let's implement these three steps here let me show you how that works in c plus plus code the first step is to check if previous node is null so i will just say if previous is equal to null in that situation i will write out a message to my user and i will say that previous cannot be null like this and i will return from this function here which means that i will not continue the execution of this function here why well because here we want to receive a valid element and null is not valid element we want to receive a valid node after which we will add a new node and null is not a valid node so that is the first step and then the second step says that we need to prepare a new node so let's create a new node pointer and i will call it new node and here i will allocate memory for that node like this and then i will assign this new value as the value for my new node so i will say newnode dot value is going to be equal to new value the value that i want to add in my linked list and then this third step here says that i need to insert a new node after this previous node which means that now my previous node so now my node a needs to point to that new node and then that new node now needs to point to my node b so instead of my node a pointing to my node b now my node a will point to the new node and my new node will point to my node b but one very important thing to pay attention to is when will you break this connection between your node a and your node b so that you don't lose your node b so that you don't lose the address of your node b forever because the only one who knows where your node b is is your node a and if you do it the way that i just explained so if you first say that your node a will point to your new node at that moment you are deleting this connection in order to make this connection and you will lose the address of your node b forever if you do that so what you need to do first is you first need to say that your new node will store the address of your node b so your new node will point to whatever your node a is pointing to which is your node b and then after you have successfully stored the address of your node b inside this connection then you can break this connection so then you can say that your node a will point to your new node so let's see how we can implement that in c plus plus code so first you implement this connection so first you say that newnode dot next will be equal to whatever our previous node was pointing to so it will be equal to our previous next and then after you have successfully stored the address of your node b then you can overwrite this connection with disconnection so then you can say that your previous dot next will point to your new node like this okay so with this function here we have successfully inserted an element after a specific node so let's test this function here and i will invoke it here before my print list function i will say insert or actually insert after and what i want to do is i want to insert an element after this head node so i will say please insert after this element here so after one what i want to insert is i want to insert minus one like this and if i run my program let's see what will happen as you can see minus one has successfully been inserted after one so we have inserted an element after our head element now let's insert another element for example let's insert an element after this element here so after two i want to insert the value of -2 and if i run my program as you can see this is how our linked list looks like now so 1 minus 1 2 minus 2 and then 3 which means that this function here indeed is inserting elements after a specific element so it is inserting nodes after previous node that is passed as a parameter here okay so i hope this video helped you understand how you can insert a node at the beginning of a linked list at the end of a linked list and then also after a specific element of your linked list there is something else that i wanted to say i don't know so give this video a thumbs up and share it with your friends and if you have any questions put those in the comments down below and tag me on your instagram stories i love watching your instagram stories and i will leave links to my other social media accounts in the description of this video and thank you very much for watching i will see you in my next video bye

Channel: CodeBeauty

Views: 138,099

Keywords: how to insert a new node in a linked list, c++, codebeauty, code beauty, programming, insert a node at the front of a linked list, insert a node at the end of a linked list, insert a node after a given node, how to add an element to linked list, insert an element into a linked list, insert a node into linked list, linked list insertion at beginning, linked list insertion at specific position, linked list insertion at end, linked list insertion in c++, inserting a node, how to

Id: RNMIDj62o_o

Length: 30min 31sec (1831 seconds)

Published: Wed Mar 03 2021