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.
Contact me here!
Check out my Github!
Check out my LinkedIn!

©2025 Jordan Malek