Bag / Multiset implementation with LinkedList in Java

A Bag / Multiset is a collection where removing items is not supported—its purpose is to provide clients with the ability to collect items and then to iterate through the collected items.

Unfortunately, there is no direct implementation available in Java collection framework. But, you can take the help of other open source libraries such as Apache Common Collections or Guava libraries (Google Collections) or GS Collections. Today, we’ll implement Bag / Multiset in plain java with linked lists.

Image credit: CodeThinked


Bag / Multiset implementation: Below is the ADT that we are going to follow for implementation of Bag / Multiset

As we are implementing Bag / Multiset using linked lists, we need private inner class to support Nodes in linked list of type Node.

As Bag by definition, we can only insert and retrieve. For retrieving objects, our class is implementing Iterable<T>
which has the interface method to be overridden in our class.

What is Iterator?

Iterator is an object that enables you to traverse elements in a collection. Iterator<T> interface has below 3 methods of contract.

Retrieving elements of Bag

We’ll implement the way to access elements of collection Bag / Multiset using ListIterator private inner class. You go through below implementation which is self explanatory with the comments provided.

Adding elements to Bag

How to add elements to Bag? here is the implementation.

Supporting methods

While implementing any ADT for a data structure the common properties that we need to know about the data structure is

  1. size of the collection and
  2. To check whether the collection is empty?

Download Source

Leave a Comment