14
for (Entry<Double, String> entry : map.entrySet()) { 
        Double key = entry.getKey(); 
        String value = entry.getValue(); 

        // double nextKey = ?
        // String nextvalue = ?

        // double prevKey = ?
        // String prevValue = ?
    }

is it possible to know what the previous element and the next element while iterating the map?

d_low
  • 141
  • 1
  • 1
  • 7
  • 3
    Most Maps have no guaranteed ordering, so unlikely. – Evan Knowles May 07 '15 at 11:06
  • 4
    `LinkedHashMap` - see this http://stackoverflow.com/questions/2889777/difference-between-hashmap-linkedhashmap-and-treemap – ChristofferPass May 07 '15 at 11:06
  • 1
    Short answer: No, not reliably. A `Set` does not have a specified order, hence. You could save the previous/next entry in a separate variable/variables, but the order of the entries may not be the same on successive calls of this part of code. – Dominik Sandjaja May 07 '15 at 11:08
  • @DaDaDom actually, there are sets that support such navigation, like `NavigableSet` implementations. – Alex Salauyou May 07 '15 at 11:35
  • @SashaSalauyou agreed, but the return value of `.entrySet()` does not mention any such order, hence, there is no guarantee about the order. – Dominik Sandjaja May 07 '15 at 12:07
  • @DaDaDom see here: http://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html#entrySet-- – Alex Salauyou May 07 '15 at 12:08

2 Answers2

30

You can use NavigableMap for this, which entrySet()'s iterator return entries in ascending key order:

NavigableMap<Double, String> myMap = new TreeMap<>();

//...

for (Map.Entry<Double, String> e : myMap.entrySet()) {
    Map.Entry<Double, String> next = myMap.higherEntry(e.getKey()); // next
    Map.Entry<Double, String> prev = myMap.lowerEntry(e.getKey());  // previous

   // do work with next and prev
}

Every entry retrieval is O(logN), so for full iteration this is not the most effective approach. To be more effective, on iteration just remember last 3 entries, and use 1st as prev, 2nd as current and 3rd as next, as @Malt suggests.

Community
  • 1
  • 1
Alex Salauyou
  • 14,185
  • 5
  • 45
  • 67
4

A TreeMap is an OrderedMap and a NavigableMap and will allow you to iterate forward and backward, allowing you to access previous and next keys with lowerKey() and higherKey() respectively. However it might not be the best solution.

Can you describe the actual problem you're trying to solve, and we can give you a more fitting solution?

Kayaman
  • 72,141
  • 5
  • 83
  • 121
  • I need to generate key with each new addition in the map. The calculation depends on the previous and next value and the map must be sorted according to the key, which determines the position of the new addition. – d_low May 07 '15 at 21:00
  • Is the complexy of lowerEntry O(1) or O(log n)? After all if you already have a pointer to an element, moving in the tree can be easy. – Nathan B Feb 20 '22 at 12:45
  • @NathanB it's `O(log n)`. The parameter is a key not a pointer, so it works like `get()` in terms of time complexity and sort of like `get(key-1)` logically. – Kayaman Feb 21 '22 at 09:29
  • @Kayaman is there an implementation of TreeMap with linked list of elements to allow iterating in O(1)? – Nathan B Feb 21 '22 at 11:17
  • @NathanB that's a different issue. Iterating any `Map` fully is `O(n)`. You can keep track of the next/current/previous elements yourself easily with the `Iterator`, but since most maps don't have a guaranteed iteration order it doesn't make sense with all of them. – Kayaman Feb 21 '22 at 11:22