coding with a singly linked list and bubble sort in java

Question

I have a problem with my code, I have made a singly linked list class in which you can add, remove, modify, merge etc... however, I am attempting a simple bubble sort and have come across problems in which the list is not correctly sorted. here are some things to note:

• it is a custom implementation of a linked list
• the nodes of the singly linked list contain 2 things: a CustomerFile object with all the data for a customer and a 'next' node pointer to the next item in the list
• the list is sorted in ascending order (A-Z) by the surname stored in the customer file of each node
• the add record function inserts the nodes at the correct position in the list so that the list does not need to be sorted initially - however if the surname is changed, as part of the program, the list needs to be sorted again
• I would rather not create a new list and re-use this insert record on that list to create a new list as this is memory intensive and my task is to be as efficient as possible
• the very structure of the linked list cannot be changed - it is decided and I am too far to change to something such as an array
• the list has a head node, it has next items but does not have a tail node. It has an appointed NULL next pointer to indicate the end pf the list

the code

public static void sortList()
{
    if (isEmpty() == true)
    {
        System.out.println("Cannot sort - the list is empty");
    }
    else if (getHead().getNext() == null)
    {
        System.out.println("List sorted");
    }
    else
    {
        Node current = getHead().getNext();
        CustomerFile tempDat;
        boolean swapDone = true;
        while (swapDone)
        {
            current = getHead().getNext();
            swapDone = false;
            while (current != null)
            {
                if (current.getNext() != null &&
                    current.getData().getSurname().compareTo(
                        current.getNext().getData().getSurname()) >0)
                {
                    tempDat = current.getData();
                    current.setData(current.getNext().getData());
                    current.getNext().setData(tempDat);
                    swapDone = true;
                }
                current = current.getNext();
            }
        }
        if (getHead().getData().getSurname().compareTo(
            getHead().getNext().getData().getSurname()) >0)
        {
            current = getHead().getNext();
            getHead().setNext(current.getNext());
            setHead(current);
        }
    }
}

I would appreciate the feedback

Answer 1

Your code is an odd mixture, mostly swapping data but treating the head specially trying to swap it with the next by switching the links.

As noted in another answer, this last swap is not correctly implemented, but really there's no reason to treat the head specially if you're doing things by swapping the data.

All you have to do is start each traversal of the list at the head in the outer loop.

This yields a working solution:

public void sortList()
{
    if (isEmpty())
    {
        System.out.println("An empty list is already sorted");
    }
    else if (getHead().getNext() == null)
    {
        System.out.println("A one-element list is already sorted");
    }
    else
    {
        Node current = getHead();
        boolean swapDone = true;
        while (swapDone)
        {
            swapDone = false;
            while (current != null)
            {
                if (current.getNext() != null && current.getData().getSurname().compareTo(current.getNext().getData().getSurname()) >0)
                {
                    CustomerFile tempDat = current.getData();
                    current.setData(current.getNext().getData());
                    current.getNext().setData(tempDat);
                    swapDone = true;
                }
                current = current.getNext();
            }
            current = getHead();
        }
    }
}

I've made this non-static because as noted in comments it wasn't clear to me how yours could work as a static. You may be able to make it static in your context.

I also changed a couple other minor things. It's never necessary to check a condition by code like

if (isEmpty() == true)

In Java, this is entirely equivalent to

if (isEmpty())

And tempDat doesn't need to be declared outside of where it's used.

Answer 2

I think the main issue here is that you start with

current = getHead().getNext()

With this code you will leave the head completely out of the sorting process and it could be the case that the data in here needs to go to the other end of the list, but in this case it will always be either the data in the head element, or be the data directly after the head node (the latter is due to your if statement at the end).

Try starting from the head of the list instead and see what that brings up.

Answer 3

You are not including the head in your sorting.

public static void sortList()
{
    if (isEmpty() == true)
    {
        System.out.println("Cannot sort - the list is empty");
    }
    else if (getHead().getNext() == null)
    {
        System.out.println("List sorted");
    }
    else
    {
        Node current = getHead();
        // Node current = getHead().getNext();
        CustomerFile tempDat;
        boolean swapDone = true;
        while (swapDone)
        {
            current = getHead().getNext();
            swapDone = false;
            while (current != null)
            {
                if (current.getNext() != null && current.getData().getSurname().compareTo(current.getNext().getData().getSurname()) >0)
                {
                    tempDat = current.getData(); // td -> objectA, cd -> objectA
                    current.setData(current.getNext().getData()); // cd -> objectB
                    current.getNext().setData(tempDat); // nd -> td -> objectA
                    swapDone = true;
                }
                current = current.getNext();
            }
        }
        //if (getHead().getData().getSurname().compareTo(getHead().getNext().getData().getSurname()) >0)
        //{
        //  current = getHead().getNext(); // current -> head+1
        //  getHead().setNext(current.getNext()); //head+1 -> head+2
        //  setHead(current); // head -> head+1
        //}
    }
}

Also there is a error in the commented out code above. Applying that code drops a node.

// list: a -> b -> c -> d
current = getHead().getNext(); // current = b
getHead().setNext(current.getNext()); // a -> c 
setHead(current); // head = b
// list: b -> c -> d
// and nothing points to 'a' anymore

Rather then swapping data you should try swapping nodes. If you go about that approach you should find a better solution.