Asking this question with C# tag, but if it is possible, it should be possible in any language.
Is it possible to implement a doubly linked list using Interlocked operations to provide no-wait locking? I would want to insert, add and remove, and clear without waiting.
I don't believe this is possible, since you're having to set multiple references in one shot, and the interlocked operations are limited in their power.
For example, take the add operation - if you're inserting node B between A and C, you need to set B->next, B->prev, A->next, and C->prev in one atomic operation. Interlocked can't handle that. Presetting B's elements doesn't even help, because another thread could decide to do an insert while you're preparing "B".
I'd focus more on getting the locking as fine-grained as possible in this case, not trying to eliminate it.
I would say that the answer is a very deeply qualified "yes, it is possible, but hard". To implement what you're asking for, you'd basically need something that would compile the operations together to ensure no collisions; as such, it would be very hard to create a general implementation for that purpose, and it would still have some significant limitations. It would probably be simpler to create a specific implementation tailored to the precise needs, and even then, it wouldn't be "simple" by any means.
A simple google search will reveal many lock-free doubly linked list papers.
However, they are based on atomic CAS (compare and swap).
I don't know how atomic the operations in C# are, but according to this website
http://www.albahari.com/threading/part4.aspx
C# operations are only guaranteed to be atomic for reading and writing a 32bit field. No mention of CAS.
Here is a paper which discribes a lock free doublly linked list.
We present an efficient and practical lock-free implementation of a concurrent deque that is disjoint-parallel accessible and uses atomic primitives which are available in modern computer systems. Previously known lock-free algorithms of deques are either based on non-available atomic synchronization primitives, only implement a subset of the functionality, or are not designed for disjoint accesses. Our algorithm is based on a doubly linked list, and only requires single-word compare-and-swap...
Ross Bencina has some really good links I just found with numerious papers and source code excamples for "Some notes on lock-free and wait-free algorithms".
FWIW, .NET 4.0 is adding a ConcurrentLinkedList, a threadsafe doubly linked list in the System.Collections.Concurrent namespace. You can read the documentation or the blog post describing it.
What I've seen so far here are papers which demonstrate the implementation of a double-ended queue without locks, not the implementation of a general doubly-linked list. The former only supports operations on the ends of the list, where the latter must allow insertions and deletions from the middle.
It seems to me that a general doubly-linked list is possible, depending on what kind of consistency you're looking for. I can think of two relevant levels of consistency right off:
Everybody sees the same list all the time.
This is the highest level of consistency you can seek, because it forbids any discrepancy between, say, a forward-reader and a backward-reader. I cannot find a paper which implements this without locking for a doubly-linked list. Singly-linked implementations are out there.
Every traversal of the list is successful.
There are two pointers in a doubly-linked node: next and previous. One of these may be safely removed at a time using only non-lock primitives, just like a singly-linked list. Swapping both of the pointers atomically is not supported on any common multicore architecture (as noted here).
Basically, this second level of consistency is made by treating a doubly-linked list as two related singly-linked lists. By removing just one pointer at a time, you may keep the list consistent for all readers in a particular direction. If it's okay for forward-readers and backward-readers to occasionally see a slightly different list, then this will totally work.
This does make some assumptions about how nodes are de-allocated. It would be very easy, in an explicit-deallocation memory system, to delete a node which is currently being iterated through in a different thread. I think garbage-collected environments would be fine.
It's relatively (lock-free stuff is all complex) to implement an add-only doubly linked list. You can prolly extend it easily to being able to logically delete elements - just they won't be actually physically deleted, not until the whole list is deleted.
That might be enough for you.