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.
Let’s head over to the interactive shell to see how it works. We can import the required object with
from collections import deque.
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.
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.
Looks good so far. We can call the
.append() method on our
llist object, passing in an iterable object.
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.
.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.
.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.