Bag / Multiset implementation with LinkedList in Java

by

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

The ADT

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

public class Bag<T> implements Iterable<T> {
 public Bag(){}
 public void add(T item){}
 public boolean isEmpty(){}
 public int size(){}
}

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

// helper linked list inner class
private class Node {
    //data item for node
    private T item;
    //next pointer to a node.
    private Node next;
 }

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.

public Iterator<T> iterator();

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.

public boolean hasNext();
public T next();
public void remove();

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.

/*** ListIterator. an implementation class for Iterating through collection.*/
    private class ListIterator implements Iterator<T> {
        private Node current = first;

        public boolean hasNext(){ 
        	return current != null;                     
        	}
        public void remove(){ 
        	//currently, not being considered for our simplicity.
        	throw new UnsupportedOperationException();  
        	}

        public T next() {
            if (!hasNext()) 
            	throw new NoSuchElementException();
            T item = current.item;
            current = current.next; 
            return item;
        }
    }

Adding elements to Bag

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

/**
     * 
     * @param item
     */
    public void add(T item){
    	 //take current first to variable
    	 Node oldfirst = first;
    	 //create new node and first is made point to the new created node.
         first = new Node();
         //Feed the node
         first.item = item;
         first.next = oldfirst;
         size++;
    }

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?
 /**
     * 
     * @return
     */
    public boolean isEmpty(){
    	//return true, if size=0;
    	return size==0;
    }
    /**
     * 
     * @return
     */
    public int size(){
    	//return size
    	return size;
    }

Leave a Comment