in our previous lesson we wrote program
to insert a node at nth position or a given position in
a list, in a linked list now in this lesson, we will write a
program to delete a node at any given position in a
linked list. So, once again I have drawn a linked list here. We have four nodes in
this list at addresses 100 200 150 and 250 respectively so this is my example of
a linked list of integers. and let say we number the positions on a one
based index, so this is the first Node in the list
and this is the second Node this is the third Node and this is the fourth Node when we talk about deleting a Node
from the linked list. We will have to do two things
first we will have to fix the links so that
the Node is no more a part of the list let's say, in this case we want to delete
the node at 3rd position so will go to the second node. For nth Node
we will have to go to the (n-1)th node and we will have to
set the link part of the (n -1)th node as the link of the nth mode which will be the (n+1)th node
so we will cut this link and now this Node with address 150 is not
part of the linked list because when we will traverse the
linked list, we will go from address 100 to 200 and from 200, we will go to 250. This is
one scenario for deletion in which we have a node
before and a node after there will be special cases like we may
want to delete the node at the first position or the head itself. In that case we will have to point
head to the second node. We will have to build
this link We will talk about all these
special cases in our implementation. Let's first understand the
logic. Now fixing the links is not good enough
because all that we do when we fix the links is that we detach the node from the
linked list so that it is no more accessible but it is still
occupying space in the memory as we knoe Node is allocated space
from what we call the dynamic memory or the heap section of the memory. we
have talked about this earlier In C or C++ we have to explicitly
free this memory when we are done using it because it is not automatically deallocated and memory being a crucial resource we
do not want to consume it unnecessarily when we do not
need it so the second thing that we will have to
do is we will have to free the space that's being taken by the Node and that's when the
Node will actually be deleted from the memory
so let us now write code for this. I am
writing my C program here the first thing that I have done is I
have defined a Node which is a structure with two fields one to store data and another to store
address of the next node. so, the second field
is a pointer to node. Now to create a linked list, we will have to first create
a pointer to Node a variable which is pointed to Node and
that will store the address of the head node or the first
node in the list and now I want to define three functions first insert function that will take some value, some data to be inserted into
the list and always insert this value at the end
of the list, then I want to define up print function that will print all
the elements in the list. We have defined this
variable head as a global variable, so it will be accessible to all these functions and the third function
that I want to write is delete that will take the position n of the node to be deleted and delete
the node at that particular position. We will go back
to implementing these methods. First I'll write the main method
so in the main method, first what I'll do is I'll
set head as NULL, so at this stage the list is empty and then I'll make couple of calls to insert
function to insert some integers in the list so after this fourth insert, the list will
be 2,4,6,5 because we're always inserting at the end of the list. this insert function will
insert the node at the end of the list now, what I want to do in my main method
is that I want to ask user for a position and I'll input this position from the console
and then I'll delete the node at this particular position and then I'll print the whole linked
list Let's also make a call to print after all inserts. Okay, so this is what we want
to do in our main method, we want to
80
00:04:50,000 --> 00:04:53,090
insert 4 integers in a linked list to create a list. 2, 4, 6, 5 in this order and then I want to print the list. then
I want to input a number from the console and delete the Node that particular
position. Now, let us assume that we will always give a valid
position and in my implementation also I will not handle the error condition
when position will not be valid We have seen implementation of
insert and print earlier, so i will not go into their
implementation details what I do now is I will implement delete
function Now in my delete function let's
first handle the case when there is a Node before the
Node that we want to delete so we'll have no (n -1)th node what I'll do is first i'll create a
temporary variable that is pointer to Node and point this to head and using this
96
00:05:44,410 --> 00:05:47,410)
temporary variable, we will go to (n-1)th Node. To go to the (n-1)th Node, we
will have to run a loop n-2 times and we will have to do something like this temp1 = temp1->next Now, what I'll do is, I'll create a variable
to point to the nth Node, name this temp2, and this
will be equal to temp1->next and now I can fix the
link I can say that adjust the link section,
the link part of (n-1)th Node to point to (n+1)th Node which will be temp2->next.
now, our link is fixed and this variable temp2 stores the nth node, reference to
the nth Node, so we can make a call to Free function.
Free function deallocates whatever memory is
allocated through malloc if we were using c plus plus and used and if we would have used new operator
we should have said delete temp2. Okay now we should
be good this much code will work for scenarios
when we have an (n-1)th Node and even if there is
no (n+1)th node If (n+1)th position is null, this will
work for that scenario I leave that as an
exercise for you to validate Now, we have not handled one special case when
we want to delete the head Node, so if n = 1 then what we want to do is, we just want
to set head as temp1->next. temp1 is right
now equal to head and now head has moved on to point to
the second Node and temp1 still points to the first
node. so links are fixed and we can free the
first node which is not detached from the linked
list because head is now pointing to the second node okay, so this is our delete function. I have missed one thing here. for n not equal
to 1, we should not execute this section of the code. So either we put an else statement after this or what we can do is, we can say return
after we execute these statements for this condition. Now this code should work if I've got everything right. so let us
now run this and see what happens I have already written the insert and
print functions I'll come back to this main function
this is my list 2,4,6,5 and I can enter any of the
positions - one two three or four so let's first say we want to delete
the head node and we are printing the list after deleting a particular Node, so the list now is
4, 6, 5. this seems to be correct Let us run this again and this time I
delete number 5 from position 4 the list is now 2,4, 6 which is correct again similarly if I enter position 2, the list
is 2,6,5 which is correct. so we seem to be good.
I'll quickly walk you through this code in the logical view to make thanks further clear. Let's say we first make a call to delete Node from
the first position that is we want to delete the head node.
So, in this code, what we are doing is we are first creating a variable temp1
which is pointer to Node Initially temp1 is equal to head
So, it stores the address 100,
so it points to the head Node now n =1, so we come to
this instruction head = temp1->next actually this is temp arrow dot next, but while reading we read this as temp1 dot next. This is nothing but a
syntactical sugar for this statement (*temp1).next So, we are dereferencing this pointer
variable to go to this Node and then accessing the
next field of this node now we're saying head= temp1->next,
so head is now 200. So, we are building this link and breaking this link and now in the next line we see free(temp1)
so we want to free the memory which is being pointed to by this
variable temp1 temp1 still points to this
node at address 100 so, this node now will be cleared from
the memory and now we return, so this function does not
execute any further, it finishes its execution. Once the function
execution finishes, temp1 which was a local
variable also gets cleared from the memory. head
is a global variable so it does not get cleared this is how we know the linked list. This
is the identity of the linked list this particular variable head let's rerun this code again and this
time I want to delete the Node at 3rd position in the list. I have
drawn this initial list. So, once again we create
this variable temp1. We say that the address
here is equal to 100 so it points to the head Node or the
first Node and now n is not equal to 1. it is equal
to 3 so we come to this particular loop
n is equal to 3, so this loop will execute exactly once.
this statement will execute exactly once so temp1 will now move to address 200 so temp one is now pointing to the
second node this is what we wanted to do. we
wanted temp1 to point to (n-1)th node, n is 3 here. Now, we create another
variable another pointer to Node, temp2 and we
set this guy as temp1->next. temp1->next is 150. so we set this guy as 150. so this guy
points to the nth node or the third Node. Now, in the next line we are saying that temp1->next this value which is 150 right now is now temp2->next, address of the (n+1)th
node or 4th node So this guy will now be 250 So, we are building this link and we're
breaking this link so we have fixed the links and now
finally we are seeing that free the memory which is being pointed to by temp2.
so now this third Node the memory block will be deleted from
the memory and once this function execution finishes all the local variables temp1 and
temp2 will be cleared and this is what the list will be. This
Node at address 250 will now be the third node so, this was deleting a Node at a
particular position in the linked list we can also have a problem where we may
want to delete a Node with a particular value. You
can try implementing it. in the coming lessons, we will see more
problems are linked list so, thanks for watching !
