Java基于LinkedList实现选择排序的效率与节点操作问题

实现背景 #

• 核心目标：基于Java的LinkedList实现选择排序算法，已掌握ArrayList的对应实现，无需建议改用ArrayList。本次实现的核心目的是验证链表相对数组的优势（插入、删除操作效率高）与固有劣势。
• 技术选型参考：此前在C语言中可通过指针直接访问链表节点结构体完成同类实现，Java中最接近的可用工具为ListIterator。

当前编写的可正常编译运行的代码如下：

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
            // 下方交换代码会触发ConcurrentModificationException // Problem C
            // it.previous();
            // it.add( list.remove( indexToMoveToCurrent ) );
        }
        
        cards.addAll( list );
    }
}

现存问题 #

• 问题A：内层迭代器初始化的性能浪费 #

  为了从外层迭代器it所在位置的下一位开始遍历，目前需要传入索引调用listIterator方法。经推测，该方法会从链表头部开始逐节点遍历到指定索引位置，存在明显性能损耗。既然已经持有前序位置的迭代器，如何从指定迭代器位置出发，高效遍历到链表末尾？

• 问题B：索引调用set方法的性能损耗 #

  交换元素时目前需要传入索引调用list.set方法，该操作和问题A的情况一致，存在不必要的遍历性能浪费。

• 问题C：节点调整操作触发并发修改异常 #

  原本计划通过修改链表节点引用的方式完成元素调整，而非仅修改节点存储的元素值，尝试编写的移除插入逻辑会触发ConcurrentModificationException。

  当前仅修改节点值的代码执行效果对应参考图中间状态，期望实现参考图底部的节点调整效果：
  
  虽然在当前选择排序算法中，两种调整方式的最终结果差异不大，但后续还会研究其他排序算法的链表实现，目前LinkedList的操作表现不符合预期。

额外疑问 #

逐位置两两交换元素，和「移除目标元素后插入到指定位置之前」的逻辑并不等价：例如原序列为abcdefgh，交换位置b和f会得到afcdebgh，但将f移除后插入到b之前会得到afbcdegh。原本认为LinkedList可以高效完成后一类操作，如果LinkedList只能像数组一样依赖索引操作，该数据结构的存在价值是什么？

内容的提问来源于stack exchange，提问作者z32a7ul