Best Data Structure for ordered list of connected users

Question

I have three attributes for a user: connectionId (e.g. "sd4-h4sdg-u4j-a2rr3"), userName, and placeInLine.

I can't think of a single data structure that will handle my scenario of only allowing a single user to work on a given webpage resource and advancing the line of people as each active user leaves their connection. I am using C# / SignalR with jQuery.

When a user (Adam) hits the page, if this proposed data structure is empty, they get to interact with the page. The next user who comes along (Bob) while Adam is working gets put in line. So we store his userName, connectionId, and place in line as 1. Carl comes along and gets put in line as well, getting placeInLine=2. David is 3, etc.

Now, in a perfect world, everyone would wait patiently for their turn, and get prompted when the user in front of them disconnects so they can have their turn on the page. In this scenario, a Queue would work. However: If Carl leaves, we cannot simply remove him from the Queue since he is in the middle [B, C, D]. I want this code to scale so rebuilding a queue with each change is not an option.

If I were using a Dictionary, I could have the userName as the key, with a value of the placeInLine. But in this scenario, I cannot get the next user, since Get() happens via Key. If the placeInLine int is the key, I cannot remove a user based on username since Remove() is also done by key.

Am I naive for assuming this should be possible with a single data structure?

Answer 1

What you choose might depend on the particular load you anticipate.

But, I'd start with a simple Queue. Possibly extended with a naive O(n) complexity Remove(item). Or, use a Dictionary or Map to index "removed" users. As you pop() items out of the Queue, just ignore "removed" users and re-pop().

You could potentially micro-optimize further, but, I'm already skeptical that the complexity of adding an index is a necessary optimization. I wouldn't likely fuss about unless I had strong evidence that the n in my O(n) Remove() method will be significant.