Selection sort with LinkedList in Java

I would like to implement selection sort using LinkedList in Java.

I know how to do it with ArrayList, please don’t comment that I should use it instead. I am interested in demonstrating the advantages (fast insertion and removal) and disadvantages of linked lists compared to arrays.

I know how to do this in C where I have pointers and access to the list’s node struct. But in Java the closest thing I found is the ListIterator.

Here is my code that compiles and works:

class Pile {
    private final List< Card > cards;

    public void sortWithSelectionSortUsingLinkedList( final Comparator< Card > comparator ) {
        final List< Card > list = new LinkedList< Card >( cards );
        cards.clear();
        
        for( final ListIterator< Card > it = list.listIterator(); it.hasNext(); ) {
            final int currentIndex = it.nextIndex();
            final Card currentCard = it.next();
            int indexToMoveToCurrent = currentIndex;
            Card cardToMoveToCurrent = currentCard;
            for( final ListIterator< Card > jt = list.listIterator( it.nextIndex() ); jt.hasNext(); ) { // Problem A
                int indexPossiblyLower = jt.nextIndex();
                Card cardPossiblyLower = jt.next();
                if( comparator.compare( cardPossiblyLower, cardToMoveToCurrent ) < 0 ) {
                    cardToMoveToCurrent = cardPossiblyLower;
                    indexToMoveToCurrent = indexPossiblyLower;
                }
            }
            it.set( cardToMoveToCurrent );
            list.set( indexToMoveToCurrent, currentCard ); // Problem B
            // The below swapping code causes ConcurrentModificationException // Problem C
            // it.previous();
            // it.add( list.remove( indexToMoveToCurrent ) );
        }
        
        cards.addAll( list );
    }
}

My problems are the following:

A) To iterate from 1 beyond the position of the outer iterator (it), I have to call listIterator with and index. I suspect that this method walks from the beginning of the list to the given position. This is wasteful because we already have an iterator to an element before. How can I efficiently iterate from a given iterator until the end of the list?

B) To swap elements, I have to use list.set with and index which causes the same inefficiency as A).

C) I planned to swap the elements by modifying the list nodes, not just their value. As I understand my current code leads to the middle of the below diagram, while I wanted to get to the bottom part:

In the current algorithm this may make no difference but I would like to examine other sorting algorithms, and this LinkedList does not work as I expected.

A one-on-one swapping is not the same as removing an element and inserting it before another. Example: abcdefgh is the original, swapping b and f leads to afcdebgh, while removing and inserting f before b would result in afbcdegh. I thought LinkedLists can perform the latter efficiently. If I can use them only like Arrays, then why do LinkedLists exist at all?

Answer

I am interested in demonstrating the advantages (fast insertion and removal) and disadvantages of linked lists compared to arrays.

Congratulations!! You have succeeded in showing the disadvantages of java’s particular implementation of LinkedLists. They suck, don’t use them – their performance is worse than big-O notation suggests (modern CPU architecture and linked lists just don’t like each other), and actually trying to use the advantages is impossible without bending over backwards and using ListIterator. However, ListIterator’s API is not sufficient to do stuff like swapping elements, because you don’t get direct access to the tracker nodes (the nodes containing the prev, next, and value fields).

then why do LinkedLists exist at all?

They probably shouldn’t exist in the first place. “Why do they?” is tantamount to asking: “What was the core java dev team thinking somewhere in the 90s, when this stuff was written?”

We can guess.

• It feels logical to write. Some things make perfect sense until you think about it very carefully and then it doesn’t. Someone simply failed to truly think it through.
• LinkedList as a concept is very well known, and every fundamental informatics chapter about lists and how to implement them mentions them in the same breath as array-style lists.
• The ‘cost’ of arraylist growth is amortized – usually it costs 0, but every so often the backing array is ‘full’ and the ArrayList impl needs to make an entirely new array, copy all elements over. So, amortized – cheap, but it comes in ‘bursts’. Every so often an arraylist.add() call takes a ton of time, relatively speaking. These days that’s completely irrelevant; if you want to write an app that never gets that kind of sudden slowdown, the JVM is not what you want (garbage collection pauses, OSes that pause, etc), so the ‘benefit’ is irrelevant. But it was (deemed to be) relevant way back then in the 90s when it was written. People would definitely expect an impl and would file feature requests for it, even if the core team did realize it was probably rarely a good idea to actually use them.
• Java definitely won’t remove them – once introduced, they stay, unless there is an extremely compelling reason not to. Backwards compatibility is good to have.
• LinkedList predates ArrayDeque and most other collection classes (LinkedList was an original addition. It wasn’t in java 1.0 (only Vector and Hashtable were), but it was in 1.1, which introduced the hierarchy (Collection, List, Set, Map, HashMap, ArrayList, and LinkedList). At one time it offered fast insertion at front and fast insertion at end without hardship (i.e. without having to first slow-roll navigate a ListIterator to the insertion point), a property no other type had at the time. Today, whatever problem you have that needs a collection, it is extremely unlikely LinkedList is correct, but back then, it was somewhat more likely.
• The extremely bad performance characteristic of LinkedList, explicitly not in big-O notation sense but in pragmatic sense – how those tracker objects tend to cause lots of cache page misses and thus they are ridiculously slow even when they should be fast, algorithmically – was far, far less of a factor back then. In the 90s, the cost of a cache miss was a few cycles and many processors didn’t have them in the first place. Today the cost is enormous – a thousand cycles.
• Most of all, who knows. Someone decided to write it. Doesn’t mean you should use it.