If you’re programming in Python for some time at least, you must know what a list is. It’s the most common data structure in entire Python programming. But as you keep on coding and learn new things you get to know about time complexity. Then you wonder how much time doing anything takes. You keep checking it out. The in-built functions of lists in Python are very powerful. It makes programming very easy. But it isn’t always the best idea to use lists. Today we’re going to compare list with another commonly used data structure in Python – deque.
Why do we need to compare the list with the deque?
The list is the most commonly used data structure in Python. But the list isn’t always the best choice. It sure has a lot of features but sometimes when we program we may have time constraints so we would have to make sure that we pick the most suitable option. Deque is another data structure in Python that have a lot of features. So we can compare both of them and moving forward whichever one turns out to be best in a situation can be used.
How to compare the list with the deque?
List and Deque are somewhat similar. They both are linear data structures and are mutable. You can append an element at any position and also delete any element in both of them. Their performance is based on how much time it takes to append or delete an element at a position. So we’re going to compare the append time and delete time in both of them at the beginning, middle, and end.
What is a List?
A list is a data structure that stores a collection of data. It is derived from the most basic data structure array. An array is a continuous and contagious collection of data of similar data types. In general, we refer list as similar to an array but they both are different. Unlike an array, the elements in the list don’t have to be of the same data type.
num_list = [1,2,3,4,5,6,7,8,9,10]
print(num_list)
OUTPUT[1,2,3,4,5,6,7,8,9,10]
What is a Deque?
Before learning what a deque is, first we have to understand what a queue is. A queue is a data structure that follows the FIFO (first in first out) rule. It means the first element that enters the queue gets out first. Insertion is done from the front and deletion is done from the back in a queue. A deque is nothing but a queue that allows deletion and insertion from the front and back. Python doesn’t have a deque in-built but there is this one in-built library in Python called collections. There’s deque in collections and it is very efficient.
In this article, we’re going to compare this deque from the collections library with a list. But first, let’s take a look at how to use deque in Python.
from collections import deque #importing deque from collections library
dq = deque([1,2,3,4,5]) # creating a deque
print(dq)
OUTPUTdeque([1, 2, 3, 4, 5])
Big O Notation
Moving forward, many time measurements will be done using the big O notation. Big O notation is a relative method to calculate the time taken in the worst-case scenario. It doesn’t give any actual value to the time taken by the program but can be used to get a good idea of the relative time taken. It works on the step-counting method. Basically, we calculate how many steps a program makes to run to completion. O(1) is the best time complexity which takes a constant amount of time to run to completion.
Related: Learn more about time complexity.
Comparing append at the end
In theory, appending an element at the end of both – list and deque must take a constant amount of time i.e.O(1). They both take an almost equal amount of time to append an element at the end. Let’s try it ourselves.
from time import time #importing time function from module time
from collections import deque #importing deque from collections library
nums_list = [1,2,3,4,5] # creating a list
start = time()
nums_list.append(6) #appending 6 at the beginning of the list
end = time()
print("Time taken to append an element at beginning of the list:", end-start)
nums_deque = deque([1,2,3,4,5]) # creating a deque
start = time()
nums_deque.append(6) #appending 6 at the beginning of the deque
end = time()
print("Time taken to append an element at end of the deque:", end-start)
In the above code, first, we imported the time function from the time module to get time at any given point and then we imported the deque from the collections library. To calculate the time taken to append an element in the list, first, we initialized a variable named start with the current time. Then we appended 6 at the end of the list using the append function. After that, we just stored the time at the moment in the end variable. Then we got the time taken to append the element to the list by subtracting the start from the end. Then we did the same for deque. We created a deque, initialized start with the time at the moment, appended 6 at the end of the deque, and then stored the time at the moment in the end variable. Then, subtracting start from end gives us the time taken to append an element at the end of a deque.
The time taken to append an element at the end of a list is 2.07 x 10-4 and at the time time to append an element came out to be 1.35 x 10-4.
This difference is very less significant. That just means that they both take almost equal time. This proves the point at the start that both must take O(1) amount of time.
Comparing append at the beginning
Now let’s check the difference in runtime for appending an element at the start of a list and deque. For the list, we’re going to use the insert function and for deque, we’re going to use the appendleft function.
from time import time #importing time function from module time
from collections import deque #importing deque from collections library
nums_list = [1,2,3,4,5] # creating a list
start = time()
nums_list.insert(0,0) #appending 0 at the beginning of the list
end = time()
print("Time taken to append an element at beginning of the list:", end-start)
nums_deque = deque([1,2,3,4,5]) # creating a deque
start = time()
nums_deque.appendleft(0) #appending 0 at the beginning of the deque
end = time()
print("Time taken to append an element at beginning of the deque:", end-start)
So this time, again, first we imported time and deque from collections. Then we appended 0 at the beginning of the list using the insert function and at the beginning of the deque using the appendleft function. Just like the previous example, we created a list of 5 numbers, noted the start time inserted 0 at the beginning, noted the end time, and subtracted start from end to get the time taken. Similarly, with deque, we created a deque of 5 numbers, noted the start time inserted 0 at the beginning, noted the end time, and subtracted the start from the end to get the time taken. You can see there isn’t any significant difference again in the runtime. But, let’s try it again with a bigger list and deque.
from time import time #importing time function from module time
from collections import deque #importing deque from collections library
nums_list = list(range(10**8)) # creating a list
start = time()
nums_list.insert(0,0) #appending 6 at the start of the list
end = time()
print("Time taken to append an element at the start of the list:", end-start)
nums_deque = deque(range(10**8)) # creating a deque
start = time()
nums_deque.appendleft(0) #appending 6 at the start of the deque
end = time()
print("Time taken to append an element at the start of the deque:", end-start)
Wow! Now that’s a big difference. You can see, for the list, the runtime came up to 0.43 seconds, and for the deque it is 5.67 x 10-5. That’s 7.5k times for list than deque. In this case, we are sure the deque is better than the list. This is because for a list it takes O(n) time to append an element at the beginning and for a deque, it takes O(1) time to append an element at the beginning.
Comparing append at the middle
from time import time #importing time function from module time
from collections import deque #importing deque from collections library
A_really_big_number=10**8
nums_list = list(range(A_really_big_number)) # creating a list
start = time()
nums_list.insert(A_really_big_number//2,0) #appending at the middle of the list
end = time()
print("Time taken to append an element at middle of the list:", end-start)
nums_deque = deque(range(A_really_big_number)) # creating a deque
start = time()
nums_deque.insert(A_really_big_number//2,0) #appending at the middle of the deque
end = time()
print("Time taken to append an element at middle of the deque:", end-start)
We did the same thing again but this time, we appended the element in the middle of the list and deque. Appending in the middle takes almost a lot but an almost equal amount of time. For the list, it is 0.28 and 0.35 for the deque in our case. Appending, in the end, has a time complexity on O(n) for both list and deque.
Comparing pop time
Popping an element out of the list is another frequent task. Let’s compare it with popping an element out of the queue at the end and at the start. For this, we’ll use the pop function.
from time import time #importing time function from module time
from collections import deque #importing deque from collections library
A_really_big_number=10**8
nums_list = list(range(A_really_big_number)) # creating a list
nums_deque = deque(range(A_really_big_number)) # creating a deque
start = time()
nums_list.pop(0) #popping from the start of the list
end = time()
print("Time taken to append an element at the start of the list:", end-start)
start = time()
nums_deque.popleft() #popping from the start of the deque
end = time()
print("Time taken to append an element at the start of the deque:", end-start)
start = time()
nums_list.pop() #popping from the end of the list
end = time()
print("\nTime taken to append an element at the end of the list:", end-start)
start = time()
nums_deque.pop() #popping from the end of the deque
end = time()
print("Time taken to append an element at the end of the deque:", end-start)
The stats of the pop function are almost similar to the append function. The popping out an element from the end takes very less and almost equal time for both list and deque. But popping out an element from start takes much less time for deque and for the list, it takes a significantly large amount of time. So popping from the start is better in deque than list and popping from the end is almost similar for both of them.
Table of complexities
Append function
| Position | List | Deque |
| Beginning | O(n) | O(1) |
| Middle | O(n) | O(n) |
| End | O(1) | O(1) |
Pop function
| Position | List | Deque |
| Beginning | O(n) | O(1) |
| Middle | O(n) | O(n) |
| End | O(1) | O(1) |
Conclusion: Which is better – Deque or List?
As we saw just now, the list takes a lot of time to append at the beginning or to pop the beginning element than deque and almost equal time for the rest. Both are easy to manipulate and has really great application. So is a deque better than a list? If you have a time constraint, it is better to use deque. But deque lacks functionality. Lists in Python gain their importance through their slicing ability. Deque doesn’t have the slicing property.
So, if you don’t need to perform complex functions like slicing and have a time constraint, it’s always a good idea to use a deque. We could just use the list for the rest.
Both data structures are really powerful and we must learn both. Understand when to use which and keep practicing.