A bit of warning - this is going to get a bit involved and very technical.

---

When I was in the middle stages of designing the Java Rabbit Engine (http://jrabbit.minds-eye-games.com/), I began considering how I would manage groups of active game objects. There are a number of stipulations for a rigorous game engine:

Necessary:

• Hold as many objects as needed (basically, no max limit).
• Dynamically resize to hold new objects.
• Dynamically remove objects when they are no longer needed.
• Iterate through the current objects in the list, performing operations wherever needed.

These would be nice:

• Maintain order of addition.
• Not allow duplicate objects.
• Allow random access.
• Allow for fast checking of whether or not an object is present in the list.
• When an iteration is started, iterate over the same objects that were initially in the list, even if some of them are removed or new ones are added during iteration (basically, cache removals and additions until iteration is over). (Remember this as Point X, it's potentially incredibly useful and I decided I wanted to have it.)

And, obviously, all of these need to be as fast as possible, and not increase as more objects are added to the list. Basically, they need to be O(1) instead of O(n) in operation time, if possible.

So, these ideal points in mind, I started looking at existing methods. From what I found, JME and Slick both seemed to use ArrayList fairly often. It makes sense. Once the objects are on the list, it's basically array-fast to iterate through them.

However, how dynamic are they? ArrayList in particular seems a particularly bad choice, because when you need to add more objects than its max limit, it spazzes out and needs to allocate and reseed an entire new array. Also, when you want to remove objects, it has to search through the entire thing to find it, and then it needs to move objects around to fill the gap! The larger the list gets, the longer these adjustments will take. Therefore, though it doesn't have a technical limit, it has a practical one.

The concept I would use for this is: For an iteration-based data structure to allow for "unlimited objects," the maximum number of objects it can iterate through and maintain a viable operation speed should be effectively the same as the number of objects it can have while performing dynamic operations (additions and removals) and keep that viable operation speed.

So ArrayList, the common choice, seems to be non-optimal. What other choices are there?

Let's look at a few:

LinkedList:
Good:

• Not quite as fast as an Array or ArrayList, but still quite competitive.
• Adding new objects is a breeze, being O(1) and totally independent of the number of other entries in the list.
• Can append an entirely different LinkedList to its end without any increase in operation time.

Bad:

• Removing objects is O(n).
• Allows for duplicate entries.
• Does not allow Point X.

LinkedHashMap:
Good:

• About LinkedList fast.
• By Keying objects to themselves, adding and removing objects can approach constant time.
• Does not allow for duplicate entries.
• Checking if an object is contained in the list is essentially O(1).

Bad:

• Cumbersome API.
• Does not allow Point X.

In all seriousness, lobotomizing a LinkedHashMap seemed like the most feature-complete option. However, I felt I could do better than that, so I made my own data structure.

The result is something I call LockingList (and yes, it has been designed to accommodate Point X).

Here is the code, including documentation:



So, what do you guys think? Is the above an improved method? Or is vanilla ArrayList better, and there are advantages/disadvantages in the different methods I'm not aware of?

I ran a few tests, constantly adding objects (it was a stress test), and I noticed some stutters as the number of objects got very high. Granted, the stutters only happened once each jump, but I still felt that they shouldn't be there.

Additionally, the removal time is what really concerns me.

There is an inherent flaw in your design. You are tracking added and removed objects in different lists. If you add and remove the same object a certain number of times, you can't be sure what you end up with after you 'unlock' your datastructure. It depends on the order in which you process the lists holding the added/removed items, not the order in which you added/removed your items.

You should have a single list holding 'events': the item and whether it is currently in an added or removed state. Map<Object, Boolean> modifications or List<Pair<Object, Boolean>> for example. Once you unlock it you can iterate over the map, adding and deleting the elements to/from your 'main' collection.

Hehe, I guess that's true...

Guess I'm old school in this regard.
I only use bare arrays.
I use Lists in special cases when you never have to search for one element / dont need random access. -> particle systems

In my latest minigame, I used a combination of ArrayLists and LinkedLists to try something else; for what its worth, it worked, but I personally wouldn't trust it in a very big game. Not sure.

Also, my main point here is: You never need "unlimited" space, because you can never use an infinite amount of objects anyway.
All arrays have limits, and I just set them accordingly.

Best example is of course a given particle system in which you set the maxParticles parameter.

Well I'm only concerned with data structures in action packed arrays so to speak; for example the inventory item data structure could be whatever - not important.
And in these action packed arrays, a given object shall only be removed when a certain event happens; meaning we have straight causality.

My point is, there is no removal time, because you never search.
For example some logic results in an enemy dying, the next line of code is a check if he's dead, and then, null that object.
I don't have to iterate separately to remove it; I remove it when I'm already iterating, to update this object.
item = null;    obviously is isn't as easy with arraylist, because you cannot remove an object while iterating the collection.

I don't know, at some point, practically speaking, things will get so convoluted... Depends on the game I guess, but there is always a limit...
In super mario there would never be more than like 30 enemies on one screen, at one time I guess. Multiply this by the length of one map and you have your limit. Maps have similar lengths by game design...
I just see limits everywhere internally
if the whole screen is full of stuff, doesnt really make such sense to add double that... maybe for benchmarking

I doubt practical usefulness, is what I'm saying.

Though interesting technically.

it's not that fast and the stuff under your 'necessary' list can all be fulfilled by collections that already exist?

depends on your specific uses

ArrayList has very fast adding, but very slow removing, is ordered, and iterating over it is quick (plus you can use indexes to remove objects semi-quickly if you know the index). the contains method is slow.

HashSet (it actually is just using a HashMap in the background, you can write a faster implementation of this by yourself or I can give you one) has decent adding, very fast removing (tops out arraylist if you are adding as often as removing) is unordered, and does not iterate as quickly. the contains method is fast.

those are just 2 popular collections.

usually when I'm going for speed I use my own HashSet implementation.

No. Not unless you have a high % of collisions (which would ruin a hash anyway). Iterating over an array is a lot faster than a linked set of references, so even if it's a larger array with possible nulls, in general it'd be faster. Unless of course the array is very large with very few elements - which is a different problem. You can make it reduce size the array after a certain number of elements have been removed.

Well I prefer bare arrays anyway. But using this, I would always fear that something would get screwed up, like removing the wrong, or whatever; and such a behavior is then hard to spot - like what really happened - which was removed which shouldn't be removed

I just like the control and accessibility of an array so much.

I usually just use a HashMap and an ArrayList of its keys.