Java: Adding a sorting function to self-implemented doubly-linked list

Question

I am trying to implement a sorting function into this code which creates a doubly-linked list.

I don't know where to start other than adding "implements Comparable". After that, I'm simply at a loss for what to do next.

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

related: http://stackoverflow.com/questions/2938495/sorting-a-doubly-linked-list-with-merge-sort?rq=1 — , Oct 09 '12 at 05:31
In the built in libraries, Java copies the elements into an array, sorts them and copies them back. This is faster than trying to sort the elements in the list. — Peter Lawrey, Oct 09 '12 at 05:44
Cory, I added the last compareTo method. I don't know where to go from here. — Haque1, Oct 09 '12 at 05:46

score 1 · Accepted Answer · answered Oct 09 '12 at 06:30

Usually you would want your list to implement the Collection interface and the items in the list to implement Comparable (which involves implementing compareTo() in any type you add to the list). You could strongly type this by requiring that list element types implement Comparable. A short cut may be to extend another Collection type such as LinkedList, and enhance it with the reverse list.

As a general rule though, if have a look for someone else's doubly linked list implementation. Maybe try Google's Guava library? - http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained

score 0 · Answer 2 · answered Oct 09 '12 at 06:01

A linked list is about the worst possible data structure to sort. One easy approach (which may be seen as a cheat) is to map the list into an array, sort the array, then reconstruct the list.

If you must implement the whole sort algorithm (for your class?) then each one has a basic sorting primitive, usually "exchange" which you have to implement.

In any case, watch out for the identity of the root element of the list.

Java: Adding a sorting function to self-implemented doubly-linked list

2 Answers2