Bag ADT: Introduction, Operations, and Implementations

This report provides a discussion on scenarios in which the Bag ADT can be used and why it’s a better alternative to other abstractions. It covers the introduction, operations, and implementations of the Bag ADT.

Assignment
Student
Course
Instructor
Date

Contents
Introduction.................................................................................................................................................3
Part 1...........................................................................................................................................................3
Bag ADT.......................................................................................................................................................3
Part 2...........................................................................................................................................................4
Bag ADT with Arrays....................................................................................................................................4
Conclusion...................................................................................................................................................4
References...................................................................................................................................................4

Introduction
A Bag object is a collection of objects with no order containing none or more elements of the
same type (homogenous bag) or of different types (heterogeneous bag). Any implementation of a
collection of objects has to factor in operations revolving around the addition, removal or
examination of the objects contained in the collection. In the Queue and Stack abstractions, the
order used to place the elements in the container is very important it related to the order in which
the elements are removed. For the Bag abstraction insertion and removal of objects is completely
random. This report provides a discussion on scenarios in which the Bag ADT can be used and
why it’s a better alternative to other abstractions.
Part 1
Bag ADT
A Bag is perhaps the most basic of all the other collection of data structures thus it can be used
for almost any application that does not need keeping track in which the elements in the
collection were inserted (Chauhan, 2015). The basic operations supported by the Bag abstraction
are;
 Add – Inserting a value into the bag.
 Remove- Removing a value from the bag.
 Contains- Checking if a value exists in a bag.
 Size- Getting the size of the bag.
 Iterator- iterating over the collection of values.
A good example of a real-life scenario where a Bag can be implemented is a spelling checker.
The spelling checker would place the dictionary of the words that are spelled correctly into a
bag. To test whether a word is spelled correctly, the word is checked against the words contained
in the bag and flagged if it’s found. This would be applicable for an online checker. For an off-
line checker the words that are spelled correctly are inserted in one bag and the words in a
document are inserted into another bag. The difference between the two bags are then computed
and the words that are found in the document and not in the dictionary are printed as the
misspelled words.
A Bag is better than most of the other abstract data collections like queues and stacks because
implementation of a bag can be done using different techniques. The most important concept of a
bag is that it allows random insertions and can allow duplicates (Wayne, 2014). This makes the
Bag implementation more suitable for implementations that need to perform search or delete
operations and not just iterating over the items.

Part 2
Bag ADT with Arrays
An array data structure is a collection of objects of the same type. When an array is declared, memory
space is reserved to hold the specific values of the array. This means that declaring an array whether its
empty or leads to allocation of memory. An example of an array in java can be demonstrated using the
following code;
Int[] cards=new int[4];
for(int i=0;i<cards.length;i++){
cards[i]=i++;
System.out.println(cards[i]);
}
The code above demonstrates the declaring of an array and then using a loop to assign values to the array
and display the value allocated in each slot of the array.
The decision on whether to utilize a fixed-side array or a dynamically-resizable array lies on the type of
the data being stored. If the type of data is known for example a deck of cards this can be stored in a
fixed-size array but if the size of the data is not known and can grow exponentially then using a
dynamically-sized array is ideal. To implement an ADT Bag using arrays in java we can use a Binary
Search Tree.
Conclusion
A Bag is an abstract collection that is not specifically tied up to one type of implementation but
depends on how the user wants to implement the bag. This makes the bag a better option to use
in scenarios that require use of duplicates and random insertions.
References
Chauhan, A. (2015). Abstract Data Types - GeeksforGeeks. Retrieved 18 July 2019, from
https://www.geeksforgeeks.org/abstract-data-types/
Wayne, K. (2014). Bags, Queues, and Stacks. Retrieved 18 July 2019, from
https://algs4.cs.princeton.edu/13stacks/