The big picture

ArrayList

• Backed by an array.
• Default initial capacity is 10.
• When full, grow 50% of its capacity.
• Inserting or removing an element in the middle is O(n).
• Random access is O(1).
• Not thread-safe.
• Source code and API

LinkedList

• Backed by a double linked list.
• Inserting or removing an element in the middle is O(1).
• Random access is O(n).
• Not thread-safe.
• Source code and API

Vector

• Same as ArrayList, but thread-safe.
• When full, double its capacity.
• Source code and API

ArrayDeque

• Backed by an array.
• Inserting or removing an element at head or tail is O(1).
• When full, double its capacity.
• Source code and API

PriorityQueue

• Backed by a balanced binary heap, which is implemented as an array.
• Should provide a comparator. Otherwise, natural ordering will be used.
• Default initial capacity is 11.
• When full, double size if small (< 64); else grow by 50%.
• Inserting any element or removing the smallest element is O(log(n)).
• Not thread-safe. Use PriorityBlockingQueue for thread-safety.
• Source code and API

TreeSet

• Backed by a red-black tree, so the data is already sorted.
• Should provide a comparator. Otherwise, natural ordering will be used.
• No duplicates.
• Inserting, removing, or locating an element is O(log(n)).
• Not thread-safe.
• Source code and API

TreeMap

• A key-value pair store.
• Backed by a red-black tree, so the data is already sorted.
• Allow NULL keys but not NULL values.
• Inserting, locating, or removing or locating an element is O(log(n)).
• Not thread-safe.
• Source code and API

HashMap

• A key-value pair store.
• Backed by an array of linked lists ("binned (bucketed) hash table"), as in this picture.
• No duplicate keys.
• Inserting an element is O(1) in the best case and O(n) in the worst case (because it needs to check for duplicate keys before insertion). But if the capacity exceeds the loading factor, the hash table will be expanded and all existing elements will be re-hashed.
• Removing or locating an element is O(1) in the best case and O(n) in the worst case.
• Not thread-safe. Use Hashtable or ConcurrentHashMap for thread-safety (but Hashtable does not allow NULL keys or values).
• Source code and API

HashSet

• Backed by HashMap.
• Not thread-safe.
• Source code and API

LinkedHashMap

• Backed by HashMap, but also has a double linked list, so one can iterate in the order in which the entries were put into it.
• LinkedHashMap can be used to implement a Cache object by overriding the removeEldestEntry() method. This lets you create a Cache object that can expire data using some criteria that you define.
• Source code and API

CopyOnWriteArrayList

• Backed by an ArrayList.
• A copy of the underlying ArrayList is created first, and mutation operation (e.g. add or set) is applied.
• Suitable for concurrent write-intensive situations.
• Source code and API

ConcurrentSkipListMap

• Backed by a skip list, so the data is already sorted.
• Inserting, removing, or locating an element is O(log(n)).
• ConcurrentSkipListMap is lock-free.
• The size() method is not a constant-time operation.
• Source code and API