Accessing Random Items in a Deque

00:00 So far, you’ve learned that deques are optimized for adding and removing items from either end of the sequence. But deques also support several operations that you may already be familiar with if you worked with Python lists before. So let’s see them in action.

00:15 Let’s import the deque from the collections module,

00:20 and let’s create a deque from a string.

00:25 So the deque now has a, b, d, e. You can insert c into letters at position 2 by using the .insert(), giving the position 2, and then the letter that you want to insert, in this case, c.

00:40 So the deque now has a, b, c, d, e. If you would like to remove d, you can do that by using the .remove() method and providing d as an argument.

00:52 So now, d is gone. deques also allow indexing to access items. For instance, the item at index 1 from the letters deque is b.

01:04 And you can use the del keyword to delete any existing item from a deque. In this case, you give it a position. The difference between .remove() and del is that .remove() deletes items by value, while del removes them by index. Even though deque supports indexing, it doesn’t support slicing.

01:24 The reason why slicing isn’t available is that performing a slice operation on a linked list would be inefficient. When you try to get a slice from a deque, you will get a TypeError.

01:38 So far, you’ve seen that deque is quite similar to list. However, while list is based on arrays, deque is based on doubly linked lists.

01:47 There is a hidden cost behind deque being implemented as a doubly linked list. Accessing, inserting, and removing arbitrary items aren’t efficient operations.

01:58 To perform them, the Python interpreter has to iterate through the deque until it gets to the desired item. So they are O(n) instead of O(1) operations.

02:09 Accessing elements from the middle of a deque is less efficient than accessing the same elements from a list. The main takeaway here is that deques aren’t always more efficient than lists.

02:20 This summary table can help you choose the appropriate data type for the problem at hand. In the next lesson, you’ll learn how to build an efficient queue using a deque.