1

By "the amount is unknown" I mean that at the time of creation of whatever data structure I use to store them in, I don't know how many objects there will end up being to store. Once I have all these objects, I want to be able to iterate through all of them, and it doesn't matter what order I visit them in. I'm wondering what would be the most efficient (in time and space, but mostly time) way to go about doing this in java.

I do have a cap on the max number of objects that there will be in the thing, so I was considering just making an array of this size. But I didn't want to waste space, and the array could end up being more than twice as big as the number of elements that actually get stored in it.

I was also considering a LinkedList, because I thought maybe it would be more efficient to iterate through it than having to create an iterator from something else like a hashmap and iterate through that. But I don't know how expensive it is to create an iterator from various java data structures.

So, any ideas?

Tim
  • 4,295
  • 9
  • 37
  • 49
  • Are we talking 10? 10000? 10G? Size does matter. – ptyx Apr 27 '12 at 01:28
  • The various data structure iterators are all tiny objects with similar creation costs. – David Harkness Apr 27 '12 at 01:31
  • @ptyx: well, we're talking decently small (like maybe 50 objects at most per data structure), but it's going to be something that's done (storing new objects and iterating through them) millions of times if not more. – Tim Apr 27 '12 at 01:37
  • 1
    I recommend you don't optimize (ie, worry too much about memory usage, speed, etc) until the system is running and demonstrably fails to meet the business requirement. Premature optimization is a bad thing. – Tony Ennis Apr 27 '12 at 01:38

3 Answers3

7

Use an ArrayList. This will allow you to iterate over the items without issue. You won't be unduly limited on size, and you won't have to know how many items in advance.

Tony Ennis
  • 12,000
  • 7
  • 52
  • 73
  • 1
    You may still end up with an array that's twice as big as necessary, but this is the best way to go given the very generic requirements. – David Harkness Apr 27 '12 at 01:28
3

From what I can understand it sounds like you need a dynamic array. I guess your main concern is iterating through the objects and you would not be inserting/deleting objects to/from the middle of the structure. In that case I think Java ArrayList class would suit your needs well.

Martin Prakash
  • 66
  • 4
0

You can try a Vector. A small summary from Javadocs: The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of a Vector can grow or shrink as needed to accommodate adding and removing items after the Vector has been created.

It provides random access and it is optimized for storage increments. Also, if you don't have any multithreading requirements, you can use an ArrayList which is unsynchronized.

rogermenezes
  • 1,143
  • 8
  • 12
  • Use `ArrayList` instead of `Vector` for single-threaded access. For multi-threaded access, you're better off with one of the lists from `java.util.concurrent`. `Vector` is old and kept for backward compatibility. – David Harkness Apr 27 '12 at 01:30
  • http://stackoverflow.com/questions/1386275/why-java-vector-class-is-considered-obsolete-or-deprecated – Jeffrey Apr 27 '12 at 01:30