In our previous lesson, we had written code
to insert a node at the beginning of the linked list. Now, in this lesson we will write program
to insert a node at any given position in the linked list. So, let me first explain the problem in a
logical view. Let's say we have a linked list of integers
here. There are 3 nodes in this linked list. Let us say they are at addresses 200, 100
and 250 respectively in the memory and we have a variable head that is pointer to node,
that stores the address of the first node in the list. Now, let us say we number these nodes. We number these positions on a 1-based index. So, this is the first node in the list and
this is the second node and this is the third node and we want to write a function Insert
that will take the data to be inserted in the list and the position at which we want
to insert this particular data. So, we will be inserting a node at that particular
position with this data. There will be a couple of scenarios. The list could be empty. So, this variable head will be NULL. or this
argument being passed to the insert function, the position n could be an invalid position. For example, 5 is an invalid position here
for this linked list. The maximum possible position at which we
can insert a Node in this list will be 4. If we want to insert at position 1, we want
to insert at beginning and if we want to insert at position 4, we want to insert at end. So, our Insert function should gracefully
handle all these scenarios. Let us assume for the sake of simplicity,
for the sake of simplifying our implementation that we always give a valid position, we will
always give a valid position so that we do not have to handle the error condition in
case of invalid position. The implementation logic for this function
will be pretty straight forward. We will first create a node. Let's say in this example we want to insert
a node with value 8 at 3rd position in the list. So, i'll set the data here in the node. The data part is 8. Now, to insert a node at the Nth position,
we will first have to go to the (n-1)th node. In this case n =3, so we will go to the 2nd
node. now the first thing that we will have to do is we will have to set the link field
of this newly created node equal to the link field of this (n-1)th node, so we will have
to build this link. Let's say the address that we will get for
this newly created node is 150. Once we build this link, we can break this
link and set the link of this newly created node as address of this, set the link of this
(n-1)th node as address of this newly created node. We may have special cases in our implementation. like the list may be empty or may be we may
want to insert a node at the beginning. let's say we will take care of special cases
(if any) in our actual implementation. So, now let's move on to implementing this
particular function in our program. In my 'C' program. the first thing that I need to do is i want
to define a Node. So, Node will be a structure. We have seen this earlier. So, Node has these two fields - one data of
type integer and another next of type pointer to Node. Now, to create a linked list, the first thing
that I need to create is a pointer to Node that will always store the address of the
first node or the head node in the linked list. So, i will create struct Node*, let's name
this variable head. And once again, i have created this variable
as a global variable. To understand linked list implementation,
we need to understand what goes where, what variable sits in what section of the memory
and what is the scope of these variables. What goes in the stack section of memory and
what goes in the heap section of the memory. So, this time as we write this code, we will
see what goes where. In the main method, first i'll set this head
as NULL to say that initially the list is empty. So, let us now see what has gone where so
far in our program in what section of the memory. the memory that is allocated to our program
or application is typically divided into these four parts or these 4 sections. We have talked about this in our lesson on
dynamic memory allocation. There is a link to our lesson on dynamic memory
allocation in the description of this video. I'll quickly talk about what these sections
are. One section of the application's memory is
used to store all the instructions that need to be executed. Another section is allocated to store the
global variables that live for the entire lifetime of the program, of the application. One section of the memory which is called
stack is used to store all the information about function call executions, to store all
the local variables. And these 3 sections that we talked about
are fixed in size , their size is decided at compile time. The last section that we call heap or free
store is not fixed and we can request memory from the heap during run-time and that's what
we do when we use malloc or new operator. Now, i have drawn these 3 sections of the
memory. Stack, heap and the section to store global
variables. In our program, we have declared a global
variable named head which is pointer to Node. So, it will go and sit here. And this variable is like anyone can access
it. Initially, value here is NULL. Now, in my program what i want to do is, I
first want to define two functions - Insert and this function should take two arguments
- data and the position at which i want to insert a node and insert that particular node
at that position, insert data at that position in the list. And another function Print that will simply
print all the numbers in the linked list. now, in the main method i want to make a sequence
of function calls. First i want to insert number 2, the list
is empty right now so i can only insert at position 1. So, after this Insert, list will be having
this one number, this particular number 2 and let's say again I want to insert this
number 3 at position 2. So, this will be our list after this insertion. And i will make two more insertions and finally,
I'll Print the list. So, this is my main method. I could have also asked a user to input a
number and position, but let's say we go this way this time. Now, let us first implement Insert. I will move this Print above. So, the first thing that I want to do in this
method is, I want to create a Node, so I will make a call to malloc. In C++, we can simply write a new Node for
this call to malloc and this looks a lot cleaner. let's go C++ way this time. now, what I can do is, I can first set the
data field and set the link initially as NULL. I have named this variable temp1 because I
want to use another temp variable in this function. I'll come to that in a while. We first need to handle one special case - when
we want to insert at the head, when we want to insert at the first position. So, if n is equal to 1, we simply want to
set the link field of the newly created node as whatever the existing head is and then
adjust this variable to point to the new head which will be this newly created node. And we will be done at this stage so we will
not execute any further and return from this function. If you can see, this will work even when the
list is empty because the head will be Null in that case. I'll show a simulation in the memory in a
while, so hold on till then. Things will be pretty clear to you after that. Now, for all other cases, we first need to
go to the (n-1)th node. As we had discussed in our logic initially. So,what i'll do is i'll create another pointer
to node, name this variable temp2 and we will start at the head and then we will run a loop
and go to the (n-1)th node something like this. We will run the loop n-2 times because right
now we are pointing to the head which is the first node. So, if we do this temp2 = temp2->next n-2
times, we will be pointing temp2 to (n-1)th node. And now the first thing that we need to do
is set the next or the link field of newly created node as the link field of this (n-1)
the node and then we can adjust the link of this (n-1)th node to point to our newly created
node. And, now i am writing this Print here. I have written this print here. We have used a temporary variable, a temporary
pointer to node initially pointing to head and we have traversed the whole list. Ok, so let us now run this program and see
what happens. We are getting this output which seems to
be correct. The list should be 4 5 2 3 in this order Now,
i have this code. I'll run through this code and show you what's
happening in the memory. When the program starts execution, initially
the main method is invoked. Some part of the memory from the stack is
allocated for execution of a function. All the local variables, and the state of
execution of this function is saved in this particular section, we also call this stack
frame of a function. here in this main method, we have not declared
any local variable. We have just set head to NULL which we have
already done here. Now, the next line is call to function Insert. So, the machine will set the execution of
this particular method main on hold and go on to execute this call to insert so insert
comes into the stack and insert has couple of local variables. it has two arguments - data and this variable
n. This stack frame will be a little larger because
we will have couple of local variables. And now we create this another local variable
which is a pointer to node temp1. And we use the new operator to create a memory
block in the heap and this guy temp1 initially stores the address of this memory block. Let's say this memory block is at address
150, so this guy stores the address 150. when we request some memory to store something
on the heap using new or malloc, we do not get a variable name and the only way to access
it is through a pointer variable. So, this pointer variable is the remote control
here kind of. So, here when we say temp1->data is equal
to this much, through this pointer which is our remote we are going and writing this value
2 here and then we are saying temp->next = NULL. So, null is nothing but address 0. So, we are writing address 0 here. So, we have created a Node and in our first
call n is equal to 1, so we will come to this condition. Now, we want to set temp1->next = head. temp1->next is this section, this second field
and this is already equal to head. head is Null here and this is already null. Null is nothing but 0. the only reason we said temp->next = head
will work for empty case is because head would be null. And now we are saying head is equal to temp1. So, head guy now points to this because it
stores address 150 like temp1. And in this first call to insert, after this
we will return. So, the execution of insert will finish and
now the control will return to main method. We come to this line where we make another
call to Insert with different arguments this time, we pass number 3 to be inserted at position
2. Now, once again memory in the stack frame
will be allocated for this particular call to insert. The stack frame allocation is corresponding
to a particular call. So, each time the function execution finishes,
all the local variables are gone from the memory. Now, once again in this call we create a new
node. We keep the address initially in this temporary
variable temp1. let's say we get this Node at address 100
this time. Now, n is not equal to 1, we will move on
to create another temporary variable temp2. Now, we are not creating a new node and storing
the address in temp2 here. We are saying temp2 is initially equal to
head. So, we store the address 150. So, initially, we make this guy point to the
head node. And now, we want to run this loop and we want
to keep going to the next node till we reach (n-1)th node. In this case, n = 2 so this loop will not
execute this statement even once. (n-1)th node is the first node itself. Now, we execute these two lines. The next of the newly created Node will be
set first, so we will build this link.. oopss.. NO.. temp2->next is 0 only. So, even after reset this will be 0. And now we are setting temp2->next as temp1,
so we are building this link. And now this call to insert will finish, so
we go back to the main method. So, this is how things will happen for other
calls also. After everything we have inserted, when we
will reach this print statement in the main function, our list will be something like
this in the memory. This is a little messy. i have chosen these addresses as per my convenience
for the sake of example and now Print will execute and once again I'm using a temp variable
in Print. By now, it should have been clear to you why
we use temp variable again and again and why this variable head that stores the address
of the first Node is so important. Now what if this head was not global, what
if we would have declared this head inside the main method. We have talked about this in our previous
lesson. head will not be accessible everywhere. So, in each call to these functions, in each
call to insert we will have to return some value from the function to update this head
or we will have to pass this head by reference. We have talked about this in our previous
lesson. So, this is it for this lesson. In our next lesson we will see program to
delete a node at a particular position in the list. So, Thanks for watching !
