Lock-Free Linked Lists
Let's consider a classical singly linked list.
Here are the steps to insert a node, B, between two consecutive nodes, A and C, that are already in the list:
- First, you traverse up to A, which will immediately precede B in the list.
- Next, you update the next-pointer of B to point to C, which will immediately follow B in the list.
- Finally, you update the node that will precede the new node to point to the new node.
Here are the steps to remove a node, B, that immediately follows A and immediately precedes C:
- You traverse to B.
- You update the node immediately preceding it, A, to point to the node immediately following it, C.

