- Backed by array (which are co-located in memory), thus fast iteration and get(i) operation.
- Slow inserts when the backed array is full and has to double in size.
- Fail-fast iterators, which can throw ConcurrentModificationException.
- Add is O(n) - When element is added to middle of list, all elements on the right have to be moved.
- Use Case - When iterations outnumber number of read/writes.
- Chain of nodes referencing each other (doubly linked list).
- No co-location of nodes, pointers need to be chased for next element, thus slow iterations and get(i) operation.
- Fail-fast iterators, which can throw ConcurrentModificationException.
- Implements Queue interface, thus allows offer/pop/peek operations.
- Add is O(1) - Adding element in middle of list is just adjusting the node pointers.
- Internally uses references (~ to skiplist) to optimize iterations.
- Use Case - Lot of inserts in middle of the list.
| Operation | ArrayList | LinkedList |
|---|---|---|
| get(i) | O(1) | O(n) |
| add() | O(1) amortized | O(1) |
| remove(i) | O(n) Remove and move all elements | O(n) Iterate then remove |
| iterator.remove | O(n) | O(1) |
- For stack operations push/pop/peek.
- Not used anymore. Recommended to use Deque implementations.
- Synchronized version of list.
- Not used anymore. Recommended below mentioned alternatives.
- Thread-safe.
- Backed array is copied during every element insert.
- Avoids ConcurrentModificationException since iteration can continue in original copy, and insert results in new copy.
- High memory usage (more pressure on GC) due to the resulting copies.
- Use case - Large number of threads for read, low number of writes.
- Thread-safe.
- Can be slow due to mutual exclusion.
- Iterations have to be externally synchronized by developer
- Can throw ConcurrentModificationException if (above mentioned) synchronization not done during iteration.
Collection of unique elements. No duplicates.
- Backed by HashMap.
- Performance can vary based on hashCode implementation.
- Constant time get/remove/add/contains (subject to above point).
- Fail-fast iterators.
- Insertion order not retained.
- Insertion order is retained.
- Uses doubly-linked list to maintain the order.
- Iteration can be slower due to this.
- Other features, same as HashSet above (except iteration)
- Elements sorted by their natural order (or Comparator passed in constructor).
- Log(n) time for add/remove/contains operations.
- Navigable (floor, ceiling, higher, lower, headSet, tailSet operations).
- Fail fast iterators.
- Thread-safe.
- Log(n) time for add/remove/contains operations.
- Navigable (floor, ceiling, higher, lower, headSet, tailSet operations).
- Size method is not constant time operation.
- Weakly consistent iterators (do not throw ConcurrentModificationException but also may not reflect concurrently added items).
- Thus, bulk operations (addAll, removeAll, retainAll, containsAll etc) are not guaranteed to be atomic.
- Backed by CopyOnWriteArrayList
- Thread-safe.
- Slow. Operations have to iterate through the array for most operations.
- Recommended where reads vastly outnumber writes and set size is small.
- To be used with Enum types.
- Very efficient and fast (backed by bit-vectors).
- Weakly consistent iterators.
- Nulls not allowed.
- key, value pairs.
- Permits a null key, and null values.
- Iteration order not guaranteed.
- Throws ConcurrentModificationException.
- Article detailing implementation.
- Backed by array (buckets), array-size is known as table-size.
- Position in array = element-hash % table-size.
- If elements end up in same bucket, they are added to linked-list (or a balanced red-black tree).
- O(1) access (if hashcode properly distributes the values, else O(n) for linked-list & O(log(n)) for tree.
- Load factor - 0.75 default, decides when table-size should increase (double).
- Bigger load-factor - more space-efficient, reduced speed (due to more elements in same bucket).
- Lower load-factor - less space-efficient, more speed (less, ideally 1 element in 1 bucket).
- Initial table-size = 16.
- Insertion order is retained.
- Thread-safe.
- Not used anymore, ConcurrentHashMap recommended.
- Thread-safe.
- Fine grained locking called striped locking (map is divided into segments, each with associated lock. Threads holding different locks don't conflict).
- Improved performance over Hashtable.
- Sorted by keys.
- Uses Red-Black tree implementation.
- Thread-safe version of TreeMap.
- Navigable (floor, ceiling, higher, lower, headSet, tailSet operations).
- Implements Queue interface.
- offer, peek, poll operations.
- Use case - task queues
- Thread-safe.
- Backed by array. Thus bounded in size.
- Adding element to full queue results in blocking.
- Polling an empty queue results in blocking.
- Use case - Producer consumer problem.
- Thread-safe.
- Backed by linked-list.
- Optionally bounded in size. Takes maxSize as constructor argument.
- Thread-safe.
- Uses CAS (Compare-And-Swap) for more throughput. Also known as lock free.
- ArrayDeque - Double ended queue. Backed by array. Can throw ConcurrentModificationException.
- LinkedList - Implements Deque interface.
- LinkedBlockingDeque
- ConcurrentLinkedDeque
- Elements sorted based on their natural order (or Comparator provided in Constructor).
- Use case - task queues where tasks can have different priorities.
- Thread-safe.
- Elements added, are available to be removed only after their delay-time is expired.
- Holds single elements.
- Blocks for both producer and consumer to arrive.
- Use case - For safe/atomic transfer of objects between threads.
- equals required for all collections.
- equals and hashCode required for Maps and Sets (which are backed by Maps).
- sort(list, key) - guarantees stable sort
- reverse
- reverseOrder - returns Comparator for reversed order
- shuffle
- rotate(list, distance) - rotates elements by the distance specified
- binarySearch(list, key)
- list should be sorted else can get unpredictable results
- log(n) if list implements RandomAccess, else O(n)
- RandomAccess - Marker interface that says, collection supports fast random access, get(i). Typically backed by arrays.
- empty - emptyList, emptySet, emptyMap etc.
- synchronized - synchronizedList, synchronizedSet, synchronizedMap etc.
- unmodifiable - unmodifiableList, unmodifiableSet, unmodifiableMap etc.
- singleton(t) - singleton (returns set), singletonList, singletonMap etc.
