Hacker News Reader

Forgive me doesn’t deque mean double ended queue? Also why can’t a simple array behave like a list?

Yes it does mean double ended queue. I'll assume you mean a python list when you say simple array. One drawback of lists is that you cannot add a new element to the start of a list in constant time (with a python list it requires O(n) time), whereas you can with a deque.

I had a script a while back that created really long lists at runtime by continually appending data as it came over the wire. The lists would quickly get so long that I needed to remove items from the beginning to conserve memory though because reasons I could only remove items one at a time. Long story short, converting those lists to collections.deque and making use of popleft() rather than "del l[0]" improved performance considerably.

Normal lists have a backing array. In theory, every time you resize it, it needs to allocate new memory and copy everything over, which is very slow. Obviously python does a lot of optimization behind the scene by over-allocating memory, which gives it better amortized speed.

Linked lists are slow at accessing data in the middle, but you can very quickly add and remove stuff from the ends, hence double-ended queue. A stack is basically a deque where you only use the tip, so deque is very versatile like that.

Reply on news.ycombinator.com