Effective queue/linked list in Python

I need to write event calendar in Python which allows pasting events in any position AND works as FIFO (pop elements from the left side).

Python collections.deque can efficiently works as FIFO, but it don't allow to paste elements between current elements.

In the other hand, Python list allows inserting into the middle, but popleft is inefficient.

So, is there some compromise?

UPD Such structure probably more close to linked list than queue. Title changed.

Solution

You can have a look at blist. Quoted from their website:

The blist is a drop-in replacement for the Python list the provides better performance when modifying large lists.

...

Here are some of the use cases where the blist asymptotically outperforms the built-in list:

Use Case                                      blist              list
--------------------------------------------------------------------------
Insertion into or removal from a list         O(log n)           O(n)
Taking slices of lists                        O(log n)           O(n)
Making shallow copies of lists                O(1)               O(n)
Changing slices of lists                      O(log n + log k)   O(n+k)
Multiplying a list to make a sparse list      O(log k)           O(kn)
Maintain a sorted lists with bisect.insort    O(log**2 n)        O(n)

Some performance numbers here --> http://stutzbachenterprises.com/performance-blist