Practical choices

Default to ArrayList. It has O(1) indexed access, amortised O(1) append, 4 bytes per element reference and contiguous storage. LinkedList offers O(1) insertion at a node you already hold, but you rarely hold one; finding the position costs O(n) and each element costs a 24-byte node. In practice ArrayList wins even for many insertions in the middle, because shifting a contiguous array is very fast.

Reach for LinkedList only when you need null-friendly queue/deque methods and do not mind the cost, and even then ArrayDeque is usually better. Compare element access in the animation.

1static int getFromArray(int[] arr, int k) {
2    return arr[k];                      // address = base + k * 4: one memory read
3}
4
5static int getFromList(Node head, int k) {
6    Node cur = head;
7    for (int i = 0; i < k; i++) {
8        cur = cur.next;                 // pointer chase: one read per hop
9    }
10    return cur.value;
11}

Use HashMap when you only look keys up: O(1) expected, smaller, faster. Use TreeMap when you need sorted iteration or order queries: firstKey, floorKey, ceilingKey, subMap, headMap. LinkedHashMap is the third choice: hash speed plus predictable insertion (or access) order.

The key requirements differ: HashMap needs hashCode and equals; TreeMap needs Comparable keys or a Comparator, and treats two keys as the same when the comparison returns 0.

1static void choose() {
2    Map<String, Integer> lookup = new HashMap<>();             // only exact lookups
3    TreeMap<Integer, String> schedule = new TreeMap<>();       // need "the next event at or after t"
4    schedule.put(900, "standup"); schedule.put(1400, "review");
5    System.out.println(schedule.ceilingEntry(1000).getValue()); // review
6}

The same split applies to sets. HashSet for membership and duplicate removal; TreeSet when elements must come out sorted or you need first, last, floor, ceiling and range views; LinkedHashSet when insertion order must be preserved.

A TreeSet uses the comparator, not equals, to detect duplicates. With a comparator that compares only string length, "aa" and "bb" are the same element and the second add is ignored: the set printed [c, aa] after adding aa, bb and c.

1static void comparatorDecidesDuplicates() {
2    TreeSet<String> byLength = new TreeSet<>(Comparator.comparing(String::length));
3    byLength.add("aa"); byLength.add("bb"); byLength.add("c");
4    System.out.println(byLength);                                // [c, aa]: "bb" compared equal to "aa"
5}

java.util.Stack is a legacy class: it extends Vector, so every method is synchronised (needless locking), it exposes list operations such as get(i) and add(i, x) that break the stack abstraction, and its iteration order is bottom to top. Use ArrayDeque through the Deque interface instead: push, pop and peek work at the front, it is faster and smaller, and it does not pretend to be a list.

One visible difference: after pushing 1, 2, 3, Stack prints [1, 2, 3] (bottom to top) while ArrayDeque prints [3, 2, 1] (top first). Both peek() the value 3. Stack.pop() on an empty stack throws EmptyStackException; ArrayDeque.pop() throws NoSuchElementException.

1static void stacks() {
2    Deque<Integer> stack = new ArrayDeque<>();
3    stack.push(1); stack.push(2); stack.push(3);
4    System.out.println(stack + " " + stack.peek());              // [3, 2, 1] 3
5    int top = stack.pop();                                        // 3; pop() on an empty deque throws NoSuchElementException
6}

A PriorityQueue and a TreeMap both give you the smallest element quickly, but they are different tools. The heap does exactly one thing: peek the best element in O(1) and poll it in O(log n); it has the smallest overhead of the two (an array, 4 bytes per slot plus the element). The tree does everything the heap does and more (any element can be removed in O(log n), and floor, ceiling and ranges work), at the price of 40-byte entries and O(log n) for the minimum.

Rule of thumb: if you only ever take the minimum or maximum (top-k, scheduling, merging sorted lists, Dijkstra), use a PriorityQueue. If you also need to remove or update arbitrary elements, look up by key, or ask about neighbours and ranges, use a TreeMap/TreeSet.

1Comparator<Integer> cmp = Comparator.naturalOrder();   // Comparator.reverseOrder() makes a max-queue
2PriorityQueue<Integer> pq = new PriorityQueue<>(cmp);
3pq.offer(x);              // append at the end, then sift up
4Integer top = pq.poll();  // last element to the root, then sift down
5Integer next = pq.peek(); // the root only; nothing is removed