"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)
Insert/Remove Time 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) from the ends.
Insert/Remove Time 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.
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()