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

Is possibe to retrive the objects of a LinkedList without sorting it?

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

        };
    }
}

In this case we can assume that objects of type T have an Integer field for sorting

CodePudding user response：

It's not possible, unless you create extra methods to sort 'on-the-fly' or store a pre-ordered list in another object (I'm assuming you dont want to change the original list order).

Both methods have costs:

You can keep an index of the 'current' index and find the next index looking throu the whole list, but this costs CPU
You can create a private copy of the list and sort it, and return this new list, but it costs more memory, and you have to keep the new list updated in case the original list have values changed.

CodePudding user response：

Short answer: No.

Sorting is sort of finding a running minimum/maximum, there is no way you can find that without going through every element in the list and hence you would need it all sorted somehow, a way of doing that is through a Heap which means extra memory if you dont wish to sort the list itself.

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

    };
}

CodePudding user response：

If type T implements Comparable<T>, you can do like this.

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

output:

0
1
2