The article mentions the advantages of deque, but neglects the mention its disadvantages. While deque has fast pop/append from both ends, it has slow item access.

Use deque only if you need insert/remove to be fast from both ends, and don't care about read speeds. List has constant time append/pop from one end and also constant time access anywhere in the list. You should almost always prefer list over deque, which is why list is builtin.

Could anyone explain me what I did wrong here

Yes, your timing is dominated by the time to create the list or deque. The time to do the pop is insignificant in comparison.

Instead you should isolate the thing you're trying to test (the pop speed) from the setup time:

In [1]: from collections import deque

In [2]: s = list(range(1000))

In [3]: d = deque(s)

In [4]: s_append, s_pop = s.append, s.pop

In [5]: d_append, d_pop = d.append, d.pop

In [6]: %timeit s_pop(); s_append(None)
10000000 loops, best of 3: 115 ns per loop

In [7]: %timeit d_pop(); d_append(None)
10000000 loops, best of 3: 70.5 ns per loop

That said, the real differences between deques and list in terms of performance are:

• Deques have O(1) speed for appendleft() and popleft() while lists have O(n) performance for insert(0, value) and pop(0).

• List append performance is hit and miss because it uses realloc() under the hood. As a result, it tends to have over-optimistic timings in simple code (because the realloc doesn't have to move data) and really slow timings in real code (because fragmentation forces realloc to move all the data). In contrast, deque append performance is consistent because it never reallocs and never moves data.

Your mileage may vary according to your application and precise use case, but in the general case, a list is well suited for a stack:

append is O(1)

pop() is O(1) - as long as you do not pop from an arbitrary position; pop() only from the end.

Deques are also O(1) for these operations, but require importing a module from the standard library, require 'O(n)' for random access. An argument could be made to prefer using vanilla lists though, unless for specific applicatins.

Correction:

from this post by Raymond Hettinger, a principal author of the C code for both list and deque, it appears that deques may perform slightly better than lists: The pop() operation of deques seem to have the advantage.

In [1]: from collections import deque

In [2]: s = list(range(1000))      # range(1000) if python 2

In [3]: d = deque(s)

In [4]: s_append, s_pop = s.append, s.pop

In [5]: d_append, d_pop = d.append, d.pop

In [6]: %timeit s_pop(); s_append(None)
10000000 loops, best of 3: 115 ns per loop

In [7]: %timeit d_pop(); d_append(None)
10000000 loops, best of 3: 70.5 ns per loop

the real differences between deques and list in terms of performance are:

Deques have O(1) speed for appendleft() and popleft() while lists have O(n) performance for insert(0, value) and pop(0).
List append performance is hit and miss because it uses realloc() under the hood. As a result, it tends to have over-optimistic timings in simple code (because the realloc doesn't have to move data) and really slow timings in real code (because fragmentation forces realloc to move all the data). In contrast, deque append performance is consistent because it never reallocs and never moves data.

A List is general and flexible.

Generalized structures are ideal for return values in business, web, and desktop applications. It's not optimal to return a Deque or an Array if your consumers will be converting to List in most cases anyway. It's potentially less efficient. And, it clutters your consumers' codebases with boilerplate conversions and/or utility libraries to deal with your "more efficient" interfaces.

To be clear: Some structures, like Deque's and Array's are certainly more efficient for particular use cases, but a List is sufficiently efficient for most use cases. List's may be over-used. But, in many domains, the performance hit of using a List over a more well-suited structure is negligible — not even worth a second thought.

Compound that with work-effort versus business value: Choosing a data structure that supports the precise interface I need and no more requires mental effort and time. And those are costs to the business. Sometimes there's a corresponding increase in value. But, in many applications there isn't — neither the business nor the customers will see any difference if you swap your List out for a more-optimized Deque when you're piping 50 rows from the database through your model to your view. (Or whatever.)

That said, there are use-cases that are well-served by List's.

The "need" for a List is more obvious in long-lived, stateful applications, where collections can stick around and be mutated over a long period of time. A text editor, for example, shouldn't automatically create a data[MAX_ROWS][MAX_COLS] array of arrays. And, you certainly could create an array of arrays with some default sizes and scaling behaviors and add methods for insertions and deletions. But, that's precisely what the List interface already does for you. (And the existing implementation already well-tested and optimized!)

My "2 cents": Unless your domain is small, very well-defined, or performance-critical, start with general collections and optimize later. The flexibility is immediate valuable in most business and web applications. Whereas the performance edge is negligible.

And don't forget about stateful applications, where a List interface is more often precisely what you'll end up reinventing if you've defaulted to an array or Deque...

^{Examples of things where you might favor efficiency over flexibility might include things like system code (OS, driver, firmware), a VM, or other types of "platform" code — like a modern web browser's internal DOM implementation or JavaScript execution engine.}