Get Item by Index

Question

What is the best data structure, in java, for getting and setting items by index?

I was initially using ArrayList, but the problem is sometimes, I need to insert an element that is greater than the size of arraylist, like:

pseudocode
array = new ArrayList();
array.set(10, object);

Obviously this returns out an error. I could initialize the array with sentinel values, but using:

array.size()

will always say that my array is filled to the brim. Obviously it is just filled with sentinel values.

[Map](http://docs.oracle.com/javase/7/docs/api/java/util/Map.html). — Maroun, Nov 11 '13 at 09:05
@Maroun Maroun I reload the page, waiting for someone to state Map as the answer so I could accept, and all I see is your comment increasing upvotes :D — Secret, Nov 11 '13 at 09:07
Could you tell why you need to insert something at a point that is not exactly after the last element in the list but "further on"? [This question](http://stackoverflow.com/questions/390181/sparse-matrices-arrays-in-java) might be of interest if you are actually looking for a sparse list, otherwise go with a `Map`. — Anders R. Bystrup, Nov 11 '13 at 09:07

christopher · Answer 1 · 2013-11-11T09:09:14.300

3

If you always know the index at which you're inserting the value, then using a concrete implementation of the Map interface is usually the way to go.

The advantage of this set of classes is that, with knowledge of the index (or the Key in this context), you can directly retrieve the object from memory in O(1) time. That means no searching.

For example:

Map<String, String> map = new HashMap<String, String>();

map.put("KEY", "VALUE");

String key = "KEY";

// Do some processing..

String value = map.get(key);

// value variable now contains "VALUE".

Have a look at the documentation to get a really solid grasp of how to use this set of classes.

edited Nov 11 '13 at 09:09

answered Nov 11 '13 at 09:07

christopher

26,815
5
55
89

In this instance you would probably use `HashMap();`. – Klas Lindbäck Nov 11 '13 at 09:14
I usually just program to an interface, on the off chance I need to take advantage of Liskov's contribution to our field. – christopher Nov 11 '13 at 09:21
What I meant was that the key should be Integer instead of String. – Klas Lindbäck Nov 11 '13 at 09:43
Ah. Erm, yeah I don't see why not. – christopher Nov 11 '13 at 09:47

score 0 · Answer 2 · answered Nov 11 '13 at 09:11

It depends (as so often...). When your indices are within a certain reasonable range and you will use almost all of them, use an array with proper size:

Object[] items = new Object[MAX_INDEX];

If your range is much larger and many of your array slots will not be used, a Map (as already stated in other answers) is what you might need. HashMap is one possible implementation:

Map<Integer, Object> items = new HashMap<Integer, Object>();

Get Item by Index

2 Answers2