Hello all and welcome back.
So in this video let us now move forward and implement inserting at tail of our linked list.
So insert at tail.
Before that just one thing which we forget in the last video.
Finding out the complexity of my insert at head function.
Right.
So the same actually is pretty easy if you think about this.
We are just doing some constant operations, right?
It doesn't matter how long your linked list is or if it is if it has anything or not for that matter.
You just are changing the head by doing some key operations.
So pretty straightforward that the complexity is going to be O of one.
Right?
So complexity is O of one O of n to the power zero.
So let me write that down as well everyone.
So yeah time complexity inserted it.
As.
As only constant operations.
In place or to the power o n to the power zero, which is equal to O of one.
So it doesn't matter how long your linked list is inserting, it is always o of one as compared to O
of n.
For our array.
Right?
Great.
Cool everyone.
Now let us see insert at tail.
Right.
Again let us quickly draw a linked list.
So this is the node I'm going to make sure to always draw this so that you also get into the habit.
Right.
Now let me join this as well.
Cool.
So now if I am inserting at tail everyone then what we have to do I think it's pretty easy to understand.
We have already done similar kind of work in your print or take input function, so we just have to
make sure that we are able to find our tail.
Right.
So let me draw a new node as well.
Let's say this node as of now it is 100 and it is pointing to none as of now.
Right.
So I just have to make one connection here, which is first I have my head which is equals to this.
So my head is equals to this particular node.
I have to make a temp variable here.
So let's say I create a temp variable using that temp variable I'm going to go and find my tail.
Now we have already seen this.
The tail is where the next is none right.
So once I'm able to reach to my tail I just have to ask my tail that hey, can you please make a change?
And now please point to this node.
And if you do this because the last of this node is none.
You are all set, right?
So yeah, I think this is pretty straightforward.
Again, just let us compare this again as well with our array.
Now doing this because it is normally asked in interviews when we have an array or a list.
Right.
So compare.
With array or list.
Now adding to tail is normally an append function.
We have seen that list normally works on the principle of your dynamic array.
So we will have to take the worst case right?
We will have to take the worst case.
In the worst case, we will assume that we have to create a new array, right.
And we will be adding to the end of it, because we cannot assume that there is always the space to
add.
So we will have to create a new array.
Let's say this array is completely full okay.
And then we will have to create a complete new array copy everything and thus the complexity will become
O of N.
Time complexity.
Because we will have to make sure that we are increasing our array.
Right.
So if the space is not there, that is how we do it.
That is how a Pin function actually also works.
We have seen this already everyone.
Now let us write the code for insert at tail.
Everyone let me let us go to the code and see.
Okay so yeah we will just call it here only.
Def insert at tail right.
So we will be getting the head and the data at the very first thing.
I think we can make a note that is common making the node.
Now if you think about this there is just one case in inserting a tail.
What if your head is none?
So if there is nothing in your head right, like the linked list is empty, so let us write that down.
That's a special case.
When linked list is empty.
We have to just return.
The new node.
I hope that makes sense.
Right.
So if the linked list is empty and you are trying to add anything.
So it's very analogous to if your list is empty.
Okay.
Your array is empty and you are adding an element.
So that's the first element.
So you will have to change your head and it will become the new node.
So again what we are going to do we have to make this check first.
If my head is none then I can just return this new node as it is, right.
So if the list is empty.
Then new node becomes the head.
Straightforward, right?
So again you have to always make sure that you are handling these edge cases right.
So if that's the case then of course we can do it.
If not if this is not the case then I'm going to write a loop right.
So I'm going to take a temp first.
We don't want to lose our head.
So temp is equals to head while temp dot next is not equal to none.
Okay.
What we are going to do.
Temp is equal to temp dot.
Next.
Now this is the same thing which we have done here.
So I'm pretty sure all of you will remember this is what we did in our take input function as well right.
So when we need to get to the tail, once we get to the tail we are just inserting it.
So pretty straight and common thing we are doing here as well we are just inserting.
So in temp dot.
Next we will have a new node and once this is done, we can just return it.
Great.
I think this should work.
So to check it, just let us have this call again after inserting it till now.
Okay.
Let me just copy and comment it so that you can use it at your end as well.
Head.
I am commenting this for the time being.
So yeah.
Let us now try to run this one and see what exactly is going to happen.
So yeah, once I run this it is asking me for the value.
Enter the value of node.
So let me enter ten, then 20, then 30 and minus one.
So this is my first list ten 2030.
And after inserting at ten it is saying that it is added 100.
Okay.
So when I run this one more time, let's run this one more time.
This time I'm passing an empty list.
So minus one I think.
Yeah, it seems to work.
It is not giving us the error right?
Yeah, let me just do that.
Let me just remove this and show you why this particular condition is required.
If you remember, I told that if you are calling any attribute on none, it's going to be a problem.
So if your head is null, if your head is null and you call this none dot, next it's going to give
you an error and see if the list is empty minus one we get an error.
None.
Time object has no attribute.
Next.
Right?
So that's the reason we have to always make sure that we handle such cases.
Great.
So yeah I hope this is clear everyone.
Now what you have to do I have an homework for you assignment.
You have to make sure that you implement this same function but recursively.
Right.
So this is some function which we can very nicely do using recursion.
So you have to do this at your end and write the code for insert at tail recursion.
Now one thing let us move forward and see the overall time complexity of this function.
So time complexity.
I think it should be a lot clear.
We have already seen this in our take input function.
Time complexity is going to be o of n.
The reason for that is we have to travel to our tail, right?
So we start from head one by one.
We go till we reach the tail, and once we are able to reach the tail, then we add here, right?
So if the linked list is of n size, I will have to make sure that my loop runs for n minus one times,
right?
So o of n is the time complexity as we traverse to tail.
Now please make sure that you understand this.
I don't want all of you to remember this.
That's why I'm making sure to compare and tell you while we are writing the code.
Okay, cool.
Then everyone please try the recursive way of doing this in the assignment section.
The next assignment.
And yeah, we should be good.
Let's meet in the next video.
Thank you.