CODEWITHSUNDEEP
java
Dzung Nguyen
Dzung Nguyen

Reputation: 3944

Java iterator get next without incrementing

I am writing the following loop in Java, for each loop I want to access the current and the next element of linked list r:

    List<T> r = new LinkedList();

    for (int i=0; i < r.size() - 1; i++) {
        T current = r.get(i);
        T next = r.get(i+1);
    }

This might be wasting as everytime I call get(i), it start from the beginning so the run time order of the code is O(n^2). How do I achieve the same using Iterator (this time it will be O(n))? This is my first attempt:

while(it.hasNext()) {
    T current = it;
    T next = it.next();
}

Upvotes: 9

Views: 33061

Answers (4)

Chengen Zhao
Chengen Zhao

Reputation: 11

Would be nice to use ArrayQueue if you don't mind the space complexity

      var queue = new ArrayDeque<>(list);
      while (!queue.isEmpty()) {
        var first = reversed ? queue.pollLast() : queue.pollFirst();
        if (!queue.isEmpty()) {
          var second = reversed ? queue.getLast() : queue.getFirst();
          //your code goes here
        }
      }
//or
    while (!queue.isEmpty()) {
        var first = reversed ? queue.removeLast() : queue.removeFirst();
        var second = reversed ? queue.peekLast() : queue.peekFirst();
        if (second!=null) {
          //your code goes here
        }
      }

Upvotes: 0

FredK
FredK

Reputation: 4084

T current = r.get(0);
for ( int i=0; i < r.size()-1; i++ ) {
   T next = r.get(i+1);
     // do stuiff here
   current = next;
}

Upvotes: 1

rgettman
rgettman

Reputation: 178253

Maintain a variable previous that is equal to the previous loop's current value.

T previous = null;
// If it makes sense to skip the first "null, first element" pair...
if (it.hasNext())
{
    previous = it.next();
}    

while (it.hasNext())
{
    T current = it.next();
    // Process previous and current here.

    // End of loop, after processing.  Maintain previous reference.
    previous = current;
}

This will be O(n) because you are using the Iterator over your entire linked list.

Upvotes: 12

RealSkeptic
RealSkeptic

Reputation: 34618

In each iteration, you should keep around a variable that will be the "current" and one that will be the "next". And you start processing your information starting from the second iteration, when you already have a current saved from the previous round.

T current = null;
T next = null;
Iterator<T> iter = r.iterator();

while ( iter.hasNext() ) {

    next = iter.next();
    if ( current != null ) { // Passed the first iteration

        // Now you can use current and next, they both have values.

    }
    current = next; // Save what was the "next" as the next "current".
}

It's best to make sure that the list itself doesn't have null values. If it does, and it's a valid value, then you should have a boolean flag instead of just checking whether current != null.

Upvotes: 5

Related Questions