如何在没有集合的情况下对链表排序，java

Question

给定一个比较某些类型T的对象的比较器，如何根据此比较对链表进行排序？

下面是我的链接列表的类链接的代码：

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();
    }

下面是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();
    }

}

有没有有效的方法可以在不使用集合的情况下对链表进行排序，并且只使用LinkedList类中的方法？（无需创建新阵列或新链接）

我尝试使用while和for循环以及函数“get（int index）”和“set（int index）”

但我正在寻找更有效的方法。

提前感谢。

Answer 1

对于如此低效的数据存储机制来说，谈论“效率”有点荒谬。请注意，链表的效率远低于算法复杂性的基本分析（O（n）分析）所暗示的效率。内存中附近的东西更快，因为CPU不能直接对内存进行操作，它们只能对缓存中的整个页面进行操作。如果一个页面不在缓存中，则需要获取它，这需要500个或更多周期——而这些都不包括在算法复杂性中。

有了这些小跟踪器对象（那些链接对象），就会有更多的“流量”和更多的缓存未命中。因此，如果您想提高效率，只需使用ArrayList或ArrayDesk，或其他任何更适合该工作的数据类型（重点是：对于几乎所有可以想象的工作，LinkedList都不是最佳答案。对于所有可以想象的情况，没有一种解决方案可以击败LinkedList，但LinkedList实际上永远都不是正确的答案）。

为了回答你的问题：好吧，如果你仍然关心效率，我建议你阅读快速排序维基百科页面。

它不仅解释了这个算法，还提供了一些有用的图片来展示它是如何工作的。Quick排序在算法上是完美的（它是O（nlogn），我们有“证据”证明对列表进行排序不会比这更快）。在实践中，有一些方法可以更快，但如果您还没有学习集合，那就太远了，所以让我们尽量不要走得太远。

如果你想打电话给这个家庭作业，你可以考虑在网上搜索quicksort Single-linked list java，但如果你这样做了，你就不会学到很多东西：P