collections.deque() / collections.OrderedDict()
collections.deque is a class that provides a double-ended queue, allowing you to add and remove elements from either end in O(1) time. Operations at the front of a regular list take O(n) time, but with deque, front operations also run in O(1). collections.OrderedDict is a dictionary that preserves insertion order. While regular dictionaries in Python 3.7 and later also guarantee insertion order, OrderedDict provides additional features such as order-aware comparisons and move operations.
Syntax
from collections import deque, OrderedDict # Create a deque dq = deque([initial_elements], maxlen=max_length) # Create an OrderedDict od = OrderedDict()
Functions and Methods
| Function / Method | Description |
|---|---|
| deque(iterable) | Creates a double-ended queue. You can specify maxlen to limit the maximum number of elements. |
| dq.append(x) | Adds element x to the right end. |
| dq.appendleft(x) | Adds element x to the left end. |
| dq.pop() | Removes and returns the element at the right end. |
| dq.popleft() | Removes and returns the element at the left end. |
| dq.rotate(n) | Rotates the deque n steps to the right (use a negative value to rotate left). |
| dq.extend(iterable) | Adds multiple elements to the right end. |
| dq.extendleft(iterable) | Adds multiple elements to the left end in reverse order. |
| OrderedDict() | Creates a dictionary that preserves insertion order. |
| od.move_to_end(key) | Moves the specified key to the end (or the beginning) of the dictionary. |
| od.popitem(last=True) | Removes and returns the last item (or the first item if last=False). |
Sample Code
from collections import deque, OrderedDict
# Basic deque operations
dq = deque([1, 2, 3])
dq.append(4) # Add to the right → [1, 2, 3, 4]
dq.appendleft(0) # Add to the left → [0, 1, 2, 3, 4]
print(dq) # deque([0, 1, 2, 3, 4])
dq.pop() # Remove from the right → 4
dq.popleft() # Remove from the left → 0
print(dq) # deque([1, 2, 3])
# rotate: shift elements n steps to the right
dq.rotate(1)
print(dq) # deque([3, 1, 2])
# With maxlen, elements that overflow are automatically dropped
dq2 = deque(maxlen=3)
for i in range(5):
dq2.append(i)
print(dq2) # deque([2, 3, 4], maxlen=3)
# Basic OrderedDict operations
od = OrderedDict()
od['a'] = 1
od['b'] = 2
od['c'] = 3
print(list(od.keys())) # ['a', 'b', 'c']
# Move a key to the end
od.move_to_end('a')
print(list(od.keys())) # ['b', 'c', 'a']
# Move a key to the beginning
od.move_to_end('a', last=False)
print(list(od.keys())) # ['a', 'b', 'c']
# Remove the last item with popitem
key, val = od.popitem(last=True)
print(key, val) # c 3
Notes
By setting a maximum length (maxlen), a deque can serve as a fixed-size queue or a sliding window. When you add elements beyond the maximum length, elements are automatically dropped from the opposite end. It is well suited for both queue (FIFO) and stack (LIFO) use cases, and replacing a list with a deque can significantly improve performance for front-end operations.
OrderedDict retains relevance even in Python 3.7 and later, where regular dictionaries already preserve insertion order. It provides features not available in regular dictionaries, such as move_to_end() and order-aware equality comparisons. A common use case is implementing an LRU (Least Recently Used) cache.
If you find any errors or copyright issues, please contact us.
シェアする