1

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

除了添加“实现可比”之外，我不知道从哪里开始。在那之后，我完全不知道下一步该做什么。

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

2 回答 2

1

通常，您希望您的列表实现 Collection 接口，并且列表中的项目实现 Comparable（这涉及以您添加到列表的任何类型实现 compareTo()）。您可以通过要求列表元素类型实现 Comparable 来强类型化。一个捷径可能是扩展另一个 Collection 类型，例如 LinkedList，并使用反向列表增强它。

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

于 2012-10-09T06:30:56.430 回答
0

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

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

无论如何，请注意列表的根元素的身份。

于 2012-10-09T06:01:07.623 回答