On 9 Jan 2005 16:03:34 -0800, "John Machin" <[EMAIL PROTECTED]> wrote:
>My wild guess: Not a common use case. Double-ended queue is a special >purpose structure. > >Note that the OP could have implemented the 3-tape update simulation >efficiently by reading backwards i.e. del alist[-1] Note that I was just trying to say that it's not obvious that list insertion at the first element is O(n); because there are "less naive" implementation that can do better. For a lower level language O(n) is probably what 99% of programmers indeed would expect, but for a VHLL like python this is IMO not the case. I remember when a few years ago working with PowerBuilder (a RAD environment for client-server applications) to my great surprise I found that even adding at the end of a list was O(n) in that language... where is the line ? After all "smart" reallocation is still a tradeoff (extra "wasted" space traded for diminshed copying) ... Andrea -- http://mail.python.org/mailman/listinfo/python-list
