Part of the solution as to which data structure you will use will depend on how often, in what order, and so on, you will be accessing this information.
So, for example, if you are just going to iterate through the data for table generation, then things like arrays, vectors, stacks, queues or linked lists will work (though in the case of stacks or queues that is not, obviously, their primary advantage.)
But if you need to access individuals pieces of data at random times then obviously more will be needed. Hashtables, for example, search in constant time, that is, the time to access the data is (relatively) the same regardles of the size of the table. (I say relatively because if hashing collisions- where two items map to the same place- occur, one has to be "rehashed" to another place. So the time to access will be different, but not significantly so.)
There are priority queues, where the information is stored according to some criterion of value (for example, bills, according to date due then are stacked for payment), black-red trees, ordered arrays, 2-3-4 trees, heaps, and graphs.
Based on you basic description the following are the ones you will probably want to look at.
Arrays have quick insertion and constant time access if the index is known. But they have slow search capabilities, deletion, and are of fixed size. You can get around this with Vectors, but of course you tried this.
Ordered arrays have quicker searches than unsorted and the same disadvantages.
Stacks are Last In First Out but are slow for access of middle items by repeated pops(You can get around this if you create one from a linked list- just add a push() method that keeps linking to the head and then becoming the head, and the pop() keeps returning the head. In this case you can iterate through it like a linked list- and it
is a linked list, so you might as well use that, unless you need both traits.)
Queues are First In First Out, same advantages and disadvantages (and you can do the linked list thing again, with modifications).
Linked Lists are fast on iteration but slow on searches (since, like arrays, you search by starting at the beginning and looking until you find what you want) and might be more memory intensive (not sure, though).
Binary Trees, obviously more complex, are fast at everthing. Deletion is complex (but, as for all of these, you can find implementions to use so it's not that much of a problem). I believe its search time (in # times through the main workhorse algorithm) is no more than log2 (n) where n is the number of items in the tree- that is worst case, which is really good. The only really better time (without some really strange, comlicated algorithm) is O(c), where the time is the same no matter what (almost- see above).
Hashtables as I mentioned are really good at speedy accessing, but only as long as you know the key. Otherwise you have to get all the keys (or objects) and check them to see if they're what you want- and then it is just like an array, etc. It's deletion is slower, and it uses memory inefficiently.
So, if iteration is your game, use arrays or linked lists (limited only by memory, really), or trees. If random searches for specific items only, then hashtables or trees. If you will be adding to or deleting from
alot, then trees (in all their complex forms) and, if not alot of deleting, hashtables.
For specific implementations, check the java.util.Collections for the specialized types. You can find implementations of others (like red-black trees) on the web.
hope that helps,
[ July 20, 2002: Message edited by: Ian Ohlander ]
