# ArrayList vs LinkedList

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.

• 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()){
}
}

//Alive objects are now in nextList. Clear currentList.
currentList.clear();

//Swap current and next list
ArrayList<GameObject> temp = nextList;
nextList = currentList;
currentList = temp;
}

``````

Wasn’t memory fragmentation another good reason to avoid LinkedList?

This doesn’t apply with a Mark 'n Sweep GC tough, right? Or does it? ???

I thought about that too. In my tests LinkedLists are slower to traverse. I believe this is because in an ArrayList it can predict all following references and load those from RAM, but in LinkedList only the next reference in the list is known.

Small allocations on a heap lead to fragmentation. Linked lists will (statistically) walk random memory, arraylist will walk linear.

I think I’ve said before that there is almost no actual utility whatsoever for a RAM-based linked list implementation. There is no software problem anyone will encounter that will not be better faster and more efficiently by ArrayList.

Cas

The only usecase I can think of is an extremely long queue (millions of elements) where realtime behaviour is required (ruling out array based queues as they have to grow/shift/compact sooner or later).

It’s very unlikely to have this requirement though.

Free lists of pool allocated items comes to mind (edit: but that’s in-place so linked lists vs. LinkedList).

It does. Mark and sweep is one of the slowest forms of GC, and the more pointers you have to chase, the more time it takes. Java has to do M&S with the tenured generation, whereas it has fast copying collectors for the young generation. The more fragmented your memory gets, the less it’s able to take advantage of cache, and once your app starts paging to disk, the page thrashing can really kill your app (sometimes quite literally)

That’s one of the G1 GC’s strengths apparently - it performs the mark/sweep operation concurrently, and in small chunks, compacting collected stuff into contiguous RAM, which should then in theory make it a bit more cache-friendly next time.

Cas

I have to agree with the fact that we will probably never need something else than an ArrayList for game. I tried inserting integer into an arraylist, always in the middle of the list. And I didn’t got any performance hit before 10000 elements… After that the performance degrade really fast but I don’t think a lot of us are using more than 10000 elements.

Note : With Mark-sweep compact collector there is no fragmentation. I thought Java was using that one instead of Mark-sweep collector for the tenured generation.

@princec : The Concurrent collector is also supposed to do that, but when I tried it the performance were absolutely awful

The concurrent collector performs most of its work concurrently (i.e., while the application is still running) to keep garbage collection pauses short. It is designed for applications with medium- to large-sized data sets for which response time is more important than overall throughput, since the techniques used to minimize pauses can reduce application performance. The concurrent collector is enabled with the option -XX:+UseConcMarkSweepGC.
</off topic>

Just for fun I did some raw microbenchmarks comparing the ways to manage a hypothetical particle or game entity system. Using the sweep-and-copy with ArrayList is approximately 4x faster than LinkedList on its own, and uses less memory. Using iterators slows things down by between 10% and 25%.

However… this was testing with 500,000 entities/particles, and I was getting times of under 1ms for ArrayList and only 4ms for LinkedList. A more realistic sort of scenario with the kinds of games we make round these parts, with maybe 1/100th the number of entities, would mean that the amount of time spent culling entities or particles in a frame would be probably unmeasurable.

Furthermore with just 5,000 entities, we were talking only 2ms using brute force on an ArrayList. And this is for the pathologically unlikely scenario that you’re killing all 5,000 entities in a single frame.

I think this might go back to that fascinating talk given by Jon Blow on making computer games. Please watch it. It is massively significant to how good you will be at making games, or even just software.

Cas

That is certainly going on the ‘watch ASAP’ list. Conversely if you have any more of those little treasures floating around in your bookmarks, don’t hesitate to spam

ONLY THIS. I ams as robots.

Cas

This is worth a quick read IHMO: http://blogs.valvesoftware.com/abrash/valve-how-i-got-here-what-its-like-and-what-im-doing-2/

Generally speaking:

If preserving element order is important and insert/remove before/after operations are common, linked list is much faster at those uses than arrays.
If you want a persistent data structure (in the sense of immutability, not persisting to storage which is another use of the same word), linked lists are ideal.
In most other cases, use arrays.

BTW, you can do O(1) removes on arrays if you can alter element order (swap element with last and remove last)

This is a very elementary, academic subject. I wouldn’t think it is fully in line with this site.

I appreciate what he’s talking about, and when you’re hand-coding the data structures in question then it makes sense to keep it simple.
However, we have access to Java’s wonderful Collections api; so using a HashXYZ is no more effort than using a less complex structure like an ArrayList.

It’s not so much about effort as what’s fastest in what circumstances. LinkedList is an academic curiosity. No-one in their right mind should be using it.

Cas

I tested the performance of several List implementations. I couldn’t decide what to do with collection size vs add/remove frequency, but it was surprising. Frequent adds/removes on relatively small linked-lists-based Lists out performed the same frequency, but large lists were the opposite. I couldn’t find a relationship between size and frequency and did not want to spend time testing and plotting all kinds of possibilities, so I decided it would be too hard to make a meaningful benchmark.

I would not make generalizations on linked lists vs arrays. I would just use Lists in the form `List<Thing> someList = new ListType<Thing>();` and replace the implementation later if needed. In general, you will more likely than not see better performance from ArrayLists than LinkedLists for games on PCs, but that’s not universally true for all hardware (although a real time system is not the usual platform for games) or all applications. I also think it’s naive to use either LinkedList or ArrayLists as an automatic choice of data structure.

Small aside: were you to implement a linked list in the traditional way - with forward and maybe back pointers actually inside the instances you were linking - you would alleviate some of the problems that LinkedList has, which revolve around the need to implement the List interface, and the creation of little bits of potentially long lived support garbage all over the place.

Cas