I'm looking to implement a collection that needs to support only two operations:

  1. AddOrUpdate: Insert item into collection if it doesn't exist; otherwise, move it from whatever the current position is to the head of the list
  2. Enumerate: Enumerate items in the order they were inserted/updated in

Any type of delete operation is not quired for now.

There will be a single writer thread. Writing must be O(1) and wait-free - optimising for write speed is key here.

There will be multiple reader threads.

  • Read efficiency is slightly less crucial, so having overhead here is more tolerable.
  • Once a reader acquires an enumerator, it must be able to enumerate the items in the collection in the same order as it was at the exact time the enumerator was acquired. Subsequent changes to the collection must not impact the enumerator's items or their order
    • Example: Say an int collection is currently [1,2,3], and an enumerator is acquired
    • Shortly thereafter, a writer thread pushes 3 to the front, so the collection in its latest state is now [3,1,2]
    • The previously acquired enumerator must still enumerate items in the same order as it was at the time it was acquired, i.e. [1,2,3]
  • Assume that these enumerators can and will be deterministically disposed of when done

I'm specifically looking to implement this in C#, so general efficiency must take GC into account.

Is there any known data structure that would seem to fit this bill very well? Does anyone have any thoughts on an efficient implementation, otherwise?

My general thought so far has been a structure roughly:

  1. Maintain a Map<T, Node>, simply for O(1) retrieval of existing items
  2. Maintain the data as a relatively plain either single or double linked list with a node structure roughly as follows:
class Node<T>
   public readonly T Item;
   public readonly ulong Version;
   public Node<T>? Next;
   public ulong LastIncludedVersion

Inserting a new value should be trivial - just replace the head node, and set the new head's version to the prior head's version + 1.

Moving an existing value of the front could then be done by

  1. Finding the node-to-be-moved, then setting its LastIncludedVersion to current head + 1
  2. Cloning and re-inserting the node as the new head

Enumerators could then grab a hold of the head node, and start enumerating; if they encounter any node whose LastIncludedVersion is < the version of the head node they got, they can omit it.

I believe this should work, but it leaves the big issue of: Who, what or when do we remove nodes who've been marked for deletion (i.e. have LastIncludedVersion set)?

Generally, my hunch would be to leave it up to readers; when an enumerator is created, it inserts its head version into some shared ordered set. When it's done enumerating, it removes itself again from this yet, and then enumerates the entire list again, removing any node for good whose LastIncludedVersion is smaller than the minimum head version of all active readers.

The problem of course is.. that would be horribly inefficient. If there are no pending removals, an enumerator would still need to enumerate the entire list again for no good reason.

Maybe I can tweak this part to be more efficient - but I'm curious to hear if there are any more elegant approaches.

  • $\begingroup$ I haven't found any existing structure that fits this bill yet - do you know any specific collections from python or java that might? The closest I've found were concurrent linked lists, but typically they seem to have no coherent "move existing item to front" operations - only separate delete and insert $\endgroup$
    – Bogey
    Commented Apr 26 at 16:35
  • $\begingroup$ I'm confused what "in the order they were inserted/updated in" means. Do you mean, in the order they currently are in the list? Or do you have to go based on the order in which the item was originally inserted, even though it has since been moved to the front? Can you state the behavior of Enumerate more clearly? $\endgroup$
    – D.W.
    Commented Apr 26 at 19:35
  • $\begingroup$ We require questions to state the requirements in a way that any reader can know what answers will be acceptable, any answerer can know whether you will consider a candidate answer to be acceptable, and every voter will know how to evaluate answers. It's not clear to me how answers should be evaluated, and specifically, what the running time requirements are for reading and writing. Do you want $O(1)$ time writing? $O(\log n)$ time? "Blazing fast" is not very clear. It's not clear how slow reading can be. I have a candidate answer in mind but I can't tell if it'll be acceptable. $\endgroup$
    – D.W.
    Commented Apr 26 at 19:45
  • $\begingroup$ Maybe something similar to CopyOnWriteArrayList will do this for you? $\endgroup$
    – Russel
    Commented Apr 27 at 0:27
  • $\begingroup$ @Russel Thanks - unfortunately, a CopyOnWriteArrayList would invert the performance characteristics I'm looking for, i.e. this and similar (eg persistent) types of collections are fast to read, but slow to write $\endgroup$
    – Bogey
    Commented Apr 27 at 14:51

1 Answer 1


There is a trivial way to achieve $O(1)$, wait-free writes: use an append-only, log-structured data structure. Specifically, have an append-only linked list of AddOrUpdate log records.

Each time the caller invokes AddOrUpdate, you just append a log record containing the parameter to AddOrUpdate (the item that was added/updated).

Each time the caller invokes Enumerate, you stash a pointer to the current log head, then walk the entire list to build up the answer to the Enumerate operation (e.g., maintaining a list and moving items to the front as you read each log record), stopping when you reach the stashed pointer.

This will achieve $O(1)$ time writes and $O(N)$ time reads.

Of course, this is a rather trivial and silly solution. But it could be the foundation for an optimized version of this data structure. For instance, each time an Enumerate operation finishes, you can replace the entire log up to the stashed pointer with the collection built up by the Enumerate operation, and do an atomic compare-and-swap to change the head of the log to point to this collection followed by log entries starting at the stashed pointer. This can all be implemented in a way that supports multi-threading and ensures writes remain wait-free.

See also log-structured filesystems.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.