1

二重リンクリストを作成するこのコードにソート機能を実装しようとしています。

「implements Comparable」を追加する以外にどこから始めればよいかわかりません。その後、私は次に何をすべきか途方に暮れています。

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 を実装することを要求することで、これを厳密に型指定できます。LinkedList などの別の Collection タイプを拡張し、逆のリストでそれを強化するのが近道かもしれません。

ただし、一般的なルールとして、他の誰かの二重連結リストの実装を探している場合。Google の Guava ライブラリを試してみませんか？- http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained

于 2012-10-09T06:30:56.430 に答える