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!
Add me on Discord!

©2026 Jordan Malek