Implementation of Bag ADT: Use Cases & Array Structures

This report provides an overview of the Bag Abstract Data Type (ADT) and its implementation, focusing on scenarios where it proves to be a better alternative than other data abstractions like Queues and Stacks. It highlights the basic operations supported by the Bag abstraction, including Add, Remove, Contains, Size, and Iterator. A practical example, such as a spelling checker, illustrates the Bag's utility in real-world applications, contrasting online and offline implementations. The report further explores the implementation of the Bag ADT using arrays in Java, discussing the use of fixed-size and dynamically-resizable arrays based on the nature of the data being stored. It concludes by emphasizing the flexibility of the Bag ADT, making it suitable for scenarios requiring duplicate entries and random insertions, and mentions the use of a Binary Search Tree for array-based implementation.

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/