2

I'm trying to implement a bubble sort for my linked list. I'm using an algorithm I found on this site and made the appropriate methods. However, I get the errors:

Exception in thread "main" java.lang.NullPointerException

at Node.compareTo

at LinkedList.bubbleSort

at LinkedList.main

I'm not sure how to fix this. Any help would be appreciated.

public class LinkedList {                                                                                                                                                                                                                                                                                                                                                                      
    Node first;

    public void add(char c, int index) {
        if(index==0) {
            if(first==null) first = new Node();
            else add(first, first.datum, 1);
            first.datum = c;
        }
        else add(first, c, index);
    }

    public void add(Node n, char c, int index) {
        if(index==1) {
            Node newnode = new Node();
            newnode.datum = c;
            newnode.link = n.link;
            n.link = newnode;
        }
        else add(n.link, c, index-1);
    }

    public void swap(int i1, int i2) {
        char temp = get(i1).datum;
        get(i1).datum = get(i2).datum;
        get(i2).datum = temp;
    }

    public void print() {
        System.out.println(first);
    }

    public Node get(int index) {
        return get(index, first);
    }

    public Node get(int index, Node n) {
        if(index==0) return n;
        return get(index-1, n.link);
    }


    public void set(int index, char c) {
        get(index).datum = c;
    }

    public int length()
    {   
        int counter = 0;
        Node temp = first;
        while(temp!=null) {
            temp = temp.link;
            counter++;
        }
        return counter;
    }

    public void bubbleSort()
    {   
        for (int i = 0; i < length(); i++)
        {   
            for (int j = i; j < length(); j++)
            {   
                if (get(j).compareTo(get(j+1)) > 0)
                {   
                    swap(j, j + 1);
                }
            }
        }
    }

    public static void syso(String s) {
        System.out.println(s);
    }

    public static void main(String[] args) {
        LinkedList ll = new LinkedList();

        ll.add('c', 0);
        ll.add('m', 1);
        ll.add('a', 2);
        ll.add('x', 3);
        ll.add('d', 2);
        ll.print();

        Node n1 = ll.get(1);
        Node n2 = ll.get(2);
        if(n1.compareTo(n2)>0) syso("bigger");
        else if(n1.compareTo(n2)==0) syso("equal");
        else syso("smaller");


        ll.bubbleSort();
        ll.print();
    }

} //end class LinkedList

class Node {
    char datum; 
    Node link = null;

    public String toString() {
        return datum + ":" + link;
    }

    int compareTo(Node n) {
        return datum - n.datum;
    }
}
2
  • 2
    Please check. That Node is pointing to null. Commented Jan 28, 2014 at 22:44
  • if (get(j).compareTo(get(j+1)) > 0) runs the risk of j+1 running off the end of the list. Commented Jan 28, 2014 at 22:45

2 Answers 2

2

Your problem is here.

get(j).compareTo(get(j+1))

When j is the index of the last thing on the list, this is making you compare to null, which throws the exception.

In the loop, instead of comparing j < length(), you need to compare j < length() - 1, so that you avoid the case where j is the last thing on the list.

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

2 Comments

Thanks, I saw that shortly after posting. The only problem is that my final linked list is "c:a:d:m:x:null". The first 'c' doesn't seemed to be affected by the sort.
Yeah, your algorithm is wrong. If you don't swap node 0 and node 1, then you never look at node 0 again. That comparison should involve i somehow, not just j and j+1.
0

You're executing

get(j).compareTo(get(j+1))

where j can go up to length - 1. So, when j is equal to length -1, it tries to get the element at length, and get() returns null in that case. (It should throw an exception instead, by the way, to signal the error).

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.