ArrayList and LinkedList are both very similar. They’re used in the exact same way, but have very different performance characteristics. Even if you’re using the right one for the job, you might still be using the list in a bad way leading to bad performance.
A very important thing to consider when choosing which one to use is how they scale for large lists. How lists (and algorithms in general) scale with their size can be described using Big O notation.
For example, ArrayList.get(int index) method always returns in O(1) time. The time it takes to find an object is always the same. It does not get slower as the list grows, since it’s just simple array access in this case.
LinkedList.get(int index) however is O(n). Finding the i’th object requires it to follow the linked list to the i’th. As the list gets longer, get(int index) ON AVERAGE gets slower. Finding the first object is obviously fast, O(1), but finding the last object is O(n) where n is the length of the list. On average, finding an object is O(n/2). However, the /2 is irrelevant in big O notation since it only describes how the list SCALES. LinkedList.get(int index) on average scales linearly with the list’s length, so it’s therefore O(n).
ArrayList:
- Adding objects is O(1).
- Getting objects is O(1).
- Removing objects is O(n). Double the size and the (average) access time doubles too. Note that remove(0) is the worse case scenario as a remove forces a copy of all following objects to fill the first spot that was left empty.
- contains(object) is O(n) since the whole list has to be traversed to check if the object is in the list.
LinkedList:
- Adding objects is O(1)
- Random access (getting using indices) is O(n). Getting objects in order using an iterator is O(1).
- Removing objects is O(n) when using indices or references to remove objects. Removing objects with an iterator is O(1).
- contains(object) is O(n) since the whole list has to be traversed to check if the object is in the list.
Which should I use for my game objects?
Looking at the above makes it’s easy to conclude that LinkedList is the most flexible one. Adding objects is O(1), iterating over objects in order is O(1) and removing objects as we iterate over them is O(1). ArrayList is very similar, but is O(n) for removing. Game objects will die and be removed as the game progresses, so LinkedList scales the best.
Even though LinkedList scales better, it does not necessarily have to be the fastest option for a certain use case. The problem with LinkedList is that it creates an Entry object which it wraps in each object added to store the next and previous entries. This allocation (and later garbage collection) makes it a lot slower to add and remove stuff than ArrayList in most use cases. Big O notation says nothing about the actual performance of these two. Adding objects is O(1) for both lists, but is still a lot slower for LinkedLists. Basically, for “small” lists ArrayList will always be faster, but for “large” lists LinkedList is faster. The exact point where you should start using LinkedList also depends on how you use the list, so it’s impossible to give an exact number.
ArrayList is most almost always the best choice for a game object list. Even when you have lots of stuff to remove, ArrayList can be a good choice. A good solution might be to use TWO ArrayLists and pingpong your objects between them. By doing that you can avoid all shifting while still getting fast (and random) access to all objects.
ArrayList<GameObject> currentList, nextList;
//Lists created at load time
//Example game loop:
while(true){
update(); //Updates all objects
render(); //Draws all objects
}
private void update(){
for(int i = 0; i < currentList.size(); i++){
GameObject go = currentList.get(i);
go.update();
if(go.isAlive()){
nextList.add(go);
}
}
//Alive objects are now in nextList. Clear currentList.
currentList.clear();
//Swap current and next list
ArrayList<GameObject> temp = nextList;
nextList = currentList;
currentList = temp;
}
