6
$\begingroup$

Well, it's not exactly a queue if it allows for random reads. This question is about a data structure which behaves like a queue for insertions and a sorted dictionary for reads.

Imagine an algorithm that maintains a list of elements so that:

  1. It reads an element from the list based on its key.
  2. It then inserts that element as the last element in the list.
  3. On demand it returns all entities in the order in which they were inserted.

And I am looking for a solution that is faster than a naive implementation based on a linked list, which would have complexity O(n) for all three parameters - search, insert as the last element, and return all elements in the inserted order.

Such a data structure should probably:

  1. Allow for a quick lookup of the key (e.g. a tree, a hashmap)
  2. Maintain the order in which elements were inserted (e.g. a list, a queue)

A practical example is a list of agents receiving calls. When an agent is called, it's fetched from the list, and when it finishes the call, it's put at the back of the list. Therefore the agent that is first in that list is the most idle agent (waiting for a call the longest). In other words, the list would be sorted according to agent's idleness.


Another example implementation could be based on two structures, one dictionary and one array, referencing each other. The dictionary would keep the index in the array as the value and the array would keep the key as the value. Then the element would be removed from the array by looking up the value/index in the dictionary and the dictionary would be updated with the new index once the element was put as the last element in the array.

$\endgroup$
8
$\begingroup$

Take any dictionary data structure and link its entries in whichever order suits you. In essence, you retain the $\Theta$-costs from the basic structure.

In search trees, this is called threading. It gives you constant-time access to the first and last element, respectively, and maintaining the threading takes only constant-time overhead for each dictionary or queue operation. As a consequence, you get $\Theta(\log n)$ access by key, $O(1)$ access to front and back of the queue (without modification), and $\Theta(\log n)$ insertion and deletion.

If you use hashtables you get $O(1)$/$\Theta(n)$ (AC/WC) access by key, $O(1)$ access to front and back of the queue (without modification), and $O(1)$/$\Theta(n)$ (AC/WC) insertion and deletion. The usual caveats apply.

$\endgroup$
  • $\begingroup$ How the deletion can be O(1)/Θ(n) or Θ(logn) if I need to find the element that is being moved to the back of the queue, and for a double-linked list that is always Θ(n)? Also, why does it have to be a double-linked list and not a single-linked list? $\endgroup$ – Amiramix Nov 1 '16 at 20:28
  • $\begingroup$ @Amiramix 1) The queue property is trivial to maintain using references to the first and last entry. 2) Single-linked may be enough depending on your needs, yes. $\endgroup$ – Raphael Nov 1 '16 at 20:32
  • $\begingroup$ The requirement is that I can pick any element from the data structure when moving it to end of the list, not only the first or the last. I agree that lookup will be quick but removing it from the linked list and putting it at the back of that list will be O(n) unless I am missing something? $\endgroup$ – Amiramix Nov 1 '16 at 20:36
  • $\begingroup$ @Amiramix Yes. You are missing than removing things from a linked list is possible in constant time (if you have a pointer to the element, which we have here) and that adding things to the end is possible in constant time, as well (if you have a a pointer to the end, which we have here). I recommend you implement what I propose and see for yourself. $\endgroup$ – Raphael Nov 1 '16 at 21:21
  • 2
    $\begingroup$ @Amiramix You can remove an element from a linked list if you have the last element around. If you reach an element without going through the list in order, you won't have that, so make it a doubly-linked list. $\endgroup$ – Gilles Nov 1 '16 at 21:56

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.