How to insert a new node in a linked list in C++? (at the front, at the end, after a given node)
Summary
TLDRThis video tutorial delves into the intricacies of linked lists, demonstrating three distinct methods for inserting nodes: at the front, at the end, and after a specific node. The presenter provides a clear, step-by-step guide through the process, complemented by C++ code examples. Viewers unfamiliar with linked lists are directed to an introductory video, while the current tutorial focuses on practical implementation, ensuring a comprehensive understanding of node insertion techniques.
Takeaways
- π The video discusses three methods of inserting elements into a linked list: at the front, at the end, and after a specific node.
- π¨βπ« For those unfamiliar with linked lists, the creator suggests watching an earlier video for a foundational understanding and implementation guide using C++.
- π The code for a basic linked list implementation in C++ is provided, including the creation of nodes and a 'printList' function to display list contents.
- π The 'insertAtFront' function is explained, detailing the steps to add a new node before the current head of the list, which involves creating a new node and adjusting pointers.
- π To insert at the front, the new node's 'next' pointer is set to the current head, and then the head pointer is updated to the new node, effectively adding it to the front.
- π The 'insertAtEnd' function involves checking if the list is empty and then finding the last node before inserting the new node after it, ensuring the list's integrity.
- π The process of finding the last node in a non-empty list is demonstrated using a while loop that traverses to the node pointing to null.
- π The 'insertAfter' function requires a reference to a specific node and a value to insert after it, and it involves checking for null references and updating pointers to maintain the list structure.
- π When inserting after a specific node, it's crucial to first set the new node's 'next' pointer to the subsequent node to avoid losing any elements in the list.
- π οΈ The video provides practical examples of invoking the 'insertAfter' function to demonstrate how elements are added to the list after a given node.
- π The video concludes with an invitation for viewers to like, share, and comment on the video, as well as to engage with the creator on social media.
Q & A
What are the three different ways to add an element into a linked list as discussed in the video?
-The video discusses inserting a node at the front of a linked list, at the end of a linked list, and after a specific node within the list.
What is the first step in inserting a node at the front of a linked list?
-The first step is to prepare a new node by allocating memory for it and assigning the new value to the node.
How does the 'insert at the front' function update the head of the linked list?
-The function updates the head of the linked list by making the new node the head, and then making the old head the next node in the list.
What is the purpose of the 'print list' function in the script?
-The 'print list' function is used to traverse and print out all the values stored in the linked list, starting from the head node.
What is the significance of the 'head' pointer in a linked list?
-The 'head' pointer is significant as it points to the first node of the linked list, and is used to traverse the list.
How does the video script ensure that the newly added node at the front of the list doesn't lose connection with the rest of the list?
-The script ensures this by first making the new node point to the current head (thus not losing the connection), and then updating the head pointer to the new node.
What are the steps involved in inserting a node at the end of a linked list?
-The steps are: 1) Prepare a new node, 2) Check if the list is empty (if yes, make the new node the head), 3) Find the last node, and 4) Make the last node point to the new node.
Why is it necessary to check if the previous node is null in the 'insert after' function?
-It is necessary to ensure that a valid node is provided after which the new node will be inserted, as inserting after a null node would not be meaningful.
How does the 'insert after' function handle the connection between the previous node and the node following it?
-The function first stores the address of the node following the previous node in the new node, and then updates the 'next' pointer of the previous node to point to the new node.
What happens if the linked list is empty when trying to insert a node at the end?
-If the list is empty, the new node becomes the head of the list, as well as the last and the only node in the list.
Can you explain the process of finding the last node in a linked list as described in the script?
-The process involves starting at the head node and iteratively moving to the next node until a node is found that points to null, which indicates it is the last node in the list.
Outlines
π Introduction to Linked Lists and Insertion Methods
This paragraph introduces the topic of linked lists and outlines the video's purpose, which is to demonstrate three methods of inserting elements into a linked list: at the front, at the end, and after a specific node. The speaker also refers viewers to a previous video for a basic understanding of linked lists and their implementation in C++ programming language. The provided code snippet is a brief overview of a linked list implementation, including a 'Node' class, a 'printList' function, and a sample linked list with three nodes.
π Detailed Explanation of Inserting at the Front of a Linked List
The speaker explains the process of inserting a node at the front of a linked list through a function named 'insertAtTheFront'. The function takes two parameters: a pointer to the head node and the value to be inserted. The steps include creating a new node, adjusting pointers to place the new node before the current head, and updating the head pointer. The speaker provides C++ code examples for each step and demonstrates the function's effectiveness by inserting elements with values of -1 and -2 at the front of the list.
π Steps for Inserting a Node at the End of a Linked List
This paragraph details the steps required to insert a node at the end of a linked list within the 'insertAtTheEnd' function. The process involves preparing a new node, checking if the list is empty to determine if the new node should become the head, finding the last node in the list, and then updating the last node's pointer to the new node. The speaker also provides C++ code snippets for each step, illustrating how to traverse the list to find the last node and how to add a new node to the end.
π Implementing the End Insertion with C++ Code
The speaker implements the 'insertAtTheEnd' function in C++ and tests it by adding nodes with values of 4 and 5 to the end of the list. The function first checks if the list is empty and sets the new node as the head if true. If the list is not empty, it finds the last node using a while loop and updates the last node's 'next' pointer to the new node. The results of running the program confirm that the new nodes are correctly added to the end of the list.
π Inserting a Node After a Specific Node in a Linked List
The paragraph explains how to insert a node after a specific node within the 'insertAfter' function. It requires two parameters: a pointer to the specific node after which the new node is to be inserted and the value for the new node. The steps include checking for a null previous node, preparing the new node, and then adjusting pointers to insert the new node in the correct position. The speaker emphasizes the importance of maintaining the connection to the subsequent node to avoid losing it and provides C++ code to demonstrate the process.
π Testing the 'insertAfter' Function with C++ Code
The speaker tests the 'insertAfter' function by inserting elements with values of -1 after the head node and -2 after the second node in the list. The function is demonstrated to work correctly, as shown by the updated list output after each insertion. The process involves checking for a null previous node, creating a new node with the specified value, and then reassigning pointers to insert the new node after the given node.
π Conclusion and Call to Action
In the concluding paragraph, the speaker invites viewers to like the video, share it with friends, and ask questions in the comments. They also encourage viewers to tag them on Instagram stories and provide links to their social media accounts in the video description. The speaker thanks the viewers for watching and looks forward to seeing them in the next video.
Mindmap
Keywords
π‘Linked List
π‘Node
π‘Insertion
π‘Head
π‘Pointer
π‘Traversal
π‘Null
π‘Function
π‘Parameter
π‘Memory Allocation
Highlights
Introduction of three methods to insert elements into a linked list.
Explanation of inserting a node at the front of a linked list.
Description of creating a 'node' class representing elements of a linked list.
Demonstration of linking nodes to form a linked list.
Implementation of a 'print list' function to traverse and display list elements.
Guide on how to prepare a new node for insertion.
Process of updating the head pointer to include a new node at the front.
Testing the 'insert at the front' function with example values.
Introduction of the 'insert at the end' function.
Steps to insert a node when the list is empty.
Traversal method to find the last node of a non-empty list.
Inserting a new node after the last node in the list.
Testing the 'insert at the end' function with additional elements.
Introduction of the 'insert after' function for specific node insertion.
Null check for the 'previous node' to ensure valid insertion.
Detailed steps to insert a node after a given node in the list.
Testing the 'insert after' function with specific node insertion.
Summary of the video's content on inserting nodes in various positions of a linked list.
Transcripts
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
Browse More Related Video
5.0 / 5 (0 votes)