CODEWITHSUNDEEP
javadebugginglinked-list
Daniel Soutar
Daniel Soutar

Reputation: 886

Attempting to sort a linked list

I am already aware of various answers to this question. But I have a very confusing bug in my code. The following is a series of println() calls to see if the list I created is correctly sorted.

ListNode list_b = new ListNode(3, new ListNode(-2));
System.out.println("Checking the string conversion: " +
sut.convertToString(list_b));    //output is 3,-2, as expected. Expected result of sorting is -2,3.

System.out.println("Now checking the 
string conversion of the sorted list: " +
sut.convertToString(sut.sort(list_b, int_comparator))); //output is -2,3 as expected.

System.out.println("Now this is list_b following the sorting,
by calling the element and next directly: " 
+ list_b.element + "," + list_b.next);      //3,null. How the hell did that happen!?!??!!?

The convertToString method is as follows:

public String convertToString(ListNode head) {
    if (head != null) {
        String representation = "";
        if (!head.element.equals(null))
            representation += head.element.toString();
        ListNode next = null;
        if (head.next != null)
            next = head.next;
        if (next != null && !next.element.equals(null))
            representation += "," + next.element.toString();
        while (next != null) {
            if (next.next != null) {
                next = next.next;
                if (!next.element.equals(null))
                    representation += "," + next.element.toString();
            }
            else
                break;
        }
        return representation;
    }
    else
        return "";
}

And the actual sort method is still a work in progress, albeit fairly simple:

public ListNode sort(ListNode head, Comparator comparator) {
    if (head != null) {
        ListNode next = null;
        if (head.next != null)
            next = head.next;
        else
            return head;
        if (comparator.compare(head.element, next.element) > 0) {
            head.next = next.next;
            next.next = head;
            head = next;
        }
        return head;
    }
    return null;
}

Would anyone care to explain how I've managed to do the seemingly impossible? I'm speechless at how this could happen! Many thanks to anyone who can explain!

EDIT: thank you to those for your answers and suggestions. I should clarify that the following tests are then performed on the list:

assertTrue(sut.deepEquals(list_a, sut.sort(list_a, int_comparator)));
assertFalse(sut.deepEquals(list_b, sut.sort(list_b, int_comparator)));

assertTrue(sut.deepEquals(new ListNode(-2, new ListNode(3)), sut.sort(list_b, int_comparator)));
assertTrue(sut.deepEquals(new ListNode(-14, new ListNode(-2, new ListNode(3))), sut.sort(list_c, int_comparator)));

Clearly, this implies that any updating of list_b (i.e. list_b = sut.sort(list_b)) is unnecessary. What I'm asking is how you would change the sort method itself so that updating is unnecessary.

Upvotes: 0

Views: 73

Answers (3)

JB Nizet
JB Nizet

Reputation: 691715

list_b references the node containing 3, and having the node 2 as next element.

Then you sort the list. That changes the node containing 3: its next node is now null, since it becomes the last element of the list. It also changes the node 2, which now has the node 3 as next element. But list_b continues to be a reference to the node containing 3.

When you print the node list_b, you thus get 3, null as a result.

EDIT:

to answer your last question:

how you would change the sort method itself so that updating is unnecessary

You should have an actual LinkedList class (exactly as the standard java.util.LinkedList class). The class you have doesn't represent a list. It represents a node inside a chain of nodes.

The LinkedList class would have a reference to the head node, and would contain all the methods needed to iterate through the values stored in the list, transform it to a String, sort it, etc. Of course, sorting the list would imply changing the reference to the head node inside the LinkedList object. But that would be transparent to the user of the LinkedList class, which would never manipulated nodes directly.

Of course, if you start caring so much about having a proper LinkedList class, you should simply use the standard one, which is standard, documented, and tested.

Upvotes: 0

Seelenvirtuose
Seelenvirtuose

Reputation: 20618

Well ... you are changing the internals of the passed node inside your sort method. The variable list_b is still referring to the node "3" that after sorting does not have a successor anymore.

Your sort method is returning the new head of the sorted list. But you do not use that afterwards!

Change your code snippet to:

list_b = sut.sort(list_b, int_comparator);
System.out.println(sut.convertToString(list_b));

Upvotes: 1

user4668606
user4668606

Reputation:

Pretty simple: you sort the list in this piece of code:

sut.convertToString(sut.sort(list_b, int_comparator)))

The list is transformed this way:

3 -> -2 -> null  ====> -2 -> 3 -> null
^                            ^
|                            |
list_b                       list_b

sut.sort returns the new front (head) of the list, which should be the new list_b, but since you don't update the value, it points to the second node in the list, thus producing "3 , null"

Upvotes: 1

Related Questions