Hi all,
This is my first post here. I have a homework question so please don't outright give me an answer, but if you have any tips or suggestions, I'd appreciate it. (I am studying Java Data Structures and Algorithms, using a textbook by Thomas Standish).
The assignment is:
"Write a recursive method to find the length of a linked list, where the length is defined to be the number of nodes in the list referenced by the pointer in the firstNode field of the list's header node."
So I should be finding not the number of nodes in the linked list, but the number of nodes referenced by the first node's pointer. I know that Java has a LinkedList class but I've never used it so I created my own node class and am using an ordinary array to store the node objects. I have three nodes, each has a "link" field that points to the next node, except the last, which has a null value for its link field. So therefore the length I am looking for is two, since the first node's link field links to the second node, which links to the third, and the third's link field is null. I want to make that perfectly clear because the length of the linked list is not the same as the length of the array, if I understand the exercise correctly.
My first attempt was just iterative, it was obviously wrong. My teacher commented:
To be recursive, a method has to call itself, either directly or through a chain of calls ... You have to start by figuring out how to DEFINE the length of a list recursively. Think in terms of a (nonrecursive) base case and (recursive) nonbase cases. It flows from the definition, just like factorial and fibonacci flowed from the recursive definitions. The recursive method in this example, computing the length of a list, should be loopless.
I tried again, do you think I am on the right track? My teacher thinks I rush to code without planning, and he's probably right, for short programs, I tend to just rattle them out, because it's so easy to change later. Anyway, any advice or tips, suggested reading, etc. would be appreciated.
Thank you,
Rachel - CS student
import java.util.*;
class MyLinkedList
{
static int length = 0;
static MyNode firstNode = new MyNode(); // node objects
static MyNode secondNode = new MyNode();
static MyNode thirdNode = new MyNode();
static MyNode countNode = new MyNode(); // temporary counter node
static MyNode listOfNodes [] = new MyNode[3]; //array to store node
public static void main (String args[])
{
firstNode.airport = "NYC"; //set node fields
firstNode.link = secondNode;
listOfNodes [0] = firstNode; //add to array
secondNode.airport = "FRISCO";
secondNode.link = thirdNode;
listOfNodes [1] = secondNode;
thirdNode.airport = "VEGAS";
thirdNode.link = null; // tail of list has null pointer;
listOfNodes [2] = thirdNode;
firstNode.getNextNode(firstNode);
System.out.println(length); // print length of list
}
public static class MyNode //inner class represents a node in a linked list
{
String airport;
MyNode link; //links to next node in list
public String toString()
{
return airport + " ";
}
public static void getNextNode(MyNode countNode)
{
if (countNode.link!=null)
{
length++;
countNode = countNode.link;
getNextNode(countNode);
}
}
}
}