I will try to answer with examples from JDK, if you do not mind:
Lists:
CopyOnWriteArrayList
is a list that achieves thread-safe usage by recreating backing array each time the list is modified;- Lists returned by
Collections.synchronizedList()
are thread-safe as they include exclusive locking for most operations (iteration over is an exception); ArrayBlockingQueue
. Queue that has a fixed size and blocks when there's nothing to pull out or no space to push in;ConcurrentLinkedQueue
is a lock-free queue based on Michael-Scott algorithm;- Concurrent stack, based on Treiber algorithm. Surprisingly, I didn't find that in JDK;
Sets:
- Sets, returned by factory
Collections.newSetFromMap()
with a backingConcurrentHashMap
. With these sets you can be sure that its iterators is not prone toConcurrentModificationException
, and they use a striping technique for locking it - locking all set is not neccesary to perform some operations. For example, when you want to add element, only the part of the set determined by elementhashCode()
will be locked; ConcurrentSkipListSet
. The thread-safe set based on a Skip List data structure;- Sets, returned by
Collections.synchronizedSet()
. All points written about similar lists are applicable here.
Maps:
ConcurrentHashMap
which I already mentioned and explained. Striping is based on item keys;ConcurrentSkipListMap
. Thread-safe map, based on skip list;- Maps, returned by
Collections.synchronizedMap()
. All points written about similar lists and maps are applicable here.
These were more or less standard data structures intended for multithreaded usage, which should be enough for most practical tasks. I also found some links you may find useful:
- Wait-free red-black tree;
- A huge article about concurrent data structures in general;
- Concurrent structures and synchronization primitives used in .NET;
- Articles about transactional memory - not really a data structure, but since your request serves academic purposes, worth reading;
- One more article about transactional memory - Easy to read, but it is in Russian language. If you can read it, definetely worth reading;