Java listIterator - 交换 2 个值

Question

我有一个有序的字符串 ArrayList：我编写了这个静态方法来保持它的排序，每次将元素添加到 ArrayList 时我都会使用它。

使用 listIterator，我从 ArrayList N 的最后一个值开始：如果 N-1 出现在 N 之后，我会反转这两个值。然后我转到单元格 n-1，并重复相同的过程，直到到达 ArrayList 的末尾。

在这段代码中，我无法用 prev 反转 current：我做错了什么？

public static void sort(ArrayList arr, String s){

    if(arr.size()>1){

        ListIterator<String> iterator = arr.listIterator(arr.size());
    
        while(iterator.hasPrevious()){
            String current = iterator.previous();
            String prev = iterator.previous();    
            if(compare(current,prev) < 0){
                
                iterator.set(current);
                iterator.next();
                iterator.set(prev);
                iterator.previous();

            } else {
                break;
            }
        }
    }
}

Answer 1

从 ListIterator#set(E e) 的文档中我们可以阅读

Replaces the last element returned by next() or previous() with the specified element

所以让我们看看在您的数据交换代码中发生了什么，例如 arr=["b", "c", "a"]。

我将迭代器的位置标记为<或>以指出潜在方向set方法.

所以会是

[elementE] < elementF 如果在 next() 之后调用它返回 elementE
elementD > [elementE] 如果在 previous() 之后调用它返回 elementE

让我们看一下您用来交换元素的代码。

iterator.set(current); //1
iterator.next();       //2
iterator.set(prev);    //3
iterator.previous();   //4

在执行之前，您的应用程序（迭代器和变量）的状态是

//current = "a"; prev="c", arr=["b", "c", "a"]
"b" > "c" "a"  
     |
   position of iterator

因此，由于迭代器指向元素 "c"，如果我们现在调用 set，它将被替换。

调用 iterator.set(current); 后，应用程序的 current="a" 状态将变为

//current = "a"; prev="c", arr=["b", "a", "a"]
"b" > "a" "a"  //`iterator.set` doesn't affect "position" of iterator

现在iterator.next();之后会变成

//current = "a"; prev="c", arr=["b", "a", "a"]
"b" "a" < "a"  //notce iterator was moved between "a" and "a" 
               //but points at *left* "a"

这是你的问题。

看看迭代器的方向（即<）并再次阅读此答案开头引用的文档。目前 iterator.set(prev); 将替换 middle 中的 "a"，而不是 end 中的 "a"，因为它是返回的中间元素next() 或 previous() 作为最后一个元素。

如果你想替换最后一个 "a"，你需要迭代器“指向”那个元素。所以你想创造像

这样的情况

"b" "a" > "a" - 从左边算起的点数
或"b" "a" "a" < - 从右边开始的点数

（还记得在像 "b" "a" < "a" 或 "b" "a" > "a" 这样的位置交换后设置迭代器，这样它将在我们要比较的两个下一个元素“之前”）。

在情况 1 中，您的交换代码可能类似于

//"b" > "c" "a"
iterator.set(current); //"b" > current "a"
iterator.next();       //"b" current < "a"
iterator.next();       //"b" current "a" <
iterator.previous();   //"b" current > "a" 
iterator.set(prev);    //"b" current > prev

(案例2的代码留给你做作业)

顺便说一句，你需要处理新元素在整个列表中最小的情况（比如在当前答案中 ["b", "c", "a"] 的场景（你需要嵌套 iterator.hasPrevious()）

Java listIterator - 交换 2 个值

Java listIterator - swap 2 values

java

iterator

arraylist

insertion-sort

让我们看一下您用来交换元素的代码。

这是你的问题。