Method and apparatus for performing lock-free updates in a linked list

One embodiment of the present invention provides a system that performs a lock-free update to one or more fields in an existing node in a linked list. To perform the update, the system first obtains a new node to be added to the linked list, wherein other processes do not possess references to the new node and therefore cannot initially access the new node. Next, the system copies a snapshot of the existing node to the new node, and then updates one or more fields in the new node that correspond to the one or more fields in the existing node. Next, in a single atomic operation the system modifies a next pointer of the existing node to point to the new node and also marks the next pointer to indicate that the existing node is deleted. In this way, the new node becomes part of the linked list and the existing node is deleted in a single atomic operation.