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
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:
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();
}
};
}
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);
System.out.println(obj.myList);
}
output:
0
1
2
[2, 0, 1]
Alternatively you can pass a comparator thru the constructor.
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();
}
}