| | |
In stacks and queues, the order elements are added to the collection is important, as the order in which elements are removed is related to the order in which they are inserted. A bag is a type of collection for which the order of insertion is completely irrelevant. This might be due to a requirement that once items are added to a bag, they are not allowed to be removed. Alternatively, one might allow the removal of an occurrence of some particular item, but have no mechanism for removing the $k^{th}$ item added, regardless of $k$.
Bags generally allow for the collection of duplicate objects as well. When duplicates are disallowed, the collection might be better described as a set instead of a bag.
Using the name "bag" to describe this abstract data type, we again suggest a collection familiar to everyday experience. A bag of marbles provides a good mental image.
Bags turn out to be particularly useful to store incidence information in networks (i.e., information on whose connected to whom). For example, to represent a computer network, one might keep for each computer in the network a bag of other computers to which it is connected. Similarly, to represent a molecule, one might keep for each atom in the molecule a bag of atoms to which it is bonded.
The ways to implement a bag are extremely varied. Simple implementations can be accomplished with arrays or linked lists, while more sophisticated implementations might include binary search trees, hash tables, and other more complex data structures. As mentioned above, sometimes bags are restricted to simply accumulating objects (along with the means to iterate through those items collected), while other implementations allow for removal of specified items, or checking to see if a particular item is contained in the bag.