Getting Started With Python's deque

00:00 Before we dive deep on deques, let’s think about lists for a moment.

00:05 Appending and popping items from the right end of a Python list are efficient operations most of the time. Using the Big O notation for time complexity, these operations are O(1), also known as constant.

00:17 But it gets slower when Python needs to reallocate memory to grow the list. In that case, it becomes O(n), also known as linear time.

00:27 Appending and popping items from the left end of a Python list are both always inefficient and have O(n) time complexity. So, while you can use a list as a stack or a queue with the .append() and .pop() methods, deques are faster and that’s why it’s a good idea to learn more about them.

00:48 deque stands for double-ended queue. It’s a sequence-like data structure designed as a generalization of stacks and queues. A deque supports memory-efficient, fast, and thread-safe .append() and .pop() operations on both ends. And this is possible because deques are implemented as a doubly linked list.

01:08 In case you aren’t familiar with this concept, a doubly linked list is different from a singly linked list in that they have two references. Previous references the previous node and next references the next node.

01:24 deques are particularly useful for creating custom stacks and queues in Python. They’re also a good choice when you need to keep a list of recently seen items because it allows you to restrict the maximum length of your deque.

01:37 By setting a maximum length once the deque is full, it automatically discards items from one end when you append new items to the opposite end.

01:48 To create a new deque, you first need to import it from the collections module. A deque can store items of any data type. To create a new deque, the deque initializer takes an optional argument called iterable, which holds the iterable that provides the initialization data.

02:05 If you don’t supply an iterable, then you get an empty deque, like in this case. If you provide an iterable, then the deque initializes the new instance with data from it. For instance, using a tuple.

02:18 You could also use a list, or even a string.

02:25 These are just a couple of examples. You can create a deque from any iterable, such as a range object, a set, or even another deque.

02:34 In the next lesson, you’ll learn how to use deque’s specialized methods to efficiently add and remove items from both ends of the sequence.