The code from last slide is deadlock free because every thread at every step would acquire a lock for the new cur and relinquish lock for the old prev. No thread can proceed past another thread in the list if it is behind another thread (they might acquire the same lock and only one (the one near the end of the list) would proceed).

I think the last bullet point here is referring to having locks for subsequences, such that maybe a lock protects a sequence of 10, or 100, nodes. This reduces overhead, at the cost of some parallelism. I comment as I wanted to add that this notion also seems to gel really well with something like a skip-list, which in practice are quite often implemented in this kind of way anyway. We could have locks associated with nodes at certain levels, protecting that subsequence. This also would stop late inserts from getting caught up behind early inserts... But it does seem like there would be at least a little non-trivial work getting that up and running.

Are there any other issues with having fine-grained locking or locks for every node in the list? Implementation without deadlocking is more difficult, but is there difficulty due to extensive overhead?

I was wondering ever sense taking fine-grained locking's hand over hand linked-list traversal what's the point of of locking all the previous threads that try to access the linked list and why couldn't we just let every thread lock the element it wants and the one after and before but now I finally realize that would introduce deadlock into the program. I think the point of hand over hand locking traversal is avoiding deadlock with the cost of decreased parallelism. Since if we made every thread just try to lock the element it wants to access and the one before it and after it then it's possible a thread 0 that wants to alter curr could lock prev and curr while another thread 1 that wants to access next could lock next and it won't be able to lock curr since thread 0 locked it and both 0 and 1 will have to wait for the other but neither can advance without the other so we'll reach deadlock. But in a hand over hand traversal we force some serialization between threads so it will be impossible for thread 1 to lock next while thread 0 locked curr and prev, additionally we see that we don't need to lock next since the only way next could be altered is if curr is locked as well but we control the lock of curr.