RefList help

[David Goins]

Hey all i am trying to figure out how to get this RefList working for me...

Implement a method countValue() that counts the number of times an item occurs in a linked list.

int countValue(RefList f, int item);

Generate 20 random numbers in the range of 0 to 4, and insert each number at the front of a linked list. Output the list by using a method which you would call writeLinkedList which you would add to the RefList.java (in page 414-421) program. In a loop, call the method countValue() , and display the number of occurrences of each value from 0 to 4 in the list.

So far this is what i have:

public class PREX6
{
       public static void main(String[] args)
       {
          RefList refl1= new RefList();
          int intRandomNum = 0;
          int count = 0;
 
          while (count != 21)
          {
                intRandomNum = (int)(Math.random() * 5);
                refl1.add(intRandomNum);
                count++;
          }
 
          System.out.println(refl1);
      }
}

But there's an error for the "refl1.add(intRandomNum);" since the RefList class does not have a "add" property. How am i supposed to add to a list that has no command to add?

Here is the RefList code:

public class RefList
{
  protected int numElements;          // number of elements in this list
  protected LLObjectNode currentPos;  // current position for iteration
 
  // set by find method
  protected boolean found;         // true if element found, else false
  protected LLObjectNode location; // node containing element, if found
  protected LLObjectNode previous; // node preceeding location
 
  protected LLObjectNode list;     // first node on the list
 
  public RefList()
  {
    numElements = 0;
    list = null;
    currentPos = null;
  }
protected void find(Object target)
  // Searches list for an occurence of an element e such that
  // e.equals(target). If successful, sets instance variables
  // found to true, location to node containing e, and previous
  // to the node that links to location. If not successful, sets 
  // found to false.
  {
    boolean moreToSearch;
    location = list;
    found = false;
 
    moreToSearch = (location != null);
    while (moreToSearch && !found) 
    {
      if (location.getInfo().equals(target))  // if they match
       found = true;
      else
      {
        previous = location;
        location = location.getLink();
        moreToSearch = (location != null);
      }
    }
  }
public int size()
  // Returns the number of elements on this list. 
  {
    return numElements;
  }
 
  public boolean contains (Object element)
  // Returns true if this list contains an element e such that 
  // e.equals(element); otherwise, returns false.
  {
    find(element);
    return found;
  }
public boolean remove (Object element)
  // Removes an element e from this list such that e.equals(element)
  // and returns true; if no such element exists, returns false.
  {
    find(element);
    if (found)
    {
      if (list == location)     
        list = list.getLink();    // remove first node
      else
        previous.setLink(location.getLink());  // remove node at location
 
      numElements--;
    }
    return found;
  }
 
  public Object get(Object element)
  // Returns an element e from this list such that e.equals(element);
  // if no such element exists, returns null.
  {
    find(element);    
    if (found)
      return location.getInfo();
    else
      return null;
  }
public String toString()
  // Returns a nicely formatted string that represents this list.
  {
    LLObjectNode currNode = list;
    String listString = "List:\n";
    while (currNode != null)
    {
      listString = listString + "  " + currNode.getInfo() + "\n";
      currNode = currNode.getLink();
    }
    return listString;
  }  
 
  public void reset()
  // Initializes current position for an iteration through this list,
  // to the first element on this list.
  {
    currentPos  = list;
  }
public Object getNext()
  // Preconditions: The list is not empty
  //                The list has been reset
  //                The list has not been modified since most recent reset
  //
  // Returns the element at the current position on this list.
  // If the current position is the last element, then it advances the value 
  // of the current position to the first element; otherwise, it advances
  // the value of the current position to the next element.
  {
    Object next = currentPos.getInfo();
    if (currentPos.getLink() == null)
      currentPos = list;
    else
      currentPos = currentPos.getLink();
    return next;
  }
}

Thanks!
David

[Campbell Ritchie]

Were you given that linked list class, and which book are you using ("page 414-421")?

Probably easier to use a java.util.Random object, and its nextInt(5) method, than Math.random().

You will have to write an add method, which inserts the new Object at the very beginning of the list, and maybe overload it to add at a particular location: public boolean add(Object obj) and public boolean add(int index, Object obj). You could use void return type if you prefer.

[David Goins]

Hey Ritchie: Yes that's the class on the page that we have to use with this assignment. In the chapter it has nothing about the "add" statement in order to get stuff into the list so i'm up a creak without a paddle per say. Is there a site that has the "add" method for the RefList? Seems redundant not having that in the class in the first place....

And I'm really not getting the "int countValue(RefList f, int item);"... Nowhere in that does it have the "size()" command found in the RefList that could be used to get how many items are in the list without having to do all that???

David

[David Goins]

How about this?

public void add(Object element)
  // Adds element to this list.
  {
    if (numElements == list.length)
    list[numElements] = element;
    numElements++;
  }

David

[Campbell Ritchie]

Thanks for the suggestion, but the list was supposed to be a linked list, hence the LL in the class name, so an array won't help, I am afraid.

[David Goins]

This doesnt seem to work either...

public void add(Object element)
  // Adds element to this list.
  {
    list = element;
  }

David

[Campbell Ritchie]

Actually the way I first saw a linked list described was the self-referential classes; each LinkedNode object has a reference to another LinkedNode object (usually called next; there may be another called previous too). That way you can run back and forth along the list with recursive calls.

[David Goins]

Then Ritchie would i use:

public void add(Object element)
  // Adds element to this list.
  {
    LLObjectNode currNode = list;
    list = element;
  }

David

[Campbell Ritchie]

Still not convinced.
You need a root class, the way I saw it done.

public class LLRoot<E>
{
   private LLNode<E> topNode;
 
   public LLRoot<E>()
   {
      topNode = null;
   }
 
   public LLRoot<E>(E e)
   {
      topNode = new LLNode<E>(e);
   }
 
   public void add(E e)
   {
      topNode = new LLNode<E>(e, topNode);
   }
 
   public E remove(E e)
   {
      E removed;
      if(e == null && topNode.getElement() == null || e != null && e.equals(topNode.getElement()))
      {
         removed = e;
         topNode = topNode.getNext();
      }
      else
      {
         removed = topNode.remove(e);
      }
      return removed;
   }
 
   public int getSize()
   {
      return LLNode.getSize();
   }
 
/*
 * etc etc
 */
}

public class LLNode<E>
{
   private static int size = 0;
   private E element;
   private LLNode<E> next;
 
   public LLNode<E>(E e, LLNode<E> nextNode)
   {
       element = e;
       next = nextNode;
       size++;
   }
   
   public LLNode<E>(E e)
   {
       this(e, null);
   }
 
   public LLNode<E> getNext()
   {
       return next;
   }
 
   public E getElement()
   {
       return element;
   }
 
   public boolean contains(E e)
   {
       return (element == null ? e == null : element.equals(e)) ||
              (next != null && next.contains(e));
   }
 
   /**
    * Actually removes the next element
    */
   public E remove(E e)
   {
       E removedElement = null;
       if (next != null) // If we have got a null, there can't be any more elements
       {
          if (e == null && element == null) // Therefore element == e
          {
             removeNextNode(); // removedElement is already null
          }
          else if (element != null && element.equals(e))
          {
              removedElement = e;
              removeNextNode();
          }
          else
          {
              removedElement = next.remove(e);
          }
       }
       return removedElement;
   }
 
   private void removeNextNode()
   {
       next = (next == null ? null : next.next);
       size--;
   }
 
   public static int getSize()
   {
       return size;
   }
/*
 * etc etc
 */
}

This is a singly-linked list, so your remove method actually removes the next node. See how it does it, passing the command onto the next node until it reaches the end of the list or finds the element to remove. If you reach the end of the list before removing the element, it will simply return null. If you have two elements which return true from equals, it returns the parameter, so you could use an == operator on the returned value.

The removeNextNode() method reassigns "next" to the next from the next, unless there is already a null. You need the null tests because there is guaranteed to be a null value somewhere at the end of the list.

[edit]Change removed = topNode.getElement(); to removed = e; in LLRoot to match LLNode[/edit]
[ October 23, 2008: Message edited by: Campbell Ritchie ]

[David Goins]

Ritchie:

This may help you and me more.. its some "hints" for getting this flowing:

* Declare an unsortedlinkedlist unlist.
* use a for loop in which you will do the following 20 times:
1. create a random number between 0 and 4
2. insert the number into the unlist
* print the elements in unlist.
* call the countValue method 5 times where each time you will send 2 parameters:
1. the unlist
2. the value of an int that is 0,1,2,3,4
* write the countValue method which accomplishes the followings:
1. it has 2 parameters:
o the unlist
o an int i
2. declare an int counter a.
3. make a list element out of the element i, say f2.
4. declare a for loop that will run 20 times in which you will do the following:
o get the first element from the unlist, say f1.
o make sure you compare f1 to f2.
o if they are equal increment the counter a.
5. return a.
6. done

I dont see a "LLNode<E>" in any class'es this program uses.... Is that the section i need to add to RefList.java? I really dont see anything in the chapter that has anything close to explaining what "LLNode<E>" does...

David

[Campbell Ritchie]

It might not help you; in fact I made sure to avoid writing methods directly affecting your assignment. But it shows how you can write a (singly-)linked list which runs recursively, and how you need a "root" to gain access to it.

You should be able to get at the topNode, and from that gain access to the other nodes in order (you can't simply get at node 3 in a linked list; you can only get it from node 2 or maybe node 4). You can then go through the list and look for the values you want and count them.

But sorry if I have posted something which doesn't help.

[David Goins]

Ok how close (or far) am i with this:

public void add(Object element)
  // Adds element to this list.
  {
    //LLObjectNode currNode = list;
    //list = element;
 
    LLObjectNode temp = new LLObjectNode(element);
    LLObjectNode current = head;
 
    // starting at the head node, crawl to the end of the list
    while(current.getNext() != null)
    {
       current = current.getNext();
    }
    // the last node's "next" reference set to our new node
    current.setNext(temp);
    listCount++;// increment the number of elements variable
  }

David

[Campbell Ritchie]

Just at a quick look, there are a few things, but all minor ( ).

You can get away without the temp local variable
. . . current.setNext(new LLNode(obj));

Consider whether to put the counting in the LLNode class.

Consider whether to keep a reference to the end node as a field. That will make it much quicker to reach the end of the list when you are adding, but you have to update it if you remove the end node.

But just on a 3-second look, it will all work as you expect.

[David Goins]

Thanks for the reply again Ritchie:

However this is the errors i get when i compile it:

javac -Xlint:none  -d . -g -classpath . RefList.java
 
RefList.java:149: cannot find symbol
 
symbol  : class LLNode
 
location: class RefList
 
    while(current.setNext(new LLNode(obj)) != null)
 
                              ^
 
RefList.java:149: cannot find symbol
 
symbol  : variable obj
 
location: class RefList
 
    while(current.setNext(new LLNode(obj)) != null)
 
                                     ^
 
RefList.java:149: cannot find symbol
 
symbol  : variable current
 
location: class RefList
 
    while(current.setNext(new LLNode(obj)) != null)
 
          ^
 
RefList.java:151: cannot find symbol
 
symbol  : class LLNode
 
location: class RefList
 
       current.setNext(new LLNode(obj));
 
                           ^
 
RefList.java:151: cannot find symbol
 
symbol  : variable obj
 
location: class RefList
 
       current.setNext(new LLNode(obj));
 
                                  ^
 
RefList.java:151: cannot find symbol
 
symbol  : variable current
 
location: class RefList
 
       current.setNext(new LLNode(obj));
 
       ^
 
RefList.java:154: cannot find symbol
 
symbol  : variable current
 
location: class RefList
 
    current.setNext(temp);
 
    ^
 
7 errors

And here is the updated code:

public void add(Object element)
  // Adds element to this list.
  {
    //LLObjectNode currNode = list;
    //list = element;
 
    LLObjectNode temp = new LLObjectNode(element);
 
    // starting at the head node, crawl to the end of the list
    while(current.setNext(new LLNode(obj)) != null)
    {
       current.setNext(new LLNode(obj));
    }
    // the last node's "next" reference set to our new node
    current.setNext(temp);
  }

David

[David Goins]

Ok worked on it some more and i talked with my teacher... heres what i got now:

import java.util.Random;
import java.lang.Integer;
 
public class PREX6
{
  public static void main(String[] args)
  {
    int temp;
    Integer item;
    Random random_numbers = new Random();
 
    //Generate a List of 20 random integers from 1-4
    RefUnsortedList myList = new RefUnsortedList();
 
    for (int i = 0; i < 20; i++)
    {
      temp = random_numbers.nextInt(5);
      item = new Integer(temp);
      myList.add(item);
    }
 
    //Now print the list
    myList.reset();
    
    //Now count and output values for 0-4
    for (int i=0;i<=4; i++)
    {
      temp = countValue(myList, i);
      System.out.println(i + ": " + temp);
    }
  }
 
  public static int countValue(RefUnsortedList f, int v)
  /**Count the number of instalnces of value v in a LinkedList of
  Integers f **/
  {
    int theReturn;
    int theList = f;
    int theValue = v;
 
    for (int a = 0; a < 20; a++)
    {
      if (theList == theValue)
      {
        return (theValue);
      }
    }
  }
}

So now im on the:

write the countValue method which accomplishes the followings:

1. it has 2 parameters:
* the unlist
* an int v
2. declare an int counter a.
3. declare a for loop that will run 20 times in which you will do the following:
* get the first element from the unlist, say f1.
* make sure you compare f1 to v.
* if they are equal increment the counter a.
4. return a.
5. done

However, this is the errors i get

javac -Xlint:none  -d . -g -classpath . PREX6_2.java
 
PREX6_2.java:38: incompatible types
 
found   : RefUnsortedList
 
required: int
 
    int theList = f;
 
                  ^
 
.\RefUnsortedList.java:11: RefUnsortedList is not abstract and does not override abstract method add(java.lang.Object) in ListInterface
 
public class RefUnsortedList extends RefList implements UnsortedListInterface
 
       ^
 
.\RefUnsortedList.java:19: add(java.lang.Object) in RefUnsortedList cannot implement add(java.lang.Object) in ListInterface; attempting to use incompatible return type
 
found   : void
 
required: boolean
 
  public void add(Object element)
 
              ^
 
.\UnsortedListInterface.java:11: add(java.lang.Object) in UnsortedListInterface clashes with add(java.lang.Object) in ListInterface; attempting to use incompatible return type
 
found   : void
 
required: boolean
 
  void add(Object element);
 
       ^
 
4 errors

I need some help getting the RefUnsortedList value from "f"...

David

[Campbell Ritchie]

It's while (current getNext() != null) . . ., not set.
Some of those errors are because you wrote LLObjectNode and I wrote LLNode. The compiler objects to the different spelling.

You need to compare your two interfaces, which have methods with the same signature but different return types; they both have to return the same thing.

Your count method has several unnecessary local variables and doesn't actually count. I shall be surprised if you can even compile it in its present form.
What you need to do is to start at the head node, see whether its value is the same as "v" then go to the next node. Count as you go, then return the count.
And you can't simply use the == operator to compare nodes and values.
Probably worth having a currentNode local variable to help find the next node.
And if I had been teaching I would have told you to count the occurrences of "v" in the whole list, rather than counting 20 nodes.

[David Goins]

Ok, re-worked:

import java.util.Random;
import java.lang.Integer;
 
public class PREX6_2
{
  public static void main(String[] args)
  {
    int temp;
    Integer item;
    Random random_numbers = new Random();
    RefUnsortedList myList = new RefUnsortedList();
 
    //Generate a List of 20 random integers from 1-4
    for (int i=0; i<20;i++)
    {
      temp = random_numbers.nextInt(5);
      item = new Integer(temp);
      myList.add(item);
    }
 
    //Now print the list
    myList.reset();
    
    //Now count and output values for 0-4
    for (int i=0;i<=4; i++)
    {
      temp = countValue(myList, i);
      System.out.println(i + ": " + temp);
    }
  }
 
  // Count the number of instalnces of value v in a LinkedList of Integers f
  public static int countValue(RefUnsortedList f, int v)
  {
    int theList = 0;
    int theValue = v;
    int theCount = 0;
 
    // Count from 0 to 20
    for (int a = 0; a < 20; a++)
    {
      // Save current node in theList
      theList = f.getNext().toString();
 
      // Compaire the node to the current passed static value
      if (theList == theValue)
      {
        // add to theCount if it equals
        theCount++;
      }
    }
    // Return theCounts' count back to function
    return (theCount);
  }
}

However i am still getting an error:

javac -Xlint:none  -d . -g -classpath . PREX6_2.java
 
PREX6_2.java:43: incompatible types
 
found   : java.lang.Object
 
required: int
 
      theList = f.getNext();
 
                         ^
 
.\RefUnsortedList.java:11: RefUnsortedList is not abstract and does not override abstract method add(java.lang.Object) in ListInterface
 
public class RefUnsortedList extends RefList implements UnsortedListInterface
 
       ^
 
.\RefUnsortedList.java:19: add(java.lang.Object) in RefUnsortedList cannot implement add(java.lang.Object) in ListInterface; attempting to use incompatible return type
 
found   : void
 
required: boolean
 
  public void add(Object element)
 
              ^
 
.\UnsortedListInterface.java:11: add(java.lang.Object) in UnsortedListInterface clashes with add(java.lang.Object) in ListInterface; attempting to use incompatible return type
 
found   : void
 
required: boolean
 
  void add(Object element);
 
       ^
 
4 errors

I'm not getting why it has an error on the "theList = f.getNext();" when both are defined as integers... What am i doing wrong there?

David

[Campbell Ritchie]

You haven't parameterised the List, have you?
In which case what the List contains is Object instances, and the JVM has no way of knowing what they are when they come out.
There are two ways of sorting it out, one good and complicated, the other cheap and cheerful and simple and unreliable.
See following posts.

[Campbell Ritchie]

Good and complicated and reliable way to sort it out. You can put -Xlint on as much as you like, and the compiler won't find anything to complain about, but you will probably use the cheap and cheerful method because this way to do it is complicated.
This will work in Java5 and later, not in Java1.4.2 or earlier.

Parameterise the list.
Every method in the LLObjectNode class which takes an Object as its Parameter takes an E. That's right, an E. Short for element.
Every method in the LLObjectNode class which returns an Object as its return type returns an E.
The type of class is changed; it is no longer LLObjectNode, but LLOBjectNode<E>.
Every time you quote the LLObjectNode class you have to quote it as LLObjectNode<Something>, and you add the same <Something> to any constructor calls.

What that means is the compiler will only allow you to put one particular kind of Object in, and only get one kind of Object (the same kind) out. If you declare the formal type parameter as <Integer>, then you can only put Integers in, and only get Integers out.
This is a brief introduction to generics, which ought to have been in the language from day 1 and was introduced 8 years too late in September 2004 (Java 5).

So how do you get an Integer into an int? Another feature introduced in Java5 was boxing (also called auto-boxing because it is done automatically). What it means is you can present an int to something which is an Integer and the compiler will fiddle it so it works. It works the other way round, too, so you can have an Integer and put it into an int variable, only that is called unboxing.

So, parameterising the entire class and then using it with <Integer> will sort that problem out.

[Campbell Ritchie]

Cheap and cheerful solution, which is what we had to do before Java5, but risks type-un-safety.

When you try putting an int into something which is supposed to be an Object, the compiler will try. The nearest it can find is Integer, so it will try that; an Integer is in fact an Object, so it puts an Integer into your list. You already know all about that; it is called boxing.
Now, when you try to get it out, it is still an Integer, but the compiler doesn't know that; your method returns Object, so the compiler only knows it is an Object.

If you are sure you are only putting ints/Integers into your list, you try casting them back when they are retrieved. Put a cast to (Integer) where you are retrieving the values from the list, and the compiler will un-box the value back to the int.

You will get all sorts of complaints from the compiler, particularly if you are using -Xlint, but it will actually compile and run, as long as you haven't let anything which isn't an Integer into your list.
If you have got something else . . . [Try it and see what happens.]

The other errors mean you need to have an add method which is in the interface. Also the two add methods in the two interfaces need to have the same return type.

[David Goins]

OK Ritchie i finally solved that prob. but i still have 3 errors that i dont know how to correct. It seems one is asking for a void while the other is returning a Boolean?

javac -Xlint:none  -d . -g -classpath . PREX6_2.java
 
.\RefUnsortedList.java:11: RefUnsortedList is not abstract and does not override abstract method add(java.lang.Object) in ListInterface
 
public class RefUnsortedList extends RefList implements UnsortedListInterface
 
       ^
 
.\RefUnsortedList.java:19: add(java.lang.Object) in RefUnsortedList cannot implement add(java.lang.Object) in ListInterface; attempting to use incompatible return type
 
found   : void
 
required: boolean
 
  public void add(Object element)
 
              ^
 
.\UnsortedListInterface.java:11: add(java.lang.Object) in UnsortedListInterface clashes with add(java.lang.Object) in ListInterface; attempting to use incompatible return type
 
found   : void
 
required: boolean
 
  void add(Object element);
 
       ^
 
3 errors

And heres the code the errors refer too:

public class RefUnsortedList extends RefList implements UnsortedListInterface
{
 
  public RefUnsortedList()
  {
    super();
  }
 
  public void add(Object element)
  // Adds element to this list.
  {
    LLObjectNode newNode = new LLObjectNode(element);
    newNode.setLink(list);
    list = newNode;
    numElements++;
  }
}

public interface UnsortedListInterface extends ListInterface
{
  void add(Object element);
  // Adds element to this list.
}

public interface ListInterface
{
  int size();
  // Returns the number of elements on this list.
 
  boolean contains (Object element);
  // Returns true if this list contains an element e such that 
  // e.equals(element); otherwise, returns false.
    
  boolean remove (Object element);
  // Removes an element e from this list such that e.equals(element)
  // and returns true; if no such element exists, returns false. 
  
  Object get(Object element);
  // Returns an element e from this list such that e.equals(element);
  // if no such element exists, returns null.
  
  String toString();
  // Returns a nicely formatted string that represents this list.
  
  void reset();
  // Initializes current position for an iteration through this list,
  // to the first element on this list.
 
  Object getNext();
  public boolean add(Object obj);
  // Preconditions: The list is not empty
  //                The list has been reset
  //                The list has not been modified since the most recent reset
  //
  // Returns the element at the current position on this list.
  // If the current position is the last element, then it advances the value 
  // of the current position to the first element; otherwise, it advances
  // the value of the current position to the next element.
}

import java.util.Random;
import java.lang.Integer;
 
public class PREX6_2
{
  public static void main(String[] args)
  {
    int temp;
    Integer item;
    Random random_numbers = new Random();
    RefUnsortedList myList = new RefUnsortedList();
 
    //Generate a List of 20 random integers from 1-4
    for (int i=0; i<20;i++)
    {
      temp = random_numbers.nextInt(5);
      item = new Integer(temp);
      myList.add(item);
    }
 
    //Now print the list
    myList.reset();
    
    //Now count and output values for 0-4
    for (int i=0;i<=4; i++)
    {
      temp = countValue(myList, i);
      System.out.println(i + ": " + temp);
    }
  }
 
  // Count the number of instalnces of value v in a LinkedList of Integers f
  public static int countValue(RefUnsortedList f, int v)
  {
    int theList = 0;
    int theCount = 0;
 
    // Count from 0 to 20
    for (int a = 0; a < 20; a++)
    {
      // Save current node in theList
      theList = (Integer)f.getNext();
 
      // Compaire the node to the current passed static value
      if (theList == v)
      {
        // add to theCount if it equals
        theCount++;
      }
    }
    // Return theCounts' count back to function
    return (theCount);
  }
}

David
[ October 27, 2008: Message edited by: David Goins ]

[David Goins]

Well from the code the "add" only adds whatever is placed into the list and does not need anything returned from that. So i figure the return would be void... But that's just with me guessing and looking at what the code "should" be doing.

I set them all to void and it compiled... it seems to be working now..

David

[Campbell Ritchie]

Is it returning a boolean or a Boolean? They are different, remember.
An add method with a void return type looks OK to me. Well done getting it to compile and work .