Join us and get access to thousands of tutorials and a community of expert Pythonistas.
This lesson is for members only. Join us and get access to thousands of tutorials and a community of expert Pythonistas.
Introducing collections.deque
00:00
In Python, there’s a specific object in the collections module that you can use for linked lists, called deque. This stands for double-ended queue. collections.deque uses an implementation of a linked list in which you can access, insert, or remove elements from the beginning or end of the list with constant O(1) performance.
00:27
Let’s head over to the interactive shell to see how it works. We can import the required object with from collections import deque.
00:42
As you can see, this deque object can be created just like any other. Since we didn’t pass any arguments into the constructor, our linked list has no elements.
00:53
If we want to create a linked list with elements, we just need to supply an iterable object, like this. Here, I’m using the list, but you can supply any iterable object you want, such as the string. I’ll create a new variable called llist, which will store a linked list of individual characters.
01:17
Looks good so far. We can call the .append() method on our llist object, passing in an iterable object.
01:27
And as you can see, 'f' was appended to the right side of the linked list. We can remove the rightmost object by calling the .pop() method, like this.
01:40
.pop() is interesting because it not only removes the rightmost element from the list but it also returns it. I’ll inspect llist once more, and you can see that it no longer contains 'f'. We also have access to methods for appending and popping from the leftmost side of the list.
02:02
.appendleft() can be used to append an object to the left. And, of course, I can pop it from the left too.
Become a Member to join the conversation.