How to sort linked list without collections, java

Question

Given a comperator which compares objects of some type T, How can I sort my linked list based on this comparison?

Here's the code for the class Link of my linked list:

public class Link<T> {
    private T data;
    private Link<T> next;
    public Link(T data, Link<T> next){
        this.data = data;
        this.next = next;
    }
    public Link(T data){
        this(data, null);
    }
    public T getData(){
        return data;
    }
    public Link<T> getNext(){
        return next; 
    }
    public void setNext(Link<T> next){
        this.next = next;
    }
    public T setData(T data){
        T tmp = this.data;
        this.data = data; 
        return tmp;
    }
    public boolean equals(Object other) {  
        if(!(other instanceof Link<?>))
            return false;
        T otherData = ((Link<T>) other).data;
        return data.equals(otherData);
    }
    
    public String toString(){
        return data.toString();
    }

And here is the class of the LinkedList:

import java.util.Iterator;

public class LinkedList<T> implements List<T> {
    private Link<T> first;
    private Link<T> last;

    public LinkedList(){
        first = null;
        last = null;
    }

    public void sortBy(Comparator<T> comp){
        // Thats what Im trying to fill
        
    
    }
    

    public String toString() {
        String output = "[";
        for (Link<T> curr = first; curr!=null; curr=curr.getNext()) 
            output = output+curr.toString() + ", ";
        output = output+"]";
            
    return output;
            
    }
    

    public boolean equals(Object other) {  
        if (!(other instanceof LinkedList<?>))
            return false;
        LinkedList<T> otherList = (LinkedList<T>) other;
        if (size()!= otherList.size())
            return false;
        
        Iterator<T> IterA = iterator();
        Iterator<T> IterB = otherList.iterator();
        
        while (IterA.hasNext()) {
            if (!(IterA.next()).equals(IterB.next()))
                return false;   
        }
            
        return true;
        }
    
    public void add(int index, T element) {
        rangeCheck(index);
        nullCheck(element);
        if(index == 0) {
            first = new Link<T>(element, first) ;
            if(last == null)
                last = first ;
        } else {
            Link<T> prev = null ;
            Link<T> curr = first ;
            for(int i=0; i<index; i=i+1) {
                prev = curr ;
                curr = curr.getNext() ;
            }
            Link<T> toAdd = new Link<T>(element, curr);
            prev.setNext(toAdd);
            if(index == size())
                last = toAdd;
        }
    }

    public void add(T element) {
        nullCheck(element);
        if(isEmpty()){
            first = new Link<T>(element);
            last = first;
        }
        else {
            Link<T> newLast = new Link<T>(element);
            last.setNext(newLast);
            last = newLast;
        }
    }

    @Override
    public int size() {
        int counter = 0;
        for (Link<T> curr=first; curr!=null; curr=curr.getNext())
            counter++;
        return counter;
    }

    @Override
    public boolean contains(T element) {
        for (Link<T> curr = first; curr!=null; curr=curr.getNext() )
            if ((curr.getData()).equals(element))
                return true;
        return false;
    }

    @Override
    public boolean isEmpty() {
        if (first == null)
            return true;
        return false;
    }

    @Override
    public T get(int index) {
        rangeCheck(index);
        Link<T> curr = first;
        for (int i=index; i>0; i=i-1)
            curr=curr.getNext();
        return curr.getData();
    }

    @Override
    public T set(int index, T element) {
        rangeCheck(index);
        Link<T> curr = first;
        for (int i=index; i>0; i=i-1)
            curr=curr.getNext();
        T tmp = curr.getData();
        curr.setData(element);
        return tmp;
        
    }

    @Override
    public Iterator<T> iterator() {
        return new LinkedListIterator<T>(first);
        
    }

    // throws an exception if the given index is not in range
    private void rangeCheck(int index) {
        if(index < 0 || index >= size())
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
    }
    
    // throws an exception if the given element is null
    private void nullCheck(Object element){
        if (element == null)
            throw new NullPointerException();
    }

}

Is there efficient way to sort the linked list without Collections, and using only the methods in the class LinkedList ? (without creating new arrays or new Links)

What I tried to do is using while and for loops with the functions "get(int index)" and "set(int index)"

But Im looking for more efficient way.

Thanks in advance.

Answer 1

It's a tad ridiculous to talk about 'efficiency' for such an incredibly inefficient data storage mechanism. Note that linked lists are far less efficient than basic analysis of algorithmic complexity (O(n) analysis) suggests. Things nearby in memory are faster because CPUs can't operate on memory directly, they only operate on entire pages in cache. If a page isn't in cache, it needs to be fetched, and that takes 500 or more cycles - and none of this is covered by algorithmic complexity.

With those little tracker objects (Those Link objects), there's way more 'traffic' going on and more cache misses. Hence - if you want efficiency, just use ArrayList, or ArrayDeque, or any of many other data types that are more suitable to the job (the point is more or less: For just about every job imaginable, LinkedList is not the best answer. There is no one solution that beats LinkedList for all imaginable situations, but LinkedList is nevertheless effectively never the right answer).

To get to your question: Well, if you still care about efficiency, I suggest you read the Quicksort wikipedia page.

It doesn't just explain this algorithm, it also has some useful pictures to show how it works. Quicksort is algorithmically perfect (It's O(nlogn), and we have 'proof' that sorting a list cannot be any faster than that). There are a few takes on this that can be faster in practice, but that's a few bridges too far if you haven't even learned Collections yet, so let's try not to go overboard.

If you want to phone this homework in, you could consider searching the web for quicksort singly linked list java - but you wouldn't learn very much if you did that :P