Compare ArrayList, LinkedList and HashMap.
- ArrayList: array-backed, O(1) random access, amortised O(1) append, O(n) insertion/removal in the middle. Best default for ordered lists.
- LinkedList: doubly linked, O(1) insertion/removal at the ends or given a node, O(n) random access and poor cache locality. Rarely the best choice in practice; ArrayDeque is preferred for queues.
- HashMap: hash table with average O(1) get/put, no ordering guarantee, one null key allowed. Collisions are handled with buckets that treeify to red-black trees past a threshold. Use LinkedHashMap for insertion order and TreeMap for sorted keys.
Other essentials: HashSet is a HashMap key set; ConcurrentHashMap for thread-safe maps; choose initial capacity and load factor to avoid rehashing.