I am trying to create a queue of events and I want to be able to insert and delete from the middle of the queue in constant time, something like this:
3446 --- 9493 --- 15969 --- 48381
where the number could be millis from now, or whatnot.
How could I insert an event between the 9493 and 15969 event?
I could use binary search to find the events in the queue with the desired times, but is there an easier way?
What you're looking for is called a priority queue:
https://en.wikipedia.org/wiki/Priority_queue
The typical way to implement one is to use a heap; you get O(log n) insert time and O(log n) delete time (for removing the highest priority item from the queue). Check the Wikipedia page for a list of other potential data structures, some of which have better amortized time.