Question

0

420

Views

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

over 4 years ago · Santiago Trujillo

3 answers

Answer question

0

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.

over 4 years ago · Santiago Trujillo Report

0

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

    };
}

over 4 years ago · Santiago Trujillo Report

0

Answer question

Find remote jobs

Accepted Answer · 2022-04-28T14:18:05.512Z

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

0

420

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

3 answers

0

0

0

Find remote jobs

Andres GPT