Someone claims `HashMap.get` is "technically O(n) worst case, so it's not really better than a list." Is that a fair characterisation of Java's HashMap? And separately, why does `ArrayDeque` beat `LinkedList` even at inserting into the front — the one thing LinkedList is supposedly built for?

It's technically true that a HashMap bucket can degrade to a linear scan in the worst case, but Java's implementation has bounded how bad that worst case actually is since Java 8: once a single bucket grows past eight entries (in a table with at least 64 slots), that bucket converts from a linked list into a small red-black tree, so lookup there becomes O(log n) instead of O(n). A genuinely pathological key set — a broken hashCode() that returns a constant, or an attacker who can choose keys — degrades the map to "slow" rather than "linear", which is a real and meaningful difference at scale, not a technicality. On ArrayDeque versus LinkedList: the textbook says linked lists are O(1) at insertion, and that's true for both — but ArrayDeque is a circular array where pushing at either end is one array write plus an index update, no allocation at all, while LinkedList has to allocate a new node object and link two pointers for every insertion. One array write beats a node allocation, so ArrayDeque wins even at the operation LinkedList is named for.