CODEWITHSUNDEEP
javasortingcollectionsiterator
user13121591
user13121591

Reputation: 135

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

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

Upvotes: 4

Views: 518

Answers (3)

user17201277
user17201277

Reputation:

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

Upvotes: 0

Sleiman Jneidi
Sleiman Jneidi

Reputation: 23329

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

    };
}

Upvotes: 2

Wolfgang Amadeus
Wolfgang Amadeus

Reputation: 396

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.

Upvotes: 3

Related Questions