Popping and Appending Items Efficiently

00:00 The most significant difference between deque and list is that deque enables efficient .append() and .pop() operations on both ends of the deque.

00:08 We have two dedicated methods in a deque: .popleft() and .appendleft(). Let’s see them in action.

00:15 First of all, let’s import the deque from the collections module.

00:20 And let’s create a new deque using the list [1, 2, 3, 4] using the values as iterable.

00:27 Then let’s use .popleft() to remove one value from the left end of the deque, in this case, 1. If we run it again, it will drop 2.

00:36 And if you check the numbers now, the deque will contain only the values 3 and 4. So now you can use .appendleft() to add a new value to the left end of numbers.

00:47 So now it will have 2, 3, 4, and then if we .appendleft() one more value, in this case 1, and we check what we have in the deque, we’ll see that we have the same deque that we had originally.

01:02 Just like list, deque also provides .append() and .pop(). These methods operate on the right end of the sequence, but there’s something important to notice.

01:12 .pop() behaves differently. Let’s use the .pop() method of the deque. It will always remove and return the last value of the deque, in this case 4.

01:22 However, this method doesn’t take an index as an argument. That means that you can’t use .pop() to remove arbitrary items from your deque like you can with the corresponding method of a list.

01:36 You can always use it to remove and return the rightmost item.

01:42 A deque is implemented as a doubly linked list, so every item in a given deque holds a reference to the next and previous item in the sequence. Doubly linked lists enable appending and popping items from either end to be lightweight and efficient operations.

01:58 That’s possible because only the pointers need to be updated. As a result, both operations have similar performance of O(1). They are also predictable in terms of performance because there’s no need to reallocate memory and move existing items to accommodate new ones.

02:16 You can actually test that adding items to the left end of a deque is faster than adding items to the left end of a list. This Python script performs 10,000 .insert() operations on a list and 10,000 .appendleft() operations on a deque, and then it measures the average execution time for each and then it prints the results.

02:39 When you run this script, you’ll see that .appendleft() on a deque is several times faster than .insert() on a list.

02:47 Note that deque .appendleft() is constant, which means that the execution time is constant. However, list .insert() at the left end of the list is linear, which means that execution time depends on the number of items to process.

03:04 Now that you’re familiar with appending and popping items on a deque, in the next lesson you’ll learn how to access random items in a deque.