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?

  • What's wrong with the good old linked list? Jan 18 '18 at 0:40
  • Why remove them from the queue when they leave? At worst, the connection attempt will fail if they aren’t there anymore, and you will simply move on to the next item in the queue. Jan 18 '18 at 0:44
  • 1
    Use a queue, but if you identify a user that's returning, simply let them stand in the same place in line. Jan 18 '18 at 1:22
  • 2
    Have you actually encountered a noticeable performance problem doing whatever you're already doing? If not, how many users so you realistically expect in the queue at any given time? How many of which operations will you need to preform in what interval?
    – svidgen
    Jan 18 '18 at 1:40
  • 1
    Also, why can only one user at a time access this resource? That sounds like a bigger problem that needs addressing. Jan 18 '18 at 3:55

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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