Linked List sorting issue

Question

YES, this is a homework project. That being said, I'm looking to learn from my mistakes rather than just have someone do it for me.

My project is a word frequency list - I accept a text file (or website URL) and count the:
- Number of unique words, and
- How many times they appear.

All methods are provided for me except for one: the insert(E word) method, where the argument is a generic type word. The word is stored in a Node (Linked List project) that also has a 'count' value, which is the value representing the number of times the word appears in the text being read.

What this method has to do is the following:

If the argument is already in the list, increment the count of that element. I have done this part
If the argument is not found in the list, append it to the list. I also have done this part.
sort the list by descending count value. i.e. highest -> lowest count 3.5. If two elements have the same count value, they are sorted by the dictionary order of their word.

I am VERY unfamiliar with Linked Lists, so as such I am running into a lot of NullPointerExceptions. This is my current insert method:

public void insert(E word){
    if(word.equals("")){
        return;
    }

    if(first == null){//if list is null (no elements)
        /*Node item = new Node(word);
        first = item;*/
        first = new Node(word);
    }

    else{//first != null

        Node itemToAdd = new Node(word);

        boolean inList = false;

        for(Node x = first; x != null; x=x.next){
            if (x.key.equals(word)){// if word is found in list
                x.count++;//incr
                inList = true;//found in list

                break;//get out of for
            }//end IF
            if(x.next == null && inList == false){//if end of list && not found
                x.next = itemToAdd;//add to end of list
                break;
            }//end IF
        }//end FOR

        //EVERYTHING ABOVE THIS LINE WORKS. 
        if (!isSorted()){
            countSort();
        }

    }//end ELSE
}//end method

My isSorted() method:

public boolean isSorted(){
    for(Node copy = first; copy.next != null; copy = copy.next){
        if (copy.count < copy.next.count){
            return false;
        }
    }
    return true;
}

and last but not least, the part where I'm struggling, the sort method:

public void countSort(){

        for (Node x = first, p = x.next; p != null; x=x.next, p=p.next){
            // x will start at the first Node, P will always be 1 node ahead of X.

            if(x == first && (x.count < p.count)){
                Node oldfirst = first; 
                x.next = p.next;
                first = p;
                first.next = oldfirst;
                break;
            }

            if (x.count < p.count){
                //copy.next == x.
                Node oldfirst = first;
                oldfirst.next = first.next; 
                x.next = p.next;
                first = p;
                first.next = oldfirst;
                break;
            }

            if (x.count == p.count){
                if(x.toString().charAt(0) < p.toString().charAt(0)){
                    //[x]->[p]->[q]

                    Node oldfirst = first;
                    x.next = p.next;
                    first = p;
                    first.next = oldfirst;
                    break;
                }
            }
        }
    }

Here is the output of my insert method when called by the classes/methods given to me:

Elapsed time:0.084
(the,60)
(of,49)
(a,39)
(is,46)
(to,36)
(and,31)
(can,9)
(in,19)
(more,7)
(thing,7)
(violent,3)
(things,3)
(from,9)
(collected,1)
(quotes,1)
(albert,1)
(einstein,2)
(any,2)
(intelligent,1)
(fool,1)
(make,1)
(bigger,1)
(complex,1)
(it,11)
(takes,1)
(touch,1)
(genius,1)
(lot,1)
(courage,1)
(move,1)
(opposite,1)
(direction,1)
(imagination,1)
(important,5)
(than,3)
(knowledge,3)
(gravitation,1)
(not,17)
(responsible,1)
(for,14)
(people,2)
(falling,1)
(love,2)
(i,13)
(want,1)
(know,3)
(god,4)
(s,8)
(thoughts,2)
(rest,2)
(are,11)
(details,2)
(hardest,1)
(world,7)
(understand,3)
(income,1)
(tax,1)
(reality,3)
(merely,1)
(an,7)
(illusion,2)
(albeit,1)
(very,3)
(persistent,2)
(one,12)
(only,7)
(real,1)
(valuable,1)
(intuition,1)
(person,1)
(starts,1)
(live,2)
(when,3)
(he,11)
(outside,1)
(himself,4)
(am,1)
(convinced,1)
(that,14)
(does,5)
(play,2)
(dice,1)
(subtle,1)
(but,8)
(malicious,1)
(weakness,2)
(attitude,1)
(becomes,1)
(character,1)
(never,3)
(think,1)
(future,2)
(comes,1)
(soon,1)
(enough,1)
(eternal,1)
(mystery,1)
(its,4)
(comprehensibility,1)
(sometimes,1)

My initial idea has been to try and loop the if(!isSorted()){ countSort();} part to just repeatedly run until it's sorted, but I seem to run into an infinite loop when doing that. I've tried following my professor's lecture notes, but unfortunately he posted the previous lecture's notes twice so I'm at a loss.

I'm not sure if it's worth mentioning, but they provided me an iterator with methods hasNext() and next() - how can I use this as well? I can't imagine they'd provide it if it were useless.

Where am I going wrong?

@MaxZoom - Professor is making us do it with Linked Lists, as that's the data structure we're currently learning. — csh1579
– csh1579, Commented Jun 21, 2015 at 0:18
comment out the //if (x.count == p.count){..} block for now and try to sort by count first. also try. putting while(!sorted) { } in the insert method. I understood most of it you provided but is it possible if i can see complete implementation of this. — Deepak
– Deepak, Commented Jun 21, 2015 at 0:19

maraca · Accepted Answer · 2015-06-21 18:05:48Z

1

You are close. First the function to compare the items is not complete, so isSorted() could yield wrong results (if the count is the same but the words are in wrong order). This is also used to sort, so it's best to extract a method for the comparison:

// returns a value < 0 if a < b, a value > 0 if a > b and 0 if a == b
public int compare(Node a, Node b) {
    if (a.count == b.count)
        return a.word.compareTo(b.word);
        // case-insensitive: a.word.toLoweCase().compareTo(b.word.toLowerCase())
    } else {
        return a.count - b.count;
    }
}

Or simplified which is enough in your case:

public boolean correctOrder(Node a, Node b) {
    if (a.count > b.count)
       return true;
    else if (a.count < b.count)
       return false;
    else
       return a.word.compareTo(b.word) <= 0;
}

For the sort you seem to have chosen bubble sort, but you are missing the outer part:

boolean change;
do {
   change = false;
   Node oldX = null;
   // your for:
   for (Node x = first; x.next != null; x = x.next) {
       if (!correctOrder(x, x.next)) {
            // swap x and x.next, if oldX == null then x == first
            change = true;
       }
       oldX = x;
   }
} while (change);

We could use the help of Java native library implementation or more efficient sort algorithms, but judging from the exercise the performance of the sort algorithm is of no concern yet, first need to grasp basic concepts.

edited Jun 21, 2015 at 18:05

answered Jun 21, 2015 at 1:19

maraca

9,5873 gold badges27 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

12 Comments

csh1579 Over a year ago

I tried implementing the changes to the sort method (I omitted the part about character sorting since I figured it's probably best to start with getting the count sort right), and was again greeted with an infinite loop. I'm not sure where, but I think somewhere in my code, my references are being messed up. Hopefully it's not 100+ iterations in when I debug it.

maraca Over a year ago

@csh1579 I added a little bit more code to show how I meant it, like this you shouldn't get an endless loop.

csh1579 Over a year ago

Now this is where I run into a problem that's stumped me throughout this project - you say to swap x and p, but how could I swap x and p if I don't know the element that leads to x? Wouldn't the normal process be to: link x.next to p.next, link p.next to x, link (element that points to x) to p?

csh1579 Over a year ago

I see how you're approaching it, but wouldn't we have to check to make sure x.next.next is not null (or am I missing the point here :P)?

maraca Over a year ago

@csh1579 exactly what I thought too first, but usually the check would be x != null, because it will be checked after x = x.next and therefore it is correct like that for bubble sort. oldX == null is the only special case.

|

Kutay Demireren · Accepted Answer · 2015-06-21 09:18:13Z

0

With looking your codes, it sounds like to me that two things can be done:

Firstly, you can make use of Comparable class method. So, I assume you wrote the class Node, thus you may want to inherit from Comparable class. When you inherited from that class, java will automatically provide you the compareTo method, and all you need to do is to specify in that method that "I want to compare according to your counts and I want it to be in ascending order." **Edit(1):By the way, I forgot the mention before but after you impelement your compareTo method, you can use Collections.sort(LinkedList list), and it will be done.

The second solution came to mind is that you can sort your list during the countSort() operation with the technique of adding all to an another list with sorting and after add all them back to the real list. The sorting technique I'm trying to say is, keep going towards to the end of the list until you find a Node in the list that has a count smaller than currently adding Node's counts. Hope that doesn't confuse your head, but by this way you can achieve more clear method and less complicated view. To be clear I want to repeat the procedure:

Look the next
If (next is null), add it //You are at the end.
else{
if (count is smaller than current count), add it there
else, keep moving to the next Node. //while can be used for that.
}

edited Jun 21, 2015 at 9:18

answered Jun 21, 2015 at 1:37

Kutay Demireren

6401 gold badge11 silver badges25 bronze badges

1 Comment

csh1579 Over a year ago

I understand what you're saying for the first solution, but I believe I may have been not clear in the second one. Nodes in the argument all have a count of 1, and Nodes that only appear once (thus far) will also have a value of 1. No node will have a count value smaller than the argument. Additionally, I was applied a ListIterator class - my main class declaration is this: public class Frequency<E extends Comparable> implements Iterable<E> so if I understand this: the E generic extends comparable, while the Frequency implements Iterable.

Collectives™ on Stack Overflow

Linked List sorting issue

2 Answers 2

12 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

12 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related