Bubble Sort in Double Linked List - Null Pointer Error

Question

protected void sortHorseList(int iHorseCount)
{
    int i = 0;
    Horsie currentNode = head;
    Horsie auxNode = new Horsie();
    boolean foundChange = true;
    while(foundChange)
    {
        foundChange = false;
        for(i=0; i<iHorseCount-1; i++)
        {
            if (currentNode.getHorseValue() > currentNode.getNext().getHorseValue())
            {
                auxNode.setHorseValue(currentNode.getHorseValue());
                currentNode.setHorseValue(currentNode.getNext().getHorseValue());
                currentNode.getNext().setHorseValue(auxNode.getHorseValue());
                foundChange = true;
            }
            currentNode = currentNode.getNext();
        }
    }
}

This code displays a null pointer error when running the main program. I am a novice at data structure, and I'm hoping to solve this problem with your help guys! Please teach me how to use bubble sort in a doubly linked list...HEEELP!

Homework? Nobody sorts linked lists, and nobody uses bubble sort outside academe. — user207421
– user207421, Commented Apr 14, 2013 at 10:17

tvanfosson · Accepted Answer · 2013-04-13 17:42:43Z

1

When you get to the end of the list, you aren't checking to see if a next element exists. Thus when you attempt to access it's value, you get the null reference exception. Your inner loop should look something like

   Horsie currentNode = head;
   Horsie nextNode = currentNode != null ? currentNode.getNext() : null;
   while (currentNode != null && nextNode != null)
    {
        if (currentNode.getHorseValue() > nextNode.getHorseValue())
        {
            currentNode = Swap(head,currentNode,nextNode);
            foundChange = true;
        }
        else
        {
            currentNode = nextNode;
        }
        nextNode = currentNode.getNext();
    }

Where Swap(Horsie current, Horsie next) exchanges the place of current and next in the list and, optionally, updates the head if current was the head node.

I'll also note that you do want to swap the nodes in the list rather than swap the values between nodes unless you are sure that your list holds the only references to the node objects. If you don't you run the risk of having an object held by some other class unexpectedly mutate because you've changed its value during the sort.

answered Apr 13, 2013 at 17:42

tvanfosson

534k102 gold badges703 silver badges801 bronze badges

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

3 Comments

Vincent Sy Over a year ago

Can you please help me with the Swap method? How can I start the method?

tvanfosson Over a year ago

@VincentSy - you just need to fix up the (forward) pointers so that current's parent points to next, next points to current, and current points to next's previous follower. Similarly with the back pointers. You will also need to handle the special cases where current is the head element as well as when next is the tail.

Vincent Sy Over a year ago

How can I do it? Can you give me the codes for it? (BEGINNER) :\

Collectives™ on Stack Overflow

Bubble Sort in Double Linked List - Null Pointer Error

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related