Data Structures

Deque

Lesson

"Deque" is short for a double-ended queue. It's a LinkedList that goes both ways. The main purpose of Deques is to allow you to read/write to both ends quickly, and implement data structures like Queues.

Deques are built into Python, and you create a Deque like this:

Reading and writing to a Deque is slow in general. You can say something like x[2] to read the 2nd index, but internally the computer will have to step all the way down to index 2. Inserting and removing an element are slow too for the same reason.

Read/Write Time O(n)O(n)

Insert/Remove Time O(n)O(n)

Deques are only fast when you want to read/write/insert/remove from the ends.

For example, here's how you'd insert 20 at the beginning of the Deque.

The computer only need to change a few edges:

Read/Write Time O(1)O(1) from the ends.

Insert/Remove Time O(1)O(1) from the ends.

You can see the Cheat Sheet for more operations you can do on the Deque. You won't have to know the names of the operations off the top of your head, though.

Mark as Completed:
Submits:
test
Test your code to get an output here!