list.pop(0) vs. collections.dequeue

[Roy Smith]

In article <hje979$kc9$1 at news.eternal-september.org>,
 "Alf P. Steinbach" <alfps at start.no> wrote:

> But it would IMHO have been better if it wasn't called "list", which brings 
> in the wrong associations for someone used to other languages.

+1.

When I first started using Python (back in the 1.4 days), I assumed a list 
was a singly-linked list.  Which, of course, leads to the assumption that 
pop(0) is O(1), and lots of other wrong thinking(*).

Oddly enough, I was going to write in the above paragraph, "like a C++ STL 
list", until I happened to glance at the STL docs and refreshed my memory 
that an STL list is doubly-linked.  Which just goes to show that making 
assumptions based on names is a bad idea.

So, we're right back to my statement earlier in this thread that the docs 
are deficient in that they describe behavior with no hint about cost.  
Given that, it should be no surprise that users make incorrect assumptions 
about cost.

(*) I suspect somebody is going to point out that list.pop was added in 
some version later than 1.4, but that's a detail.