Skip to Main Content

Java Programming

Announcement

For appeals, questions and feedback about Oracle Forums, please email oracle-forums-moderators_us@oracle.com. Technical questions should be asked in the appropriate category. Thank you!

recursive method to count length of linked list (homework question)

807606Apr 11 2007 — edited Apr 18 2007
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);
               }
          }
     }
}
Comments
Locked Post
New comments cannot be posted to this locked post.
Post Details
Locked on May 16 2007
Added on Apr 11 2007
15 comments
4,988 views