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 element x 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 element x 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 the iterable.

  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 the iterable. 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 element x at position i. 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 an IndexError. 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 an IndexError. 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 of value from the deque. Raises a ValueError 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 deque n steps to the right. If n is negative, rotates n 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 times x 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() or extend(), the element at the left end is automatically discarded.
• If you use appendleft() or extendleft(), 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.