Sorting a sorted LinkedList by name

Question

If the title is not confusing enough maybe this will be. I have a linked list which contains people who have first and last names as well as a few other variables. The list must be sorted by last name first, then by first name. So far I insert the people into the list in alphabetical order by last name. I then try to traverse the list, if two last names are the same, I check the first names and swap. But I have a bug.

Inserted alphabetically into the list by last name, last,first
Acy,Mary
Acy,Clayton
Bob,Lonnie
Toni,Lonnie

After my so call "sort" of first names
Acy,Mary
Bob,Lonnie
Acy,Clayton
Toni,Lonnie

You can see it is sorted by last name. I am trying to sort each same last name by first name. And this is what I get as output from

 public void sortFirstNames(){
     System.out.println("here");
     PeopleNode previous = null;
     PeopleNode current = head; 
     PeopleNode temp;

     if(head == null || head.next == null){
         return;
     }

    while(current != null && current.next != null && current.lastName.compareTo(current.next.lastName) == 0){ //traverse the list 
            if((current.firstName).compareTo(current.next.firstName) > 0){ //see which first name goes first 
                temp = current.next.next;
                current.next.next = temp.next;
                temp.next = current.next;
                current.next = temp;
                current = temp.next;
             }
            current = current.next;
        }
     }

It doesn't change the list at all, I have taken advise of commenters but have yet to make it work. Does anyone have any idea?

Basically I am trying to say while two last names are the same check the first names, then swap them if need be.

Try elaborating about the nature of the bug. On a first read through it looks like you are only swapping the names of the people, not the actual elements of the linked list. If there is data other than names, it will not be swapped. I am not sure though. — irh, May 10 '14 at 02:11
Yeah I accidentally hit enter when entering the tags so it posted before I was finished. I updated it now. — Michael Miner, May 10 '14 at 02:16
I added the [tag:java] tag because this looks like Java. Feel free to replace this with the appropriate language tag if it isn't. — Bernhard Barker, May 10 '14 at 12:17

score 1 · Answer 1 · edited May 23 '17 at 12:13

The heart of your problem lies here:

if(previous.firstName.compareTo(current.firstName) >= 0){
    temp = current;
    current = previous;
    previous = temp;
}

Firstly - >=. That's probably not so much a problem as just unnecessary - there's no need to swap elements that are equal - just make it > instead.

Next, that code doesn't change the linked-list at all. All it does is change the values of the local variables, so previous ends up pointing to the node after current in the actual linked-list, and then, because of the >=, if you have equal values, you'll just continuously process the same two nodes.

This post elaborates a bit on that: Is Java "pass-by-reference" or "pass-by-value"?

What you need to do is compare something.next and something.next.next (no need for 2 separate variables), and then you can swap these, which will change the linked-list.

Sorting a sorted LinkedList by name

1 Answers1