Rank for symbol table

Question

How would I return the number of keys that is less than the given key? I just don't know where to start. I have the base start but other than that I dont know where to begin

public class LinkedListST<Key extends Comparable<Key>, Value> {
    private Node first;      // the linked list of key-value pairs

    // a helper linked list data type
    private class Node {
        private Key key;
        private Value val;
        private Node next;

        public Node(Key key, Value val, Node next)  {
            this.key  = key;
            this.val  = val;
            this.next = next;
        }
    }

public int rank (Key key) {
        if(key == null) return 0;
        //TODO
    }

EDIT: This is what I have so far but my for loop is wrong and is giving me errors

public int rank (Key key) {
    int count = 0;
    for(Node x = first; x != null; x = x.next){
        if(x.next < key){
            count++;
        }
    return count;
    }
}

Answer 1

Pseudo code:

initialize counter to zero
loop over all nodes, starting at first:
   if node's key < key:
       increment count
return count

That should get you started.

---

EDIT

Ok, so you've actually posted a real attempt at writing the code, which is the secret to getting real help on Stack Overflow.

Your code, with proper indentation, ...

public int rank (Key key) {
    int count = 0;
    for(Node x = first; x != null; x = x.next){
        if (x.next < key){
            count++;
        }
        return count;  // <-- Note!
    }
}

... shows a return statement inside the loop. Not exactly what you wanted.

The if (x.next < key) is also giving you grief, because you need to compare Key with Key, not Node with Key.

Finally, the Comparable interface requires the the Key to implement the compareTo(Key other) method. Used like:

key.compareTo(x.key)

This returns a -1, 0, or 1 depending on which is larger or if they are the same. So you really want:

if (key.compareTo(x.key) < 0) {

or

if (key.compareTo(x.key) > 0) {

Exercise left to student.