仅访问 Java 中通用列表的每对元素一次

Question

我在 Java 中有一个列表，我想利用对每对元素的一次访问。例如，如果我有一个数组，我会做类似的事情：

O[] x = ...;
for(int i = 0; i<x.length; i++){
     for(int j=i+1; j<x.length;j++){
          someOperation(x[i],x[j]);
     }
}

问题是我有一个列表（我们假设不知道该列表是 ArrayList 还是 LinkedList）。为了与前面列出的案例具有相同的复杂性，我会用伪代码编写，例如：

 ListIterator<O> it1 = list.listIterator();
 while(it1.hasNext()){
      O x = it1.next();
      it2 = it1.clone();   //it2 have the same "status" of it1, but it is a different object in memory
      while(it2.hasNext()){
           y= it.next();
           someOperation(x,y);
      }
 }

据我所知，我们没有 it1.clone() 这样的东西。做类似事情的唯一方法是或多或少：

 int i = it1.nextIndex();
 it2 = list.listIterator(i);

但是，据我所知，

 list.listIterator(i);

可能有 O(n) 的复杂性——在 LinkedList 的情况下，这在其他语言中是绝对可以避免的。另一方面，使用随机访问（如 list.get(i)）实现相同的算法会更糟糕。假设列表是 LinkedList，正确的代码编写方法是什么？

Answer 1

我认为最好的解决方案还是使用 list.listIterator(i)。

在 LinkedList 的情况下，这是 O(n)，但您的算法的复杂性仍然是 O(n^2)。就 Big-Oh 而言，它不会改变任何东西！

干杯

Answer 2

如果可以修改列表：

Iterator<Items> things = list.iterator();

while(things.hasNext()){
    Item item = things.next();
    things.remove();
    Iterator<Item> others = list.iterator();
    while(others.hasNext()){
        //... do stuff;
    }
}

如果顺序无关紧要，您可以构建一个新列表。

List<Item> others = new ArrayList<>(list.size());
for(Item item: list){
    for(Item other: others){
        // do stuff
    }
    others.add(item);
}

Answer 3

你不能交换 i 和 j 吗？

List<E> x = ...;
int j = 0;
for (E ej : x) {
    int iMax = j++;
    int i = 0;
    for (E ei : x) {
        if (i++ >= iMax)
            break;
        someOperation(ei, ej);
    }
}

仅访问 Java 中通用列表的每对元素一次

Visit every couple of element of a generic List in Java only once

java

list

listiterator