Deque: Python Data Structure

what are Deques in Python?

When you write any programs, whether its a machine learning algorithm or other programs, you need to pick the right data structures for it. Choosing the right data structures is what makes your program fast, memory efficient, easy to implement, and easy to read. You might be familiar with common Python data structures like List, Dictionary, String etc. But have you used Deques?

Deques are a data structure in Python which act basically as a Queue data structure (FIFO). Although at the face of it, it appears as a List, behind the scenes, it is a doubly linked list , which offers great performance (time complexity) to add and remove elements from the list, from either the start or the end of the list.

That is why, as one of the most important reasons, it is useful for creating programs. Whether it be machine learning algorithms or other programs, Deques are useful. If you have a program logic where you need to remove/add item from any position in the list, not just the end, then you should use a Deque, it will offer great speed performance. Some common use case of Deques include job scheduling, web crawling.

Let’s explore using Deques and it’s underlying benefits, and of course, and it’s shortcomings.

All operations above — popleft, popright, appendleft, appendright are of O(1) complexity in a deque, since it is optimized for it. Now if you were to do any of those operations in a List data structures instead, the complexity would be much worse, it would be O(n) complexity. This is focus point and biggest benefit of using a Deques.

Everything is a tradeoff. Deque offer high speed performance, however, they also incur a lot of extra memory, so they are not very memory efficient.

Follow me for more content and learn more about computer science & machine learning.