Java：如何以排序的方式迭代LinkedList？

Question

如何在不排序LinkedList的情况下检索对象？

class MyClass<T> implements Iterable<T> {

    private LinkedList<T> myList = new LinkedList<>();

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {

            @Override
            public boolean hasNext() {
                return false;
            }

            @Override
            public T next() {
                // SHOULD RETURN THE ELEMENTS OF MYLIST IN A SORTED WAY
                return null;
            }

        };
    }
}

在这种情况下，我们可以假设类型为T的对象具有一个整数字段用于排序。

- user13121591

---

如果 hasNext 返回 false，则根本不应调用 next。 - talex

Answer 1

除非你创建额外的方法进行“即时”排序或在另一个对象中存储预排序列表，否则不可能实现（我假设您不想改变原来的列表顺序）。

这两种方法都有成本：

• 你可以保持当前索引的索引并查找整个列表中的下一个索引，但这会花费 CPU。
• 你可以创建列表的私有副本并对其进行排序，然后返回这个新列表，但这会消耗更多的内存，并且必须在原始列表的值发生更改时保持新列表更新。

- Wolfgang Amadeus

Answer 2

简短回答：不行。

排序有点像查找运行时的最小值/最大值，你无法在不遍历列表中的每个元素的情况下找到它，因此你需要将其全部排序，通过使用 Heap 的一种方法来实现，这意味着如果您不希望对列表本身进行排序，则需要额外的内存。

@Override
public Iterator<T> iterator() {
    PriorityQueue<T> heap = new PriorityQueue<>(list);
    return new Iterator<T>() {

        @Override
        public boolean hasNext() {
            return !heap.isEmpty();
        }

        @Override
        public T next() {
            return heap.poll();
        }

    };
}

- Sleiman Jneidi

---

如果类型“T”没有实现Comparable，则必须在PriorityQueue的构造函数中指定Comparator。 - user17201277

Answer 3

如果类型 T 实现了 Comparable<T>，你可以这样做。

static class MyClass<T extends Comparable<T>> implements Iterable<T> {

    private LinkedList<T> myList = new LinkedList<>();

    @Override
    public Iterator<T> iterator() {
        return myList.stream().sorted().iterator();
    }
}

public static void main(String[] args) {
    MyClass<Integer> obj = new MyClass<>();
    obj.myList.add(2);
    obj.myList.add(0);
    obj.myList.add(1);

    for (int i : obj)
        System.out.println(i);

    System.out.println(obj.myList);
}

输出：

0
1
2
[2, 0, 1]

或者你可以通过构造函数传递一个比较器。

static class MyClass<T> implements Iterable<T> {

    private LinkedList<T> myList = new LinkedList<>();
    private final Comparator<T> comparator;

    public MyClass(Comparator<T> comparator) {
        this.comparator = comparator;
    }

    @Override
    public Iterator<T> iterator() {
        return myList.stream().sorted(comparator).iterator();
    }
}

- user17201277