How to iterate a list in both directions?

Question

I have a list of objects and want to iterate in forwards and backwards, until an element is found that is "valid".

MyClass {
    private boolean valid;
    public boolean isValid() { return valid; }
}

List<MyClass> classes; //assume sorted list

Now I want to start at position idx, and iterate both forwards and backwards to find the closest element that is valid. So far I already got the forward algorithm working. But I feel that the code could be optimized:

//supposed to start at position X

int idx = 10;

//find the closest element that is valid
for (ListIterator<MyClass> itr = classes.listIterator(idx); itr.hasNext();) {
    if (itr.hasNext()) {
        MyClass my = itr.next();
        while (!my.isValid()) {
            if (itr.hasNext()) {
                my = itr.next();
            } else {
                break;
            }
        }
    }
    Sysout("the closest valid element is: " + my);
}

Could the iterator algorithm be written better?

http://stackoverflow.com/questions/2102499/iterating-through-a-list-in-reverse-order-in-java :: here for reverse order — Stefan Sprenger, Aug 28 '14 at 08:07
use `iter.hasPrevious()` and `iter.previous()` like you do with `next()` — Nir Alfasi, Aug 28 '14 at 08:07

score 3 · Accepted Answer · answered Aug 28 '14 at 08:11

Use two iterators at the same time. Start both of them at idx, and advance each of them in each iteration of the loop, until you hit the limit:

ListIterator<MyClass> fwd = classes.listIterator(idx);
ListIterator<MyClass> bck = classes.listIterator(idx);
MyClass found = null;
while (fwd.hasNext() || bck.hasPrevious()) {
    if (fwd.hasNext()) {
        MyClass my = fwd.next();
        if (my.isValid()) {
            found = my;
            break;
        }
    }
    if (bck.hasPrevious()) {
        MyClass my = bck.previous();
        if (my.isValid()) {
            found = my;
            break;
        }
    }
}

If found is null at the end of the loop, no valid items were found. Otherwise, found contains the nearest item to idx. If two valid items are located at the same distance from idx, the item located forward would be returned.

You've a typo in your while condition - the bck should check "hasPrevious". — brindy, Aug 28 '14 at 08:15

score 1 · Answer 2 · answered Aug 28 '14 at 08:48

      package iteratorPract;

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class MyIterClass {
    private boolean valid;

    public boolean isValid() {
        return this.valid;
    }

    public void setValid(boolean valid) {
        this.valid = valid;
    }

    public static void main(String[] args) {
        MyIterClass m1 = new MyIterClass();
        m1.setValid(true);
        MyIterClass m2 = new MyIterClass();
        List<MyIterClass> classes = new ArrayList<MyIterClass>();
        classes.add(m1);
        classes.add(m2);

        // from last
        ListIterator<MyIterClass> l1 = classes.listIterator(classes.size());

        while (l1.hasPrevious()) {
            if (l1.previous().isValid())
                System.out.println("it is valid");
            else
                System.out.println("not valid");
        }
        // from start
        ListIterator<MyIterClass> l2 = classes.listIterator();

        while (l1.hasNext()) {
            if (l1.next().isValid())
                System.out.println("it is valid");
            else
                System.out.println("not valid");
        }

    }

}

score 0 · Answer 3 · edited Dec 13 '20 at 20:09

0

You can use ListIterator#hasPrevious() and ListIterator#previous() for backward iteration and ListIterator#hasNext() and ListIterator#next() for forward iteration with ListIterator.

edited Dec 13 '20 at 20:09

Dave Jarvis

30,436
41
178
315

answered Aug 28 '14 at 08:10

Ruchira Gayan Ranaweera

34,993
17
75
115

How to iterate a list in both directions?

3 Answers3