Hello all and welcome back.
So in this video let us continue our discussion.
And now let's try to find out the complexity of our take input function.
So I'm pretty sure you would have also tried the same.
And we have learned complexity a lot in depth in our previous modules.
So to understand the complexity again, and we will surely be finding out the worst case complexity,
right?
Let us first draw our linked list, or let me copy that from the one which we draw earlier.
So let me just copy this particular one.
We just place it here.
Yeah.
Right.
So let us think in terms of what my temp will have to do.
Right.
So first let us go and see our code.
If we see our code okay.
So based on all these steps the way we follow it this is some quirk.
This is some quirk Right this creating of nodes.
Right.
This creating of nodes will.
Actually be done based on how many times or how many nodes I am creating.
So if I'm creating n nodes of course this while this one is going to run n times, but I believe that
this is fine because again, if I'm trying to just create n nodes, then to join them at least n time
the loop should run right.
The bottleneck I think occurs in this particular loop, right?
Because if we see here it's inside another loop and it is starting from head and trying to go all the
way till my tail.
So it is starting from head and going all the way to my tail, right.
So let us see that how much work it has to do, how much work it has to do basically.
So let me remove everything and yeah, let us see this.
Everyone here.
So for the time being just let us think when we have just created temp, right?
When we have just created our temp.
In this case, let me just write it by.
Right.
Yeah.
So when we create our temp initially when just one node is there.
So when just one node is there of course it has to not go anywhere.
Right.
Just a single.
It is staying on head only when we have when we have two nodes, it has to traverse one node because
it is on head and it has to go to the next node.
When we have three node it has to traverse two nodes because it will start from here.
It will start from here then jump first here and here right.
Similarly if we have if we are on four then it will be traversing three nodes right.
So with this understanding and let me just show you this in Python tutor as well everyone.
So it is a lot clearer.
So let us go to Python tutor.
Yeah.
If we see here everyone.
Now let me just take it back when we were adding the last node.
Right.
So when we are adding this particular node let me just have this temp here.
Right.
See.
So our node is getting created with the value of 50 okay.
Value of 50.
The node is getting created.
Then we are initializing our temp.
So in this line at this line temp gets initialized to my head.
And now it will have to jump to the last node.
Hence it will be taking these three steps right.
So in a linked list of four it has to take the three steps okay.
So let us see this once as well.
It's jumping to the second node as we can see.
Now on to the third node.
Let me just remove this for the time being so we don't get confused.
One second.
Yeah.
So now let us jump to the second node.
Now to the third node.
And now to the fourth node.
Right.
So this overall loop I think it works n minus one times for a linked list of length n okay.
And the outside loop is running n times because it is adding my linked list n where is the length of
my linked list, right?
So let us see this once then everyone.
This is how what I feel the complexity is.
So if we just x ten it for n this is n minus one.
Right now we have done this a lot of time in our time complexity lecture.
Outer loop.
Complexity is coming out to be n inner loop.
Again complexity is coming out to be n okay.
So we have seen how exactly it happens.
So the time complexity, the big O time complexity.
Is going to be O of n squared.
Right.
Which to me seems a little bit bad in terms that I am taking the input.
Right.
So in just initializing my linked list, why is the complexity so bad if I just want to initialize my
linked list, right?
We are aware that how o n square is a pretty bad complexity in terms of any operation.
So now let us discuss.
Is there some way, is there some way?
We can reduce it.
Reduce our time complexity.
Okay.
So as of now we have seen how it is o n square.
Right.
So let me write it as well.
So this is comparatively bad.
Pretty bad.
Just for taking input.
Right.
So just for taking input, it seems to be pretty bad.
Now if we just follow the process again, if we just see the process in code again, let me go back.
This was the major place where we were doing some work, which I think could have been avoided.
How it could have been avoided.
We were doing this work to find the tail of my linked list, right?
But what I feel is that we can actually save the tail as well in another variable.
So what I'm suggesting is that instead of every time going over my linked list to find the tail, what
we should instead do is to make sure that we are able to save our tail as well, and just directly add
into that how we can do that.
Let's see.
Okay, so first let me create a tail which is none as well.
Now again the understanding which we have discussed previously as well.
If a single element is there then head and tail both are same.
If we have just zero elements then head and tail both are none.
So if no node is added then of course I can directly return this head.
It will be none and again tail.
I'm just using to add things.
Okay, to add nodes into my linked list.
We don't have to return that because again, the head is the major item which my user will get and can
then traverse the list.
Great.
So now let us see how we can avoid the same.
Let me just comment this out for the time being.
Okay, let me just do one thing.
Rather it will be better.
Let me just copy this whole code and make a new function which we can say take input better.
Okay, so take input better.
I'm creating a tale here.
Now let us see how we can actually use the tale.
Now I am saying that along with head along with head, I am going to maintain a tale.
Let me just use this color for tale.
So I am going to maintain a tale as well, right?
Now for the first element, of course, head and tail.
Both are both are going to be same, right?
The first node is going to be the head as well as tail.
Let us imagine what's going to happen when we add the second element.
Okay.
So let me just draw this as well so we can imagine the same.
This is the first element as of now my head is this and my tail is this.
And both are pointing to this particular element right.
Now when I want to add when I want to add a second element, then I feel what we can do is we can just
say that.
Hey, Dale, can you please, in your next save this element.
So as of now, Dale is the first node.
I am just asking my tail.
Hey, can you please save this as your next element?
And I think, yeah, that is a reasonable thing to ask and it should be able to do that, right?
But once I do this then I believe my tail has also changed.
And what it has changed to, it has actually changed to the same element where we asked it to point.
Right.
So instead of this now instead of this, first I should ask my tail to point to the new node, and then
I should make my tail as new node only, right.
So this is my new node now.
Great.
So let us see this.
If I add another element one second.
So if I'm adding another element here.
Now can we do the same thing again?
So what I'm saying is that as of now, of course it is none.
I am saying that.
Hey, Dale, can you please in your next add this element.
So that seems like a reasonable thing to do.
And then Dale, can you please, instead of this, can you please go and become this element?
So this seems fine as well, right.
So I believe what are the steps if I just code it down?
What we are saying is Dale dot next is equals to new node.
That's the first thing which I am saying.
And the next thing is I'm saying that Dale is equals to new node.
Right.
Or I can say tail dot next because again they are same from the previous line.
If I am able to do this, I feel that we will be able to use tail and also then complete my linked list.
So let us see the same in code as well.
Everyone.
What effectively I'm saying is I'm going to create a tail, head and tail.
Initially both are going to be none.
Then moving forward again, this time, if head is none, I have to also make tail equals to new node,
right?
Something which we saw.
So let me go back to our diagram and see.
Initially both of them were equal to the first node right.
So it is the head.
It is the tail something which we have seen already.
Now this part is where I can do some optimization and what optimization I can do.
Let us see.
I am saying that tail dot next is equals to new node.
And again along with that I'm saying tail become new node.
Okay.
So yeah this seems to do the trick.
I hope you're able to actually visualize again in linked list.
Please never remember any logic.
Always form the same using visualization.
So I just asked my team, whatever is my team.
The next is going to be null, right?
I just ask it to remember the next element and then make the next element as the recently added element.
Now, if we think about this intuitively, if you remember that child example which I gave you children
in a park, let's say you know who your first child is and who your last child is.
Now you can ask your last child that, hey, can you please remember that this is another person who
we have to add into our class or something, and then we can remember that he he was the last child,
right?
We will also have to change our tail.
We will also have to remember or change our understanding that.
Who is the last child?
Okay.
So based on the similar intuition, I have just written and coded my logic.
Okay, so now let us try to run this.
Let us try to run this once.
So just let me call this take input.
One second.
Better.
And if I run this code, let us see.
So ten, 20, 30, 40, 50 minus one.
It seems to work.
It seems to work okay, but a better way to check that will be to visualize in Python tutor.
And we will see the steps as well.
Okay so let's see everyone.
So I've just pasted my code here.
We have already seen the code.
Just this part is changed.
So I've just added this tail part.
And next this part.
Let me visualize it.
So first yeah let us define all these functions.
Take input is not used but should be fine.
Okay.
So now it is asking me for the value.
Let me input ten as the first node.
Let it go forward.
See head is none.
Tail is none.
If at this point the value would have been minus one, we would have just written our head and it is
none.
As expected, it's an empty linked list.
So let's move forward, everyone.
For the time being, I'm saying create a new node so we know that new node is going to get created by
the value of ten.
And if it is created and because it's the first node, I'm going to ask my head and tail both to point
to this node only.
Right.
Because in a single element single node linked list head and tail, both are the first node.
Great.
So let me now enter 20.
Right.
So let us see for 20 now what happens.
So new node node value.
That is fine.
It's going to create a node with value 20.
It should be great.
Now again it's going to check if my head is equal to none.
I don't feel that's the case.
So if it is not none we are going and doing tail dot next.
So tail is this only next of tail is none.
I am saying hey make this connection.
Make this connection right.
So this connection gets made.
And now I will be just asking my tail.
Because if now we actually think about in a two node linked list, this is my tail, right.
This is my tail.
So I'm going to just ask my tail.
Hey can you please become this new node and we can see that it's done.
Let me enter 30.
So one second let me enter 30.
Right.
So for 30 now what is happening.
Let's see okay.
For 30 I see that.
Yeah.
You know it's going to get created.
This time the benefit is if we see okay if we just print it out head is not none.
So that is fine.
When I go to this else statement I don't have to write a loop.
So I'm not creating any temp variable which starts from head.
And then basically go to my last node.
Tail is having that information already.
I'm going to just join it.
Okay.
And see.
Similarly let's do for 40.
Okay.
So let me do this.
Mm.
Yeah.
New node is created.
So these are all the steps which you have seen again.
Now when I go back the node is created.
You will see that head is not none.
So we are going to go to else and then else.
My tail is this just I will ask hey tail can you point to this?
And I will ask tail to become the last node, which is the new node which we have created, right?
So this is the new node.
This is my tail, this is my head.
So I am not moving head head.
I have finalized once after I have just initialized my linked list.
All the work I'm just doing using tail, which seems to actually be the case because we are always adding
each and every element towards the end, so we should not even disturb our head.
Okay.
And if the tail is there, we can just use that to add the elements.
Right.
So again that is done.
And you can see that how quick it is.
Right.
So now let me add 50 summit.
And in the same way of course no new loop or something is going to work.
We already know what tale is.
This is the tale and the temp variable which was previously jumping these four nodes.
Now nothing like that is going to happen.
So see till next.
And yeah, we are all good.
Let me now come out minus one summit.
Great.
So let's come out head see.
So here again everyone please pay attention.
How nicely.
Just by returning this value I am just giving the ownership of this linked list to new head.
Right.
So pay attention.
See, this is the new head and you can visualize.
Right?
So that's the best part.
You can visualize how all of them are joining.
It's right in front of you.
And we have seen each and every step okay in front of us and see that how in the last implementation,
temp was jumping from one to next every time.
But now we have just reduced all that steps.
Now again, if we just try to print it, we will surely be able to print the same.
So if I just move it to the last, we are able to see the linked list getting printed.
Okay everyone.
So I hope this was clear.
This overall case.
Let me just come out of here.
See, this is the new head and we can see how good our linked list is.
Again, let us just try to understand the time complexity of this as well.
Let us do that in VS code where we wrote this particular code.
Okay.
So yeah, if we now try to find out the complexity, what I feel is we have just done some constant
work here.
We are just defining some values in this while loop a while loop.
Sorry.
Again we are creating nodes as per our use cases.
So it's going to run n times.
And now I am just doing some k work only.
Right.
Creating this is some let's say k one Cayman work.
This is some K2 work again.
This is also constant K3 work.
Taking the input is also constant.
Let's say k4.
Okay.
Again, in the terminology which we learned about time complexity in the last module.
So yeah using this, if we just take all of these at big K some say big K work, right?
Everyone I can comfortably say that all the work which I'm doing here, all the work which I'm doing,
is just n k and we have seen this number of times how this complexity is o of n.
Okay, great.
So let me write this as well because it's a good run, a good win from our end.
So using a tail variable.
Or say pointer.
We have.
Successfully.
Reduced.
Time.
Complexity.
From O of N square.
To big O of N.
And that is a very great optimization which we have done, because we have already seen how o n square
is pretty bad, while o n square is workable.
Okay, so greater than everyone.
I hope this is clear.
So in the next video we are going to do another operation on linked list.
Please make sure that you understand this and are able to visualize because as we move forward, all
the operations which we are going to do, that will be a lot easy.
If you are able to visualize how Linked List is going to look like.
And again, I'm going to show you each and every thing by helping you to visualize.
Then we will implement the same.
Okay.
Thank you.