A huge takeaway from these slides is the lack of needed locks to properly protect a linked list. It is easy to think that the best solution is to lock the entire list, and thus only allow a single thread to work on any part of the linked list at once. However, it we think further, we notice that as long as the index we are working with, and that directly previous, we do not run into any issues of losing data or potential breaks in our list. The analogy here of hand-over-hand, such as monkey bars is helpful in envisioning the use of this. Especially as we consider multiple people on monkey bars but never holding the same rung.

Often when I'm programming, I see a solution that involves one lock (or mutex) per element in an array, linked list, etc., but reject that solution out of pocket because it feels far too complicated. I guess this example validates that it isn't unreasonable to have a lock for every element in some data structure.

When thread 0 is deleting 11, it needs to know the next node after 11, so that it can update 5's next pointer to point to 18. While the deletion is happening, it needs to make sure that no other thread is deleting 18. Otherwise, 5's next pointer will point to an invalid value.

However, thread 0 DOES NOT need a lock on 18 (the next node) because, in our hand-over-hand locking scheme, if any other thread wants to delete 18, it must hold the lock on the prev and curr nodes (10 and 18 respectively). Since thread 0 already holds the lock on 10, it can be sure that no other thread will be able to delete 18.

While this solution works, I'm concerned with how basically if you had a really long linked list and some inserts/delete were happening relatively early in the list, while you could have parallelized traversal through the long list, the thread is actually stuck near the beginning since locks are being held there. Basically what if the future operations from other threads require to traverse beyond where another thread is currently locking at. I'm not sure but would it actually be necessary to lock along the way while traversing or can you just traverse normally as if it were a normal linked list until you reach the point you need to start locking? If we're taking the monkey bar analogy, it seems that one thread can easily bottleneck all other threads if their operations are way further down the list.

@derrick. Your understanding is correct. This is one example, where a transactional solution, or a lock-free solution, as opposed to a lock-based solution, might shine.