Counting number of nodes between two nodes

This code counts the number of nodes between any given two nodes in a circular linked list. Any feedback is appreciated:

public class CountNodesBetweenTwoNodes {
Node first;
Node fifth;

private class Node<Item> {
Item item;
Node next;
}

public static void main(String[] args) {
CountNodesBetweenTwoNodes countNodes = new CountNodesBetweenTwoNodes();
countNodes.buildCircularList();
int noOfNodes = countNodes.countNodesBetweenTwoNodes(countNodes.getFirst(), countNodes.getFifth());
System.out.println("Number of Nodes is: "+noOfNodes);
}

private Node buildCircularList() {
first = new Node();
first.item = "First";

Node second = new Node();
second.item = "Second";

Node third = new Node();
third.item = "Third";

Node forth = new Node();
forth.item = "Forth";

fifth = new Node();
fifth.item = "Fifth";

first.next = second;
second.next = third;
third.next = forth;
forth.next = fifth;

fifth.next = first;

return first;
}

private int countNodesBetweenTwoNodes(Node firstNode, Node secondNode) {
int count = 0;

while(firstNode.next != secondNode) {
count++;
firstNode = firstNode.next;
}

return count;
}

public Node getFirst() {
return first;
}

public Node getFifth() {
return fifth;
}
}

-
4th should be "fourth" ;) – Mat's Mug Mar 2 '14 at 1:41
yeah! it was quick. :) – Vijay Bhore Mar 2 '14 at 1:55

Focusing directly on the countNodesBetweenTwoNodes

  private int countNodesBetweenTwoNodes(Node firstNode, Node secondNode) {
int count = 0;

while(firstNode.next != secondNode) {
count++;
firstNode = firstNode.next;
}

return count;
}


The method name is way too long... that's an AppleScript name! The arguments in a Java method count as part of the signature, so, your method is really calling it countNodesBetweenTwoNodes Node Node... it is quite sufficient to call it countNodesBetween(Node, Node)...

Then, the parameters are Nodes, so there is no need to call them firstNode and secondNode, first and second would be fine.

Alright, so, now we have the method:

  private int countNodesBetween(Node first, Node second) {
int count = 0;

while(first.next != second) {
count++;
first = first.next;
}

return count;
}


Now, about the real issues, what if first == second? Then the result should be 0, but, in your case, it is size where size is the number of members in the list.

  private int countNodesBetween(Node first, Node second) {
int count = 0;

while(first != second) {
count++;
first = first.next;
}

return count;
}


This changes the value that you are returning though.... but... what was the requirement?

Was the requirement to get the number of steps to go from the first to the second, or the number of in-between nodes you have to visit?

If it was the number of nodes you have to visit, then you have two places where the result is 0, when first == second, and also first.next == second...

In a general sense, I have never encountered a reason why there has to be a full loop-count when the first==second

Finally, what if you are going the long way around? For example, what if someone does this?

countNodesBetween(mynode.next, mynode);
countNodesBetween(mynode, mynode.next);


Shouldn't the answer there be 1 for both situations (unless mynode.next == mynode)?

To my mind, this method should look like:

  private int countNodesBetween(final Node first, final Node second) {
int count = 0;
int size = 0;
Node tmp = first;
while(tmp != second) {
count++;
tmp = tmp.next;
if (tmp == first) {
throw new IllegalArgumentExcption("First and second nodes are not in the same list.");
}
}
if (count <= 1) {
return count;
}
int size = count;
while (tmp != second) {
size++;
tmp = tmp.next;
}
int back = count - size;
return -back < count ? back : count;
}


This code loops all the way around the loop, and it returns the distance between the nodes, where 'between' is defined as 'how many times do you have to move to get from the first to the second.

It returns a negative number if the shortest distance is to go backward through the loop... or, put another way, the number of steps forward from the second node to the first.

If that information is not relevant to you, you can stick with the simpler:

  private int countNodesBetween(final Node first, final Node second) {
int count = 0;
int size = 0;
Node tmp = first;
while(tmp != second) {
count++;
tmp = tmp.next;
if (tmp == first) {
throw new IllegalArgumentExcption("First and second nodes are not in the same list.");
}
}
return count;
}

-

Your program is really based only of case where you have 5 nodes. This make your code really hard to change if you want to have a "list" of node of a different size.

1. The name of the class should represent a concept not an action, CountNodesBetweenTwoNodes could be something like CircularList or something like that. A name that would represent what the class is, not what it does.
2. Personally, I find that re-using the first argument in the loop to iterate over the list is not what I would want. I would use a third Node variable to let to show that I'm iterating and that my firstNode will not change during this method.

private int countNodesBetweenTwoNodes(Node firstNode, Node secondNode) {
int count = 0;

while(firstNode.next != secondNode) {
count++;
firstNode = firstNode.next;
}

return count;
}

3. I would rename the class variable Node fifth for Node last, what if you have more than five nodes ? Would you change your code ? I hope not, so by changing the name to represent that it's the last one, we are good to not limit our-self to five nodes.

4. Since we changed the name of the variable, we should change public Node getFifth() too for public Node getLast().

5. You should always specify a visibility for you class variable. Currently, first and fifth are package visibility, they should be private.

6. There is a bug in your class: you made your countNodesBetweenTwoNodes private. If I want to use your class myself, I could not use this method since I would not be in your class. You don't have this problem since you use the method in your main which is in the class. If you move your main` method to another class, your program is not working anymore.

-