How should I implement sorting with my custom linked list?

Question

I've been trying to figure out how link lists work but I'm having a hard time visualizing the concept. I know multiple algorithms but I can't figure out how to implement them.

here's my code:

public class LL {
    private ListNode front,last; 

    public LL(){
        front = null; last = null;
    }

    //
    //methods here...
    //

    public class ListNode{
        public double coefficient;
        public int exponent;
        public ListNode next;

        public ListNode(){
            this(0, 0, null);
        }

        public ListNode(double coefficient, int exponent, ListNode next){
            this.coefficient = coefficient; 
            this.exponent = exponent;
            this.next = next;
        }
    } 
}

This is for storing data of Polynomials. I'm trying to get them to go in descending order. And eventually add up the coefficients of nodes with the same exponents.

I think I'm going for bubble sort algorithm but I cannot figure out how I'll rearrange the links. I was also thinking of adding a remove() method and just remove one node and add it at the end until it's sorted. But that is very inefficient because I'll have to keep making new nodes each time.

PS: I also have a Polynomial class that takes in a string and turns it into an LL. I don't think it's necessary to post it but if you need it I'll post it! Thanks!

Answer 1

Sorting linked list is really inefficient, normally you would copy the listing list into an array, sort them and copy them back (this is what the JDK does)

BTW Unless you have really sparse indecies, you are better off using an array or array list. This is not only simpler, more efficient and faster, it is also naturally sorted.

An array will use a fraction of the memory and of a linked list, even if you have quite a few zero coefficients.