Thanks to my daughter’s teddy bears/soft toys/stuffed toys/whatever else you may call them, I now have a better understanding of stacks and queues in Python.
I’ll get back to stacks and queues in a bit to discuss how to implement them, when to use them, and when not.
But first, you’ll need to meet my daughter’s teddy bears.
I asked her to get ten of her teddy bears (she has too many, I know) and rank them in order of size, from smallest to largest. We then got ten empty boxes.
Setting up a "list" of boxes
First, we found a clear spot at home and placed all ten boxes next to each other. We then put the teddy bears one in each box, starting from the left-hand side with the smallest one.
This set-up is a Python list, or more generally, an array. I’ll use the term list in this post as this is a Python-ecosystem blog.
Setting up a "linked list" of boxes
Later, we moved the boxes around the home. We took the box with the smallest teddy bear in the living room, under the table. I told my daughter to remember where we’ve put this first box. It’s the only thing she needs to remember.
We then took a piece of paper, we wrote "in the hallway next to the bookcase" on it, and we placed this paper in the box. This paper shows the location of the second box with the second smallest teddy bear inside.
We kept on putting the boxes in different parts of the home, each time putting a piece of paper in each box showing the location of the next box.
This set-up is a linked list. The boxes are not next to each other, but each points to where the next one is.
Finding one of the teddy bears
In both scenarios, I asked my daughter to find the fifth-largest teddy bear.
With the list set-up, this was easy. She knew where in the home the boxes were. When she got there, she counted up to the fifth box and opened it. Smiling at her was our medium-sized Winnie the Pooh—she has another, larger Winnie the Pooh, too!
The same task with the linked list took up more time. She knew where the first box was. She got there, opened it, and found the location of the second. Off she went to the hallway and the second box gave her the location of the third, then the fourth, and finally she found her way to the fifth box with medium Winnie the Pooh in it.
Finding an item in a linked list takes longer. It would have been worse if she were looking for the largest teddy bear, the one in the tenth box.
However, with the list set-up, it doesn’t really matter which box we need as they’re all easy to find. So, lists are better than linked lists, surely? Let’s not be too hasty.
Removing one of the teddy bears
My daughter decided to give the medium-sized Winnie the Pooh to her younger cousin. So, she needs to remove the teddy bear entirely.
I explained to her that the rule with the list set-up is that you cannot have any empty boxes except at the end of the line of boxes on the right-hand side.
When removing the teddy bear from the fifth box, she then had to get the one in the sixth box and move it to the fifth, move the one in the seventh box to the sixth box, and so on. Finally, all boxes from one to nine were full.
The same task with the linked list set-up was easier, however. Once she found the fifth box, she took the sheet of paper showing where the next box is and moved the paper to the previous box. That’s it–no need to move any teddy bears around or to visit all the other boxes in the sequence.
Which one wins?
I can hear you ask me: "But overall, which task took longer?" Finding the fifth box was slower with the linked list, but removing this teddy bear was faster than with the list.
Which scenario wins depends on the length of the lists and which item you need.
My daughter then had an idea. As her cousin is small, she thought it would be best to give him the smallest teddy bear, the one in the first box.
Finding this box was just as quick with the linked list as with the list.
Removing the first teddy bear from the linked list was also very easy. This box had a piece of paper with the location of the next box. All my daughter had to do is to remember that location as the new "starting" location. However, with the list set-up, she had much more work to do as she went through all the other boxes moving the teddy bears one box to the left each time.
The linked list is the clear winner in this case. We’ll see why this is relevant when we talk about stacks and queues soon.
Adding a new teddy bear
A few days later, my daughter was given a new teddy bear by her grandparents. It was a small one. We knew it was the smallest teddy bear in her set. So, she had to put it in the first spot.
With the linked list scenario, we just got a new box out, found a free spot in the home and put the new teddy bear in. She also put a piece of paper in the box with the location of what had previously been the first box in the linked list. All she needs to do now is to remember the location of this new box, which is now the first in the linked list.
Alas, not so easy with the list. The first box is not empty. First, she had to move the ninth teddy bear into the tenth box, then the eighth teddy bear into the ninth box, and so on. Finally, the first box was empty. Now, she could put the new teddy bear in the first box. We’re almost getting to the stacks and queues bit.
Just one more step first.
Going forwards and going backwards
Let’s go back to the linked list scenario. After finding the medium-sized Winnie the Pooh in the fifth box, my daughter decided that after all, she wanted to give her cousin the Dumbo toy instead. Dumbo is the fourth largest teddy bear. In the linked list set-up, she has to go back to the first box and start again. Each box only has the location of the next one. So, you can only move forwards in a linked list, but not backwards.
However, it’s not a lot more work to put two pieces of paper in each box, one showing the location of the next box and one showing the location of the previous one. This set-up is a doubly-linked list. Now, you can go both backwards and forwards. It also makes sense now to remember the location of both the first box and the last one so that you can choose to start at either end. This is what’s happening in Python’s deque data structure. But we’ll come to deques shortly.
Stacks and Queues
The best way to understand stacks and queues is to start by looking at the non-programming meaning of these words. The names stacks and queues describe the structures very accurately.
Let’s start with a queue. When you join the queue (or line) at the supermarket checkout, you know that the order you’ll be served in is the order in which you’re standing in the queue. The first person to join the queue is the one to be served first, the second person to join the queue will be second, and so on.
If you picture a queue as items lined up next to each other so that each new item joins the sequence at the right-hand side end, then whenever you need to remove an element, you’ll need to remove the first one in the sequence, the one on the left-hand side end. A queue is a First-In-First-Out (FIFO) structure.
Using a list for this is not ideal, as although adding a new item at the end of the list is quick, removing an item from the front of the list is expensive, as my daughter found out when she wanted to give the smallest teddy bear to her cousin from the list set-up.
You could reverse the order and add items to the beginning of the list and remove them from the end, but adding items to the beginning of the list is also time-consuming, as my daughter also found out.
However, a doubly-linked list works very well for creating a queue. Adding items to either end is very quick, as the program knows the location of both ends of the doubly-linked list. Removing items from either end is also very efficient.
Let’s look at stacks. To understand stacks, you can picture a stack of books piled up on each other. The only book you can remove is the one at the top of the stack, which is the last one that you added to the stack. A stack is a Last-In-First-Out (LIFO) structure.
You can implement a simple stack using a list in Python as adding items to the end of the list and removing items from the end of the list are both efficient. A doubly-linked list would also do the job well. Indeed, in some situations, especially when the stack size grows, doubly-linked lists can be more memory efficient.
Using Python’s deque data structure
This blog post’s aim is not to go through all the ways you can create stacks and queues in Python. There are some references at the end of this blog if you want to read more. I’ll discuss briefly one of the data types in Python’s collections module, which is part of the standard library: the deque data structure. The term deque stands for double-ended queue, and it’s implemented using the doubly-linked list structure discussed earlier.
Let’s create a large sequence of numbers and represent them both as a list and as a deque (all code shown is for Python 3.9):
import random from collections import deque repeat = 1_000_000 numbers = [random.random() for _ in range(repeat)] as_list = numbers.copy() as_deque = deque(numbers)
Let’s start by emptying both of these data structures from the left and finding out how long each task takes using a simple timer:
import random
import time
from collections import deque
repeat = 1_000_000
numbers = [random.random() for _ in range(repeat)]
as_list = numbers.copy()
as_deque = deque(numbers)
print(
"Emptying a list from the left is very expensive, "
"not so with a deque"
"\n(time to put the kettle on...)"
)
tic = time.time()
while as_list:
as_list.pop(0)
print(f"Time to empty list from left: {time.time() - tic}")
tic = time.time()
while as_deque:
as_deque.popleft()
print(f"Time to empty deque from left: {time.time() - tic}")
This gives the following output when I run this on my laptop:
Emptying a list from the left is very expensive, not so with a deque
(time to put the kettle on...)
Time to empty list from left: 152.45251202583313
Time to empty deque from left: 0.08112716674804688
As we’ve seen when my daughter removed the smallest teddy bear from the list, all the other items must be moved by one place to the left, which takes time.
Emptying lists and deques from the right, however, is efficient for both:
# ...
# Reset list and deque
as_list = numbers.copy()
as_deque = deque(numbers)
print(
"\nHowever, emptying a list from the right "
"is not expensive"
)
tic = time.time()
while as_list:
as_list.pop(-1)
print(f"Time to empty list from right: {time.time() - tic}")
tic = time.time()
while as_deque:
as_deque.pop()
print(f"Time to empty deque from right: {time.time() - tic}")
The result is:
Emptying a list from the right is not expensive though
Time to empty list from right: 0.08184814453125
Time to empty deque from right: 0.08214497566223145
There is no shifting needed when removing the last item from a list. And since a deque is double-ended, the location of the last item is known, so there’s no expensive searching needed.
Let’s now try retrieving the item in the middle of each sequence:
# ...
# Fetching an item
# Reset list and deque
as_list = numbers.copy()
as_deque = deque(numbers)
print(
"\nBut, fetching an item from the middle of a "
"deque is expensive, unlike lists"
)
tic = time.time()
for _ in range(repeat):
as_list[int(repeat / 2)] # Fetch middle element several
print(
f"Time to fetch middle element from list {repeat} times:"
f" {time.time() - tic}"
f"\n(time to drink that tea you made earlier...)"
)
tic = time.time()
for _ in range(repeat):
as_deque[int(repeat / 2)] # Fetch middle element several
print(
f"Time to fetch middle element from deque {repeat} times:"
f" {time.time() - tic}"
)
The output of this gives:
But, fetching an item from the middle of a deque is expensive, unlike lists
Time to fetch middle element from list 1000000 times: 0.21008801460266113
(time to drink that tea you made earlier...)
Time to fetch middle element from deque 1000000 times: 70.72879719734192
The middle element in a deque is the hardest one to get since the only way to get to the middle is through all the items which come either before or after the middle one, depending of whether you start from one end or the other. My daughter had to go through all boxes from the first to the fourth, reading the location of the next box each time, to get to the fifth box.
Final Words
The answer to "which structure is better, a list or a deque?" depends on what you’re trying to achieve and how large your structure is. Adding and removing items only from one or both ends tends to favour a deque, but if you need to retrieve items from within the structure frequently, lists may be the best choice.
And we have too many teddy bears at home, that’s a fact!
Further reading
Read the introductory post in The Python Coding Blog.
You may also enjoy reading about Monty and The White Room analogy for understanding programming.
Subscribe to
The Python Coding Stack
Regular articles for the intermediate Python programmer or a beginner who wants to “read ahead”
[…] You can also read about linked lists and how they compare with lists in the article about stacks and queues […]
[…] written in some detail about deques and how they’re used in stacks and queues in the very first post on this blog. You can also read more about this topic in this […]
[…] You may also like the article on stacks, queues, and deques […]