How to add element at specific index/position in LinkedHashMap?

Question

I have an ordered LinkedHashMap and i want to add element at specific index , say at first place or last place in the map. How can i add element in LinkedHashMap at an specific position?

Even if I could add an element to FIRST or LAST position in LinkedHashMap would help!

Answer 1

You could do this element adding to 1. or last place:

Adding to last place ► You just need to remove the previous entry from the map like this:

map.remove(key);
map.put(key,value);

Adding to first place ► It's a bit more complicated, you need to clone the map, clear it, put the 1. value to it, and put the new map to it, like this:

I'm using maps with String keys and Group (my custom class) values:

LinkedHashMap<String, Group> newMap=(LinkedHashMap<String, Group>) map.clone();
map.clear();
map.put(key, value);
map.putAll(newMap);

As you see, with these methods you can add unlimited amount of things to the begin and to the end of the map.

Answer 2

You can not change the order. It is insert-order (by default) or access-order with this constructor:

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

• Constructs an empty LinkedHashMap instance with the specified initial capacity, load factor and ordering mode.

• Parameters: initialCapacity - the initial capacity loadFactor - the load factor accessOrder - the ordering mode - true for access-order, false for insertion-order

• Throws: IllegalArgumentException - if the initial capacity is negative or the load factor is nonpositive

See: LinkedHashMap

Answer 3

Apache Commons solution : ListOrderedMap

Since the JDK's LinkedHashMap ensures only insertion order retrieval, in case you we want to insert at an index, we can use alternatively Apache Commons' ListOrderedMap. It does it as it sounds - by having a list to maintain the order of insertion with the corresponding index and a normal map to insert as we generally do. Here is what the docs say:

public class ListOrderedMap<K,V>
extends AbstractMapDecorator<K,V>
implements OrderedMap<K,V>, Serializable

Decorates a Map to ensure that the order of addition is retained using a List to maintain order.

The order will be used via the iterators and toArray methods on the views. The order is also returned by the MapIterator. The orderedMapIterator() method accesses an iterator that can iterate both forwards and backwards through the map. In addition, non-interface methods are provided to access the map by index.

If an object is added to the Map for a second time, it will remain in the original position in the iteration.

Note that ListOrderedMap is not synchronized and is not thread-safe. If you wish to use this map from multiple threads concurrently, you must use appropriate synchronization. The simplest approach is to wrap this map using Collections.synchronizedMap(Map). This class may throw exceptions when accessed by concurrent threads without synchronization.

Note that ListOrderedMap doesn't work with IdentityHashMap, CaseInsensitiveMap, or similar maps that violate the general contract of Map. The ListOrderedMap (or, more precisely, the underlying List) is relying on equals(). This is fine, as long as the decorated Map is also based on equals(), and hashCode(), which IdentityHashMap, and CaseInsensitiveMap don't: The former uses ==, and the latter uses equals() on a lower-cased key.

Here is its implementation for adding to a position:

        /**
428     * Puts a key-value mapping into the map at the specified index.
429     * <p>
430     * If the map already contains the key, then the original mapping
431     * is removed and the new mapping added at the specified index.
432     * The remove may change the effect of the index. The index is
433     * always calculated relative to the original state of the map.
434     * <p>
435     * Thus the steps are: (1) remove the existing key-value mapping,
436     * then (2) insert the new key-value mapping at the position it
437     * would have been inserted had the remove not occurred.
438     *
439     * @param index  the index at which the mapping should be inserted
440     * @param key  the key
441     * @param value  the value
442     * @return the value previously mapped to the key
443     * @throws IndexOutOfBoundsException if the index is out of range [0, size]
444     * @since 3.2
445     */
446    public V put(int index, final K key, final V value) {
447        if (index < 0 || index > insertOrder.size()) {
448            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + insertOrder.size());
449        }
450
451        final Map<K, V> m = decorated();
452        if (m.containsKey(key)) {
453            final V result = m.remove(key);
454            final int pos = insertOrder.indexOf(key);
455            insertOrder.remove(pos);
456            if (pos < index) {
457                index--;
458            }
459            insertOrder.add(index, key);
460            m.put(key, value);
461            return result;
462        }
463        insertOrder.add(index, key);
464        m.put(key, value);
465        return null;
466    }

Answer 4

public static <K, V> void add(LinkedHashMap<K, V> map, int index, K key, V value) {
  assert (map != null);
  assert !map.containsKey(key);
  assert (index >= 0) && (index < map.size());

  int i = 0;
  List<Entry<K, V>> rest = new ArrayList<Entry<K, V>>();
  for (Entry<K, V> entry : map.entrySet()) {
    if (i++ >= index) {
      rest.add(entry);
    }
  }
  map.put(key, value);
  for (int j = 0; j < rest.size(); j++) {
    Entry<K, V> entry = rest.get(j);
    map.remove(entry.getKey());
    map.put(entry.getKey(), entry.getValue());
  }
}

Answer 5

Just divide you LinkedHashMap on 2 arrays. Make first array with size index - 1 and put at the end new Entry. Then fill first array with entries from the second one

Answer 6

...

LinkedHashMap<String, StringExtension> map = new LinkedHashMap<>();

map.put("4", new StringExtension("4", "a"));
map.put("1", new StringExtension("1", "b"));
map.put("3", new StringExtension("3", "c"));
map.put("2", new StringExtension("2", "d"));

for (Map.Entry<String, StringExtension> entry : map.entrySet()) {
    Log.e("Test", "" + entry.getKey() + " - "+ entry.getValue().value);
}


Collection<StringExtension> temp = new ArrayList<>(map.values());
StringExtension value = map.remove("3");
map.clear();
map.put(value.key, value);

for (StringExtension val : temp) {
    map.put(val.key, val);
}

Log.e("Test", "---");

for (Map.Entry<String, StringExtension> entry : map.entrySet()) {
    Log.e("Test", "" + entry.getKey() + " - "+ entry.getValue().value);
}

...

private class StringExtension
{
    String key;
    String value;

    public StringExtension(String key, String value) {
        this.key = key;
        this.value = value;
    }
}

Answer 7

As suggested in other answers, it is certainly not recommended as by inserting a value you will go against the system.

Why?
Because LinkedHashMap is backed by a HashMap and a LinkedList.
The last is used in order to preserve insertion order.
Obviously, LinkedList is pretty good in insertion to the head and to the tale (doubly-linked). It provides O(1) time complexity for this operation.
However, it is very slow in insertion to a certain position as in order to find this position you got to iterate all over the list, which in the worst case will take O(n) what is quite expensive especially for large datasets.

I personally do not recommend it as it is quite inefficient, but if you understand the cons and it is what you want,
you may use this extension function in order to insert a key-pair onto a certain position.

fun <K, V> LinkedHashMap<K, V>.insertAtIndex(key: K, value: V, index: Int) {
    if (index < 0) {
        throw IllegalArgumentException("Cannot insert into negative index")
    }
    if (index > size) {
        put(key, value)
        return
    }
    val holderMap = LinkedHashMap<K, V>(size + 1)
    entries.forEachIndexed { i, entry->
        if (i == index) {
            holderMap.put(key, value)
        }
        holderMap.put(entry.key, entry.value)
    }
    clear()
    putAll(holderMap)
}

It will take O(n) time and O(n) space.

Answer 8

It's a Map, it doesn't have indexes. It has buckets. The way it works is when you do a

put(key, val)

It hashes the key to find out which bucket to put the val in.

The LinkedHashMap maintains a doubly linked list so it can record the order in which entries are inserted (or accessed, depending on how you instantiate the map). There is no method on the API on the Map to insert a key,val pair at a certain index of the linked list, because that is not the purpose it serves.

Answer 9

Let's assume the data being applied on the Map comes from a List (Collection), then you should create a reversed loop that starts reading from the end of that list till it gets to the first like this: for (int key = collection.size()-1; key > map.size(); key--) { Data data = collection.get(key); map.put(key, data); }

Answer 10

An element can be added as the first or last element using the putFirst() and putLast() methods which are being added to LinkedHashMap in Java 21 as part of the sequenced collections enhancement:

LinkedHashMap<String, Integer> linkedHashMap = // ...

linkedHashMap.put("A", 1);
linkedHashMap.putLast("B", 2);
linkedHashMap.putFirst("C", 3);

// linkedHashMap is now [C=3, A=1, B=2]