Hello all and welcome back.
So in this video let us move forward.
And now let's try to find the length of our linked list.
Length of linked list.
Now again the understanding is same.
We will be just given the head right.
So we have this particular sample as a test.
It is having five nodes.
What I should do I should define a function.
So let's say def length.
And it should just get my head and it should return me what the length is.
Right.
So it should return let's say length okay.
So now let's talk about what the logic will be.
I feel the logic can be very much same to the one where we printed our linked list.
That is, we started from the head and we are moving to each node until our temporary variable becomes
none, because when it is becoming known, that implies that nothing is thereafter, right?
So when it was finally equal to none, there was nothing after that particular node.
And if I just maintain a count variable as well along with that and keep on adding one to my count,
I should be able to get my length right.
So the overall idea is pretty simple.
We are just going to move to each and every node until we reach to the last node and have my temporary
temp variable as none.
Great.
So let us try to code this everyone.
Then let's say yeah def length okay and length of linked list.
Let me make it like this.
And I will be getting a head now as a good habit.
Of course we should make temp variable okay.
And one answer as well.
So let's say answer is zero initially now while okay.
So as of now I have just defined temp and head temp and answer while my temp is not equals none.
Right?
What I should do, I should just move temp to the next one.
Okay.
So again this is something which we have already seen.
Temp initially is head.
So let me just write temp as well.
Temp initially is head temp dot.
Next it's going to move here.
Then it's going to move here.
Then it is going to move here.
Finally it will become equal to this right.
Once it becomes equal to this then I think we should stop.
And then when it becomes equal to none and return the answer.
So now let us code the same.
When we are moving, we also have to make sure that answer we are adding by one.
Okay so this is just shorthand tool.
Let me maybe write it like this.
Only it should be fine.
Okay.
If we do this, then let me just return the answer in the end.
And I think we should be good, right?
Great.
So to test the code, of course, we will have to create a linked list.
or just one thing.
What I'm going to do is I'm going to copy all these things.
So all these functions which we have made into a new file, which we can say comments.
The reason for that is instead of copying them every time, I hope all of you are aware of this particular
way.
So I can make a comment.py file.
In this file I'm just printing or pasting all these functions right?
The reason for that is I want to use them right instead of copying them again and again in the same
this particular folder in each and every file.
What I can do, let me just directly import them.
So again from comments common import node and get or take input better and let's say print as well okay.
So this is a common way we do that everyone.
We are just keeping all the functions and the classes structure everything into a file from where I
can import that.
Right?
So instead of copying them every time, I will just paste any function which I want to use in this particular
directory inside this for this file.
Right.
So we have done this already.
I am pretty sure you must have seen the same when I was also taught.
So if not just you can use this particular way to import your functions.
Great!
Now what I can do, let's say head of L is equals to take input better, I can just call this.
Once I get my head, I can just print or let me just get.
Length is equals to length of L.
I'm just passing my head of L, right head of linked list.
And let me just print the length right.
So this is just going to print whatever the length is.
Now let us run this and see how it's going to happen.
So yeah okay.
Let me just bring this terminal maybe to this side.
So it is a little bit nicely visible.
Okay, so let's try this.
Oh, it should be fine.
It is asking us for the value.
So let me enter ten first, then 20, then 30.
Okay.
And after that let me enter 40, 50 and minus one.
Okay.
So once I do this then I have five nodes in my list right.
If I now press enter we are able to get five as an answer.
Okay.
So yeah pretty sure this should be easily understandable, but let us still do the dry run of this once
in the Python tutor so that we are able to visualize the same as well.
Okay, so let me just edit this code and I'm just gonna paste everything here.
Okay.
Common will not be here.
These functions are already present.
Great.
So yeah let us run this now.
If we move forward.
Now everyone again lots of these function and structure going to get defined okay.
Head of linked list.
It's going to take the input okay.
This is going to take lots of steps.
So let us just quickly run and make the linked list.
So I'm just defining the linked list.
We have already seen that okay.
Last 30.
And say 40.
And in the end just putting minus one.
Right.
So we have seen this steps a lot of time.
It is just defining my linked list.
Now once I'm out of this, once I'm out what I'm going to do the head is returned.
So you can see the head of linked list.
This is the whole head.
It is having four nodes starting from head all the way to tail.
Next is none.
We just have this head right.
So let me call the length function.
Now once I call this length of linked list function we are creating a temp which is equals to head and
answer which is equals to zero.
Now temp going to get created.
It's pointing to head.
We are just going to move okay.
And in these questions always make sure that you are handling the edge cases or the cases.
For example let's say when head is null right.
So we have to see this loop will not run and the answer will be zero.
So always make sure that these kind of cases where just zero nodes are there or a single node is there,
these type of cases are handled.
Okay.
Now let's go and run this.
So temp.
So see temp is here as of now it's going to move to the next one.
And I'm going to add one to my answer.
Okay.
Again the same thing is going to happen.
Temp is going to move to the next one.
And I'm going to add one to my answer just like this.
Of course we can just run it.
And finally when temp is at this particular case answer two.
Let me make it three.
Okay.
And as of now temp has reached to this last node.
So just run on this temple became none.
But before becoming sorry, after it becomes none, we have to still increase the answer, right?
It is inside.
And after this answer is going to get for now, we will come out of this loop.
Once I come out of this loop, I can just return the answer.
Return value for answer.
The length is four and of course I can print that.
Okay everyone.
So great!
I hope you are able to visualize using this thing exactly what is happening.
Okay, now let's go back to the code and I would like to you all to do one more thing.
So now let's also write a function length of linked list.
But this time it recursive.
So I don't want to use iteration I want to use recursion okay.
So let us go back and see how we can do that as well.
Okay everyone I'm going to teach you for this particular code.
And in future we are going to write code in iteration as well as in recursion.
Okay, great.
So linked list length.
Using recursion.
Okay.
So let me just copy this whole list again.
I want to explain you what the exact process is.
Okay.
So process is very important to understand.
It so let's just copy this.
Yeah.
Cool.
So we got our linked list here.
Everyone know exactly what we have to do.
Pay attention again.
Just let's think of recursion the way we have understood it.
There were three steps in recursion.
First used to be the base case.
Second, used to be recursive call.
Something which we used to assume don't need to question this third artwork.
Right now.
Again, if you think about this, if you are able to just do these three steps, then we can say that
recursion is going to work for us because that is how we have understood recursion, right?
Now let's think about each one by one.
First is base case.
I believe that base case can be equals to when head is none.
I can just return zero, right?
When my head is none, I can say that it's a base case because it's an empty list, right?
What are you going to find out in the empty list?
The list length is going to be zero.
Great.
Now let's see on the recursive call.
So if you remember, I told you in the starting that how my linked list is a linear data structure,
just like an array or list.
Right.
So we have seen how we used to do recursion on arrays or list.
We used to divide them.
Right.
Either by indexes or in half or just we used to keep the first element or the last element.
So the understanding is exactly the same here.
Now what I'm going to do.
Pay attention everyone.
What I'm going to do is I'm going to just ask recursion to find answer for this right part.
Because if we think on this, this is also a separate linked list, right?
So I am just reducing the problem.
I am just reducing the problem in half.
So we can ask recursion.
We can ask recursion.
To get length.
Of head dot next.
Just like when we were dividing or breaking our array by working on the first element, the rest was
also an array.
Similarly, in this case, this whole left over list is also a linked list, right?
Recursion.
Or rather, we also don't care if this is being saved somewhere.
This is right.
As of now, we don't care for the new recursion call.
This is going to be the head for my recursion, right?
So if recursion is going to get the as the answer, if recursion will be able to get the answer which
we know it will, the last work is ours, which is we just have to do one plus recursion.
Answer okay, so let me write this in that pin so that you are understanding it.
Recursion answer.
Right.
So the color coding so that you are able to remember this.
Yeah I think that the whole thing which we have to do again I will repeat it first is the base case
when my head is none okay.
When the list is empty I just have to return zero because that's an empty list with a length of zero
for the recursive call, just like we were dividing our array here, you have to just understand one
thing we can of course only work on the head and we can give the rest.
Left over.
Linked list.
Right.
We can give this leftover linked list, which is again a smaller linked list.
That's how we used to do recursion, right?
Take our problem the same problem into smaller problem.
So finding the length of this list is a smaller problem for me, right?
Once I get the answer for this, then I know that I have one node to work on, and for that one node
we can just say one plus whatever the answer I'm getting.
Okay, so let us just run this everyone.
Uh, yeah.
So let us code this.
If my head equals to none, then I can just return zero.
So this we can say is the base case.
Okay, great.
Then let's move forward.
Let's say recursion answer.
It's going to be length of my linked list into head dot next.
Now recursion is going to get the answer.
We don't have to question how exactly the answer is going to come, right?
And if this is done, I can just say one plus whatever answer recursion has got.
Okay, cool.
So let us just do one thing.
Maybe just call this length again, but this time call this function okay.
So again of course you can do the dry run for this particular case.
I hope it is a lot clearer.
What's going to happen is that if we see the run recursion call is going to get made for this, then
call is going to get made for this, then this, then this, and finally call is going to get made for
this null.
Because for this particular last ten node head dot next is none, right?
It is going to return the answer.
Let me just draw that as well.
It is going to return the answer as zero.
Okay.
We are going to add one.
We are going to add one and just say that one is the answer.
Similarly here two will get written here, three will get written here we will have four which is returning.
And finally I can just add one and say one plus four.
This is my answer, right everyone?
So I hope the overall idea of how recursion flow will be there is clear.
So if that's clear then just let us code that.
Yeah.
Just we have to check this right.
Great.
So again let me run this.
So let us clear this.
Yeah.
First node ten.
Second node 23rd node 34th 4050 and minus one.
And we seem to get the same answer from both.
Okay.
So I hope yeah our code is working fabulously well.
And I hope you are able to understand the same as well.
Now again, I took some time and help you visualize this because moving forward, many operations we
will be doing iteratively as well as recursion using recursion as well.
So we should be aware that how we can use linked list and recursion.
Okay, so cool everyone.
Now let's meet in the next video where we are going to do some operations on our linked list.
Thank you.