Design a Thread-Safe Linked List with Lock Coupling

Implement a linked-list abstraction supporting concurrent insert, delete, and read operations. Discuss node-level locking, hand-over-hand traversal, sentinel nodes, contention, and safe access to removed nodes. ### Clarifying Questions The exact list API, key ordering, duplicate semantics, and memory-management model are not specified. For a concrete design, use a sorted set of unique comparable keys with insert(key), delete(key), and contains(key) as the read operation. Treat that as a practice choice, not the only meaning of the reported API. State whether removed nodes are reclaimed manually or by managed memory. ### What a Strong Answer Covers A clear lock order, a traversal that never uses an unprotected link, linearization points, atomic membership changes, and a memory-reclamation argument. Explain the limits of lock coupling under high contention. ### Follow-up Questions - Why does unlinking a node not automatically make it safe to free? - What changes if read must return a snapshot of the entire list?