Lists

Array (code)

A resizable, ordered or unordered array of objects. It often replaces ArrayList. It provides direct access to the backing array, which can be of a specific type rather than just Object[]. It can also be unordered, acting like a bag/multiset. In this case, a memory copy is avoided when removing elements (the last element is moved to the removed element’s position).

The iterator returned by iterator() is always the same instance, allowing the Array to be used with the enhanced for-each (for( : )) syntax without creating garbage. Note however that this differs from most iterable collections! It cannot be used in nested loops, else it will cause hard to find bugs.

Primitive lists

These are identical to Array except they use primitive types instead of objects. This avoids boxing and unboxing.

Specialized lists

SnapshotArray (code)

This is identical to Array except it guarantees that array entries provided by begin(), between indexes 0 and the size at the time begin was called, will not be modified until end() is called. This can be used to avoid concurrent modification. It requires iteration to be done a specific way:

SnapshotArray array = new SnapshotArray();
// ...
Object[] items = array.begin();
for (int i = 0, n = array.size; i < n; i++) {
    Object item = items[i];
    // ...
}
array.end();

If any code inside begin() and end() would modify the SnapshotArray, the internal backing array is copied so that the array being iterated over is not modified. The extra backing array created when this occurs is kept so it can be reused if a concurrent modification occurs again in the future.

DelayedRemovalArray (code)

This is identical to Array except any removals done after begin() is called are queued and only occur once end() is called. This can be used to avoid concurrent modification. Note that code using this type of list must be aware that removed items are not actually removed immediately. Because of this, often !SnapshotArray is easier to use.

PooledLinkedList (code)

A simple linked list that pools its nodes.

SortedIntList (code)

A sorted double linked list which uses ints for indexing.

Maps

ObjectMap (code)

An unordered map. This implementation is a cuckoo hash map using three hashes, random walking, and a small stash for problematic keys. Null keys are not allowed, null values are. No allocation is done except when growing the table size.

Keys may only be in one of three locations in the backing array, allowing this map to perform very fast get, containsKey, and remove. Put can be a bit slower, depending on hash collisions. Load factors greater than 0.91 greatly increase the chances the map will have to rehash to the next higher POT backing array size.

Primitive maps

These maps are identical to ObjectMap except they use primitive types for the keys, except ObjectIntMapand ObjectFloatMap which use primitive values. This avoids boxing and unboxing.

Specialized maps

OrderedMap (code)

This map is identical to ObjectMap except keys are also stored in an Array. This adds overhead to put and remove but provides ordered iteration. The key Array can be sorted directly to change the iteration order.

IdentityMap (code)

This map is identical to ObjectMap except keys are compared using identity comparison (== instead of .equals()).

ArrayMap (code)

This map uses arrays for both the keys and values. This means get does a comparison for each key in the map, but provides fast, ordered iteration and entries can be looked up by index.

Sets

ObjectSet (code)

Exactly like ObjectMap, except only keys are stored. No values are stored for each key.

Primitive sets

IntSet (code)

These maps are identical to ObjectSet except they use primitive types for the keys. This avoids boxing and unboxing.

Other collections

BinaryHeap (code)

A binary heap. Can be a min-heap or a max-heap.

Benchmarks

The benchmark below shows the difference between array and hashtable lookup (.contains() or .get()) using libGDX collection methods. If you have less than 1024 elements in a list, you shouldn’t bother whether you’re using arrays or hashtables (Maps or Sets). Mind the fact that hashtables have significantly slower iteration than arrays and cannot be ordered.

                  array.size         GdxArray.contains()     GdxObjectSet.contains()
                           2                         0ms                         0ms
                           4                         0ms                         0ms
                           8                         0ms                         1ms
                          16                         0ms                         1ms
                          32                         0ms                         0ms
                          64                         0ms                         0ms
                         128                         0ms                         0ms
                         256                         1ms                         0ms
                         512                         1ms                         0ms
                        1024                         2ms                         0ms
                        2048                         4ms                         0ms
                        4096                        11ms                         0ms
                        8192                        22ms                         0ms
                       16384                        80ms                         0ms
                       32768                       112ms                         0ms
                       65536                       403ms                         0ms
                      131072                       615ms                         1ms

Collections