This function calculates the length of a singly linked list recursively.
tail
is an instance variable that points to the next object in the list.
public int length() {
if (tail == null) {
return 1;
}
return 1 tail.length();
}
However it uses no parameters as shown. I'm struggling to understand the logic behind this code, could I get some help with understanding what's actually going on here?
My first point of confusion is when the function reaches the last object in the list, that objects tail will be null, so why does the function not just end up returning 1?
And secondly, what does 1 tail.length()
actually do?
The most I understand is that 1
and tail.length()
can be added due to the length
function having a return type of int.
CodePudding user response:
Let's assume you have a list like [a, b, c, d]
and you're calling length()
on it. this
will initially be the first element a
and tail
will be the next element b
. So the flow of the code should be something like this:
this.length() // Element 'a'
Is tail == null? // No, tail is 'b'
return 1 <result of length() of 'b'>
|
| this.length() // Element 'b'
| Is tail == null? // No, tail is 'c'
| return 1 <result of length() of 'c'>
| |
| | this.length() // Element 'c'
| | Is tail == null? // No, tail is 'd'
| | return 1 <result of length() of 'd'>
| | |
| | | this.length() // Element 'd'
| | | Is tail == null? // Yes, there's no element after 'd' so return 1
| | | return 1 // return 1 from length() of 'd'
| | |
| | return 1 1 // return 2 from length() of 'c'
| |
| return 1 2 // return 3 from length() of 'b'
|
return 1 3 // return 4 from length() of 'a'
So in the end, length()
will give you the correct result of 4
CodePudding user response:
There is always 1 parameter to a member function ... the object you called the function on (represented by this
in the function.
When you call
return 1 tail.length();
The function length
will have a this
that refers to the tail
here. The tail
in that function is tail.tail
CodePudding user response:
when the function reaches the last object in the list, that objects tail will be null, so why does the function not just end up returning 1?
It does -- when called on the last object in the list.
what does 1 tail.length() actually do.
It calls length
on the tail
object. When you say this has "no parameters," you're not quite right -- the parameter is which object it's being called on. So if you call node.length()
where node.tail == tail1
and tail1.tail == null
, then node.length()
is 1 tail1.length()
is 1 1
is 2, for a total length of 2 -- which is what we'd expect.