On 29May2012 00:46, Julian Berman email@example.com wrote: | I've occasionally had a need for a container with constant-time append | to both ends without sacrificing constant-time indexing in the middle. | collections.deque will in these cases narrowly miss the target due to | linear indexing (with the current use case being for two deques | storing the lines of text surrounding the cursor in a text editor | while still being randomly indexed occasionally). | | Wikipedia lists at least two common deque implementations: | | http://en.wikipedia.org/wiki/Double-ended_queue#Implementations | | where switching to a dynamic array would seemingly satisfy my requirements. | | I know from a bit of experience (and a quick SO perusal) that "How do | I index a deque" does occasionally come up. Any thoughts on the value | of such a change?
It was pointed out to me recently that Python's list.append() is constant time overall.
Use two lists, one for append-forward and one for append backward. Keep track of the bound. Access to item "i" is trivially computed from the backward and forward list sizes and ends.