[Python-ideas] Question about `list.insert`

[Antoine Pitrou]

On Sat, 8 Feb 2014 05:00:24 +1100
Chris Angelico <rosuav at gmail.com> wrote:
> On Sat, Feb 8, 2014 at 1:59 AM, Antoine Pitrou <solipsis at pitrou.net> wrote:
> > On Fri, 7 Feb 2014 22:45:33 +1100
> > Chris Angelico <rosuav at gmail.com> wrote:
> >> But apart from
> >> maybe reducing the memory copying (the same optimization could mean
> >> that repeated pop(0) calls would incur less copying, too), there's not
> >> a huge gain.
> >
> > If you think switching from O(n**2) to O(n) isn't a huge gain, then
> > indeed :-)
> >
> 
> Sure, that would be a huge gain. But anyone who's repeatedly calling
> pop(0) followed by insert(0,x) should be using deque rather than list.

Indeed, since deque exists, it is the reasonable answer.

This whole discussion happens in a hypothetical setting where deque
wouldn't exist and there would be an opportunity to make list a
one-size-fits-all sequence type.

(note that my personal opinion is that built-in Python data types should
be sufficiently powerful to cater for most use cases, rather than build
a whole array of specialized collection types as in Java or C++)

Regards

Antoine.