Java:向自我实现的双向链表添加一个排序函数

Question

我正在尝试在此代码中实现一个排序函数，以创建一个双向链表。

除了添加"实现可比"之外，我不知道从哪里开始。在那之后，我简直不知道下一步该怎么做。

public class MyLinkedList<AnyType> implements Comparable<AnyType>, Iterable<AnyType>
{
    private int theSize;
    private Node<AnyType> beginMarker;
    private Node<AnyType> endMarker;
    public MyLinkedList( )
    {
        clear( );
    }
    private static class Node<AnyType>
    {
        public Node( AnyType d, Node<AnyType> p, Node<AnyType> n )
        {
            data = d; prev = p; next = n;
        }
        public AnyType data;
        public Node<AnyType>   prev;
        public Node<AnyType>   next;
    }
    public void clear( )
    {
        beginMarker = new Node<AnyType>( null, null, null );
        endMarker = new Node<AnyType>( null, beginMarker, null );
        beginMarker.next = endMarker;
        theSize = 0;
    }
    public int size( )
    {
        return theSize;
    }
    public boolean isEmpty( )
    {
        return size( ) == 0;
    }
    public boolean add( AnyType x )
    {
        add( size( ), x );   
        return true;         
    }
    public void add( int idx, AnyType x )
    {
        addBefore( getNode( idx, 0, size( ) ), x );
    }
    private void addBefore( Node<AnyType> p, AnyType x )
    {
        Node<AnyType> newNode = new Node<AnyType>( x, p.prev, p );
        newNode.prev.next = newNode;
        p.prev = newNode;         
        theSize++;
    }   
    public AnyType get( int idx )
    {
        return getNode( idx ).data;
    }
    public AnyType set( int idx, AnyType newVal )
    {
        Node<AnyType> p = getNode( idx );
        AnyType oldVal = p.data;
        p.data = newVal;   
        return oldVal;
    }

    private Node<AnyType> getNode( int idx )
    {
        return getNode( idx, 0, size( ) - 1 );
    }
    private Node<AnyType> getNode( int idx, int lower, int upper )
    {
        Node<AnyType> p;
        if( idx < lower || idx > upper )
            throw new IndexOutOfBoundsException( "getNode index: " + idx + "; size: " + size( ) );
        if( idx < size( ) / 2 )
        {
            p = beginMarker.next;
            for( int i = 0; i < idx; i++ )
                p = p.next;            
        }
        else
        {
            p = endMarker;
            for( int i = size( ); i > idx; i-- )
                p = p.prev;
        } 
        return p;
    }
    public AnyType remove( int idx )
    {
        return remove( getNode( idx ) );
    }
    private AnyType remove( Node<AnyType> p )
    {
        p.next.prev = p.prev;
        p.prev.next = p.next;
        theSize--;
        return p.data;
    }
    public String toString( )
    {
        StringBuilder sb = new StringBuilder( "[ " );
        for( AnyType x : this )
            sb.append( x + " " );
        sb.append( "]" );
        return new String( sb );
    }
    public java.util.Iterator<AnyType> iterator( )
    {
        return new LinkedListIterator( );
    }
    private class LinkedListIterator implements java.util.Iterator<AnyType>
    {
        private Node<AnyType> current = beginMarker.next;
        private boolean okToRemove = false;
        public boolean hasNext( )
        {
            return current != endMarker;
        }
        public AnyType next( )
        {
            if( !hasNext( ) )
                throw new java.util.NoSuchElementException( ); 
            AnyType nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }
        public void remove( )
        {
            if( !okToRemove )
                throw new IllegalStateException( );
            MyLinkedList.this.remove( current.prev );
            okToRemove = false;       
        }
    }
    public int compareTo(AnyType other) 
    {
        return this.compareTo(other);
    }

Answer 1

通常，您希望列表实现集合接口，并且列表中的项实现可比较（这涉及实现添加到列表中的任何类型的 compareTo（） ）。您可以通过要求列表元素类型实现 Comparable 来强类型化此内容。捷径可能是扩展另一种集合类型（如 LinkedList），并使用反向列表对其进行增强。

不过，作为一般规则，如果寻找其他人的双链表实现。也许试试谷歌的番石榴图书馆？- http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained

Answer 2

链表是关于排序的最糟糕的数据结构。 一个简单的方法（这可能被视为作弊）是将列表映射到一个数组中，对数组进行排序，然后重建列表。

如果你必须实现整个排序算法（对于你的类？），那么每个算法都有一个基本的排序原语，通常是您必须实现的"交换"。

在任何情况下，请注意列表根元素的标识。