Deques in Python: Mutable or Immutable? Exploring Size Changes
The deque
(pronounced “deck”) is a powerful and versatile data structure in Python, part of the collections
module. It stands for “double-ended queue” and, as the name suggests, allows efficient addition and removal of elements from both ends of the sequence. This makes it suitable for a variety of applications where traditional lists might be less efficient. This article dives deep into Python deques, specifically addressing their mutability and how their size can be dynamically changed.
1. What is a Deque?
Imagine a queue that allows you to enqueue and dequeue elements from both the front and the back. That’s essentially what a deque is. It combines the functionalities of both a stack (LIFO – Last In, First Out) and a queue (FIFO – First In, First Out). It’s a generalized sequence type that provides fast, constant-time (O(1)) operations for appending and popping elements from either end, even when the deque is very large. This is a significant advantage over Python’s built-in list
type, which has O(1) appends and pops from the right end (using append()
and pop()
), but potentially O(n) performance for operations on the left end (using insert(0, x)
and pop(0)
).
2. Creating a Deque
You create a deque using the deque
constructor from the collections
module:
“`python
from collections import deque
Create an empty deque
my_deque = deque()
Create a deque initialized with elements
my_deque2 = deque([1, 2, 3, 4, 5])
Create a deque with a maximum length (optional)
my_deque3 = deque([1, 2, 3], maxlen=5) # ‘maxlen’ restricts the size
“`
The maxlen
argument is optional. If specified, the deque will automatically remove items from the opposite end when new items are added and the deque is at its maximum length. This creates a “bounded” deque. If maxlen
is not specified, the deque can grow dynamically without any limit (within memory constraints, of course).
3. Mutability: Deques are Mutable
Deques are mutable data structures in Python. This means you can change their contents after they have been created. This is in contrast to immutable data structures like tuples and strings, which cannot be modified in place. The mutability of deques stems from the fact that you can add, remove, and modify elements after the deque is instantiated.
4. Modifying Deque Size and Content
Deques provide several methods to change their size and modify their contents. Here are the key methods, categorized by where they operate:
4.1. Adding Elements:
-
append(x)
: Adds elementx
to the right end of the deque. O(1) time complexity.python
my_deque.append(6)
print(my_deque) # Output: deque([1, 2, 3, 4, 5, 6]) -
appendleft(x)
: Adds elementx
to the left end of the deque. O(1) time complexity.python
my_deque.appendleft(0)
print(my_deque) # Output: deque([0, 1, 2, 3, 4, 5, 6]) -
extend(iterable)
: Extends the right side of the deque by appending elements from theiterable
.python
my_deque.extend([7, 8, 9])
print(my_deque) # Output: deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) -
extendleft(iterable)
: Extends the left side of the deque by appending elements from theiterable
. Note that the elements will be added in reverse order from the iterable.python
my_deque.extendleft([-1, -2, -3])
print(my_deque) # Output: deque([-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) -
insert(i, x)
: Inserts elementx
at positioni
. Similar to lists, inserting in the middle of a deque is O(n), as elements may need to be shifted. Inserting at either end is O(1).python
my_deque.insert(5, 'a')
print(my_deque) # Output: deque([-3, -2, -1, 0, 1, 'a', 2, 3, 4, 5, 6, 7, 8, 9])
4.2. Removing Elements:
-
pop()
: Removes and returns the element from the right end of the deque. If the deque is empty, it raises anIndexError
. O(1) time complexity.python
rightmost = my_deque.pop()
print(rightmost) # Output: 9
print(my_deque) # Output: deque([-3, -2, -1, 0, 1, 'a', 2, 3, 4, 5, 6, 7, 8]) -
popleft()
: Removes and returns the element from the left end of the deque. If the deque is empty, it raises anIndexError
. O(1) time complexity.python
leftmost = my_deque.popleft()
print(leftmost) # Output: -3
print(my_deque) # Output: deque([-2, -1, 0, 1, 'a', 2, 3, 4, 5, 6, 7, 8]) -
remove(value)
: Removes the first occurrence ofvalue
from the deque. Raises aValueError
if the value is not found. This operation has O(n) time complexity in the worst case (searching the entire deque).python
my_deque.remove('a')
print(my_deque) # Output: deque([-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]) -
clear()
: Removes all elements from the deque, leaving it empty.python
my_deque.clear()
print(my_deque) # Output: deque([])
4.3. Other Useful Methods:
-
rotate(n)
: Rotates the dequen
steps to the right. Ifn
is negative, rotatesn
steps to the left. This is a highly efficient operation.“`python
my_deque = deque([1, 2, 3, 4, 5])
my_deque.rotate(2)
print(my_deque) # Output: deque([4, 5, 1, 2, 3])my_deque.rotate(-1)
print(my_deque) # Output: deque([5, 1, 2, 3, 4])
“` -
count(x)
: Returns the number of timesx
appears in the deque. O(n) time complexity.python
my_deque = deque([1, 2, 2, 3, 2, 4])
print(my_deque.count(2)) # Output: 3 -
reverse()
: Reverses the elements of the deque in place.“`python
my_deque = deque([1,2,3])
my_deque.reverse()
print(my_deque) # Output: deque([3, 2, 1])* **`copy()`:** Creates a shallow copy of the deque.
python
original_deque = deque([1, 2, 3])
copied_deque = original_deque.copy()
copied_deque.append(4)print(original_deque) # Output: deque([1, 2, 3])
print(copied_deque) # Output: deque([1, 2, 3, 4])“`
5. maxlen
and Size Management
As mentioned earlier, the maxlen
parameter provides a way to limit the size of a deque. When a bounded deque (a deque with maxlen
specified) is full and a new item is added:
- If you use
append()
orextend()
, the element at the left end is automatically discarded. - If you use
appendleft()
orextendleft()
, the element at the right end is automatically discarded.
“`python
bounded_deque = deque([1, 2, 3], maxlen=3)
bounded_deque.append(4)
print(bounded_deque) # Output: deque([2, 3, 4], maxlen=3)
bounded_deque.appendleft(0)
print(bounded_deque) # Output: deque([0, 2, 3], maxlen=3)
“`
This behavior makes bounded deques excellent for representing things like fixed-size buffers, recent history lists, or sliding windows over data.
6. Performance Considerations
The key advantage of deque
over list
is its O(1) performance for adding and removing elements from both ends. Lists are optimized for fast access to elements by index and fast append/pop operations on the right end. However, operations on the left end of a list (like insert(0, x)
or pop(0)
) can be slow because they require shifting all subsequent elements.
Here’s a table summarizing the time complexities:
| Operation | deque
| list
|
| ———————— | ——– | ———- |
| append(x)
| O(1) | O(1) |
| appendleft(x)
| O(1) | O(n) |
| pop()
| O(1) | O(1) |
| popleft()
| O(1) | O(n) |
| insert(i, x)
(at end) | O(1) | O(1) |
| insert(i, x)
(at start) | O(1) | O(n) |
| insert(i, x)
(middle) | O(n) | O(n) |
| remove(value)
| O(n) | O(n) |
| x[i]
(indexing) | O(1) | O(1) |
| rotate(n)
| O(k) | – |
Note about rotate(n)
: Where k is abs(n)
.
7. Conclusion
Deques are mutable, dynamic data structures in Python that provide efficient mechanisms for adding and removing elements from both ends. Their ability to be bounded with maxlen
makes them incredibly versatile. Understanding their mutability and the various methods for manipulating their size is crucial for effectively using deques in your Python code. They are a valuable tool in any Python programmer’s arsenal, especially when dealing with queues, stacks, or situations requiring efficient operations on both ends of a sequence.