CODEWITHSUNDEEP
javacollectionstime-complexity
Aadi Droid
Aadi Droid

Reputation: 1739

Efficient way to modify a list of objects using maps

I have a list of objects, these objects can shift position in the list or even be removed, this object that I am saving, each of them have an unique id, lets call this id "key". To quickly check membership in the list I have an additional map which is mapped as

<object.getKey(), object>

Currently I get a call to my method with this key, and I do a 

map.contains(key)
// For delete
list.remove(map.get(key))
// For edit
Object oldObj = list.get(map.get(key))
// Modify the old obj, they are immutable so I need to set 
// old position with new object
list.set(map.get(key), newObject)

For sure this code is shit, but I am not able to wrap my head around a clean solution for this, I want to avoid any O(n) searches on the list which is clearly happening in the case of the list.remove and list.get!

One of the solutions I could think of was to map the key to the list position but then in case the map has a delete operation or an insert operation I'd have to update the whole map from the position of change! Again O(n). Any suggestions on the most efficient way to do this?

Upvotes: 1

Views: 212

Answers (1)

Mureinik
Mureinik

Reputation: 312086

You haven't specified what exactly you need to do with the list, but assuming you're looking for a collection with a predictable order, consider using a LinkedHashSet - it retains the order of insertion while stile allowing operations like add, remove or contains in O(1).

Upvotes: 2

Related Questions