Java: 如何以有序的方式迭代LinkedList？

Question

是否可以在不排序的情况下检索链表的对象？

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 的对象具有用于排序的 Integer 字段

Answer 1

这是不可能的，除非您创建额外的方法来排序 'on-the-fly' 或将预先排序的列表存储在另一个对象中（我假设您不想更改原始列表顺序）。

两种方法都有成本：

您可以保留 'current' 索引的索引并查找整个列表中的下一个索引，但这会花费 CPU
您可以创建列表的私有副本并对其进行排序，return 这个新列表，但它会占用更多内存，并且您必须保持新列表的更新，以防原始列表有值改变了。

Answer 2

简答：否

排序有点像查找运行 minimum/maximum，如果不遍历列表中的每个元素，您将无法找到它，因此您需要以某种方式对所有元素进行排序这样做是通过 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();
        }

    };
}

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();
    }
}

Java: 如何以有序的方式迭代LinkedList？

Java: how to iterate on a LinkedList in a sorted way?

java

sorting

collections

iterator