Iterator from a specific object in a LinkedHashMap

Question

I have a LinkedHashMap, I have my key as an ID, what I'm trying to achieve is for me to be able to look up an ID and if it is present have an iterator from that entry to the end of the map. What i've tried so far

Map<String, Obj> map = new LinkedHashMap<>();
Iterator it = map.entrySet().iterator();

But is there a way I can get the iterator to start from a particular object without doing a linear search and finding it myself?

Answer 1

No, there is no such a feature in LinkedHashMap.

But you can simulate it with a List at the cost of only one traversal:

 Map<String, Object> map = new LinkedHashMap<>();
 Map<String, Integer> indexesMap = new HashMap<>(map.size());
 int index = 0;
 for (String key : map.keySet()) {
 indexesMap.put(key, index++);
 }
 List<Entry<String, Object>> entries = new ArrayList<>(map.entrySet());
 // ...
 String key = ...
 Iterator<Entry<String, Object>> iterator = entries.listIterator(indexesMap.get(key));

On each subsequent invocation of entries.listIterator you will get the iterator with the O(1) complexity.

EDIT

If you also want removals to be O(1), then you should not use LinkedHashMap.

You could implement your own doubly linked list and store its nodes in a HashMap as well. Then search the node by the key from the map. When you get the node, you can traverse the rest of the subsequent entries from the linked list, or you can remove it in O(1) by removing it from both the map and the linked list.

• Aadi Droid: This is the solution I am currently using, but when I have a deletion in the middle of the list I need to update the map from that position! I have frequent edits and deletes. I know it sounds like I am asking for too much, but making sure there is no off the shelf solution for this.
• Dragan Bozanovic: @AadiDroid Ok, I wasn't aware of that. Please see my edited answer.

Answer 2

No, it's not possible for LinkedHashMap. There's a method tailMap in NavigableMap interface which can help you to do this (map.tailMap(key).iterator()), but this interface is not implemented by LinkedHashMap If TreeMap (possibly with custom comparator) is an appropriate replacement in your case, consider using it.

• Aadi Droid: Well I need the insertion order to be maintained, I am not exactly sure a TreeMap does that? I am reading on it though.