Here is something interesting I read from the blog post. When we are inserting and deleting a node in a lock-free algorithm, we may use new() and delete() to allocate and free a node. However, they are not lock-free library calls. So, it does not make sense if a lock-free algorithm calls functions that use locks. One way to fix this is to initialize a bunch of nodes in the beginning, and recycle the nodes instead of keep allocating and freeing them.

http://blog.memsql.com/common-pitfalls-in-writing-lock-free-algorithms/