Reputation:
I'm very new to Java, and I was given this Linkedlist set-up, I need to use recursion or while loop to write the size function that return the size of the linkedList. I guess I'm very confused as to how to do the size function when this linkedlist setup doesn't initialize Node, head etc.
package list;
public class LinkedList {
public int value;
public LinkedList next;
public LinkedList (int value, LinkedList next) {
this.value = value;
this.next = next;
}
public static LinkedList list () {
return new LinkedList(1, new LinkedList(2, new LinkedList(3, null)));
}
public int size () {
int size = 0;
Node Current = head;
while(Current.next != null)
{
Current = Current.next;
size++;
}
return size;
}
}
Upvotes: 1
Views: 11795
Reputation: 289
public int size()
{
int size = 1;
LinkedList head = this;
while (head.next != null)
{
head = head.next;
size++;
}
return size;
}
Upvotes: 1
Reputation: 7042
Another way of computing size in a linked list like the one you've created is to use recursion. There are only two cases:
1
- just itself1
plus the size of the next.Thus, we have the following function:
public int size(){
if(next == null){
return 1;
} else {
return 1 + next.size();
}
}
This can be written extremely concisely using a ternary operator:
public int size(){
return next != null ? 1 + next.size() : 1;
}
For the iterative solution, there's no need to use the Node
class, as each LinkedList
object represents both itself (one single value) and all of the values to follow (a list of values). From that point of view, we have to loop from "here" until there is nowhere else to go.
public int size () {
int size = 1;
LinkedList Current = this;
while(Current.next != null){
Current = Current.next;
size++;
}
return size;
}
Upvotes: 2
Reputation: 719739
In your current formulation, your LinkedList
instances are actually nodes as well as lists. That's OK, but it means that there is no distinguished "head" of the list ...
In this context, the fix is to change:
Node Current = head;
to
LinkedList current = this;
(And, yes, the size
variable should start as 1
. In this formulation, an empty list is represented by null
. If you are calling size()
on an instance of LinkedList
, then the size of the list must be at least 1.)
@Konrad states "A list itself should encapsulate the nodes."
Actually that is a design choice. If you are following OO design principles then it should. However, there are situations where pragmatically you don't want to do that. Sometimes it is necessary to "sacrifice" abstraction to get better performance or reduce memory utilization.
Upvotes: 3
Reputation: 355
Change it like:
public int size () {
int size = 0;
// set the head as current note
Node current = head;
// while a current node is set
while(current != null)
{
// increment site
size++;
// and set the next as current node
current = current.next;
}
return size;
}
The list itself is not a list. It's a linked list of nodes. A list itself should encapsulate the nodes.
Upvotes: 0