What are the advantages of using a Bag data structure over others like Set or Linkedlist for a graph implementation API

Question

Here is the sample code to go with the question. This API is trying to implement a graph with an adjacency-list representation as an array of Bags indexed by each of vertices in the graph.

public class Graph{

private final int V;          //no. of vertices
private Bag<Integer>[] adj;  // A bag for each vertex to store all adjacent vertices
.
.
.
}

Is there any advantage of using a Bag here over a linked list or a Set. I know that bags are unordered but why go with an unordered list when they don't save us time or space?

Answer 1

Each data structure can be used under different circumstances:

Set (specifically HashSet) can be list of unordered unique elements. On the other hand, Bags are multisets (unordered collections that may contain duplicate elements).

As for LinkedList they provide easier link manipulation i.e. adding elements at different places, is much easier (constant time).

Answer 2

A Bag is likely implemented with a binary search tree or hash table, giving us O(log n) or O(1) searches. A linked list is going to give O(n) searches.

A Set only allows unique elements, so if you need to store duplicates you need a Bag. The TreeSet or HashSet in the Java Collections library will give us O(log n) or O(1) searches, respectively.

In general, the Set or Bag interfaces will be more suitable when you often need to perform search or delete operations. If you just need to add to the end of the collection and iterate over it, there wouldn't be much difference.

Answer 3

Data types like bag, queue, and stack, differ in the specification of which object is to be removed or examined next.

A bag is a collection where removing items isn't supported. Bags purpose is to provide clients with the ability to collect items and then to iterate through the them.

API Bag (Java)

public class Bag<Item> implements Iterable<Item>
    Bag() // creates an empty bag
    void add(Item item)
    boolean isEmpty()
    int size()

Bag.java

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Bag<Item> implements Iterable<Item> {
    private Node<Item> first;
    private int n;

    private static class Node<Item> {
        private Item item;
        private Node<Item> next;
    }

    public Bag() {
        first = null;
        n = 0;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return n;
    }

    public void add(Item item) {
        Node<Item> oldfirst = first;
        first = new Node<Item>();
        first.item = item;
        first.next = oldfirst;
        n++;
    }

    public Iterator<Item> iterator()  {
        return new LinkedIterator(first);
    }

    private class LinkedIterator implements Iterator<Item> {
        private Node<Item> current;

        public LinkedIterator(Node<Item> first) {
            current = first;
        }

        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

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

Answer 4

In addition to the other answers, the major difference between a Bag and other unordered data structures i.e. a Set - is that Bags do not support the removal of items once they've been added.

An example use case would be a special logging system where we never intend on deleting past insertions. Or to ensure immutability in highly concurrent systems.

Please see https://algs4.cs.princeton.edu/13stacks/ for an accurate description and comparison of bags against other data structures.