Imagine dropping marbles into a bag. You can add another marble, or pour them out to count what you have. A bag works much the same way: it holds elements without promising where any one of them will appear when you go through them. section 7.11
A bag has just two operations:
- Insert one element. Duplicates are allowed. section 7.10
- Iterate through every element. The order is not guaranteed, even across repeated passes. section 7.10
Unlike an array, a bag offers no indexed access and does not promise insertion order. It also has no search or removal operation. That makes it useful when collecting elements matters but their order does not. section 7.10 section 7.13
Counting what is inside
Put marbles of several colors into a bag, then iterate through it to count the total and the number of each color. A second pass might visit them in a different order, but those counts should stay the same. section 7.11
The two-operation rule defines the bag as an abstract data type; it does not dictate how to store its elements. One Python implementation wraps a singly linked list in a Bag class. Its insert method inserts at the front of that list, while traverse returns the list’s traversal. The resulting order is an implementation detail, not a promise to callers. section 7.10 section 7.12
class Bag:
def __init__(self):
self._data = SinglyLinkedList()
The constructor creates the singly linked list that stores the bag’s elements. section 7.12
def insert(self, value):
self._data.insert_in_front(value)
Inserting into the bag delegates to front insertion on the linked list. section 7.12
def traverse(self):
return self._data.traverse()
Traversing the bag delegates to the linked list’s traversal. section 7.12
