CODEWITHSUNDEEP
javasortinglinked-list
robert
robert

Reputation: 249

Sorting a Linked List without re-linking nodes

I already know how to sort a linked list, however my method is a little different than most of my classmates. Instead of re-linking the nodes I just use something like a mutator or a setter method to sort the elements and placed the element on its proper position

Here is an example:

for(Node<E> x = head.next; x != null; x = x.next) {
    E temp = x.element;
    Node<E> y = x.previous;
    Node<E> p = y.next;
    for(; y != null && y.element.compareTo(temp) > 0; y = y.previous) {
        p = y;
        y.next.setElement(y.element);                
    }
    p.setElement(temp);
}

This works correctly.

Now my question is, am I cheating if I do something like this instead of the complicated re-linking of nodes, and is this a bad practice for sorting a linked list?

Upvotes: 0

Views: 441

Answers (4)

Kelly Bundy
Kelly Bundy

Reputation: 27629

I don't think it's bad practice. It's even what Java's own List.sort does, too, except it goes even further and sorts the elements outside the list, in an array:

obtains an array containing all elements in this list, sorts the array, and iterates over this list resetting each element from the corresponding position in the array

Code (from OpenJDK, didn't find Oracle's online):

    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

Upvotes: 1

shakhawat
shakhawat

Reputation: 2727

There is nothing cheating about your approach. It's completely dependent on what you need. If you don't need to swap references, the approach you implemented is simpler and there shouldn't be any other concern.

But say your node is a more complex object. Copying over content may not look good from a readability perspective. Or, your use case requires swap references then it's better to rearrange nodes for readability and only option when you need the references to be swapped.

Upvotes: 2

Joop Eggen
Joop Eggen

Reputation: 109593

In fact this is the solution for the interview question "sort a linked list without changing any next field." However it is a kind of cheating, using the simplest means, as it does not show any capability to handle pointers. With pointers you either change the head or a next field. As long as Nodes are not exposed to the public (which would be a bad idea anyway), your version works.

You can make your future programming efforts considerably easier, by getting hands.on experience with pointers now (as it still is easy).

Info:

You walk for i in 0 .. N, for j in i+1 .. N which is of complexity in the order of O(N²) - quadratic. 3 times the elements, 9 times slower.

For arrays one could get O(N log N) which is considerably faster.

Upvotes: 1

H.S.
H.S.

Reputation: 12679

Sorting Algorithm: [emphasis added]

In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order.

An element of a linked list is a node which comprise of data and reference (link) to the next node in the list.

In the way you are sorting the linked list, you are only moving/placing the data part of an element of the linked list to its proper position but the reference part is still the referring to same next node. When you print the list after sorting, you will get the output in sorted order but actually you have only moved the data part and not the whole elements of the list which, I believe, is not the appropriate way of sorting the linked list.

Consider an example:
A doubly linked list with ele as a member of class which hold int type data and previous and next are the members which hold previous and next node reference. Node class will be something like this:

class Node{  
    int ele;  
    Node previous;
    Node next;
    ....
    ....
}

Now you have wrote the code to place the element ele value to a proper place while sorting.

Assume you need to add some more information to the node of your linked list:

class Node{
    int element;
    char char_ele;    // newly added member
    string str_ele;   // newly added member
    Node previous;
    Node next;
    ....
    ....
}

Now with this change, you have to make changes in your sorting code to place the char_ele and str_ele at proper place along with ele while sorting. But if you implement a proper linked list sorting in which the nodes are relinked based on the sorting condition, you dont need to make any changes to your implementation irrespective of changes in the data part of node.

Upvotes: 2

Related Questions