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

Is this method really static, and with no argument? How do you get the list you're sorting? — Don Roby
– Don Roby, Commented Dec 21, 2012 at 22:26
its within the singly linked list class itself along with the other methods used by the list - the getHead() method allows you to retrieve the head of the list and you then it works from there — Lukeg101
– Lukeg101, Commented Dec 21, 2012 at 22:35
In what way is your list not sorted? 14358 -> 14358? 14358 -> 13485? 14358 -> 81345? — Rylander
– Rylander, Commented Dec 21, 2012 at 23:06
old list "jay Gatsby, Bob Marley, John Smith, Ziggy stardust" change jay gatsby surname to "Turner" new list "Bob Marley, Jay Turner, John Smith, Ziggy Stardust" it only loops once and does reallocates one node — Lukeg101
– Lukeg101, Commented Dec 21, 2012 at 23:18
It is not case sensitive as the surnames are stored as capitals — Lukeg101
– Lukeg101, Commented Dec 21, 2012 at 23:21

Don Roby · Accepted Answer · 2012-12-22 15:33:56Z

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.

dbriggs · Accepted Answer · 2012-12-21 23:30:23Z

1

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.

answered Dec 21, 2012 at 23:30

dbriggs

351 silver badge8 bronze badges

Comments

Rylander · Accepted Answer · 2012-12-21 23:33:16Z

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.

Collectives™ on Stack Overflow

coding with a singly linked list and bubble sort in java

the code

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

the code

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related