TheAlgorithms · KevinMFinch · Oct 13, 2017 · Oct 13, 2017
@@ -0,0 +1,123 @@
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.Scanner;
+
+/**
+ *  The {@code Bag} class represents a bag (or multiset) of 
+ *  generic items. It supports insertion and iterating over the 
+ *  items in arbitrary order.
+ *  <p>
+ *  This implementation uses a singly linked list with a static nested class Node.
+ *  See {@link LinkedBag} for the version from the
+ *  textbook that uses a non-static nested class.
+ *  See {@link ResizingArrayBag} for a version that uses a resizing array.
+ *  The <em>add</em>, <em>isEmpty</em>, and <em>size</em> operations
+ *  take constant time. Iteration takes time proportional to the number of items.
+ *  <p>
+ *  For additional documentation, see <a href="http://algs4.cs.princeton.edu/13stacks">Section 1.3</a> of
+ *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
+ *
+ *  @author Robert Sedgewick
+ *  @author Kevin Wayne
+ *
+ *  @param <Item> the generic type of an item in this bag
+ */
+public class Bag<Item> implements Iterable<Item> {
+    private Node<Item> first;    // beginning of bag
+    private int n;               // number of elements in bag
+
+    // helper linked list class
+    private static class Node<Item> {
+        private Item item;
+        private Node<Item> next;
+    }
+
+    /**
+     * Initializes an empty bag.
+     */
+    public Bag() {
+        first = null;
+        n = 0;
+    }
+
+    /**
+     * Returns true if this bag is empty.
+     *
+     * @return {@code true} if this bag is empty;
+     *         {@code false} otherwise
+     */
+    public boolean isEmpty() {
+        return first == null;
+    }
+
+    /**
+     * Returns the number of items in this bag.
+     *
+     * @return the number of items in this bag
+     */
+    public int size() {
+        return n;
+    }
+
+    /**
+     * Adds the item to this bag.
+     *
+     * @param  item the item to add to this bag
+     */
+    public void add(Item item) {
+        Node<Item> oldfirst = first;
+        first = new Node<Item>();
+        first.item = item;
+        first.next = oldfirst;
+        n++;
+    }
+
+
+    /**
+     * Returns an iterator that iterates over the items in this bag in arbitrary order.
+     *
+     * @return an iterator that iterates over the items in this bag in arbitrary order
+     */
+    public Iterator<Item> iterator()  {
+        return new ListIterator<Item>(first);  
+    }
+
+    // an iterator, doesn't implement remove() since it's optional
+    private class ListIterator<Item> implements Iterator<Item> {
+        private Node<Item> current;
+
+        public ListIterator(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;
+        }
+    }
+
+    /**
+     * Unit tests the {@code Bag} data type.
+     *
+     * @param args the command-line arguments
+     */
+    public static void main(String[] args) {
+        Scanner scanner = new Scanner(System.in);
+        Bag<String> bag = new Bag<String>();
+        while (scanner.hasNext()) {
+            String item = scanner.next();
+            bag.add(item);
+        }
+
+        System.out.println("size of bag = " + bag.size());
+        for (String s : bag) {
+            System.out.println(s);
+        }
+    }
+
+}
@@ -0,0 +1,123 @@
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.Scanner;
+
+/**
+ *  The {@code Bag} class represents a bag (or multiset) of 
+ *  generic items. It supports insertion and iterating over the 
+ *  items in arbitrary order.
+ *  <p>
+ *  This implementation uses a singly linked list with a static nested class Node.
+ *  See {@link LinkedBag} for the version from the
+ *  textbook that uses a non-static nested class.
+ *  See {@link ResizingArrayBag} for a version that uses a resizing array.
+ *  The <em>add</em>, <em>isEmpty</em>, and <em>size</em> operations
+ *  take constant time. Iteration takes time proportional to the number of items.
+ *  <p>
+ *  For additional documentation, see <a href="http://algs4.cs.princeton.edu/13stacks">Section 1.3</a> of
+ *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
+ *
+ *  @author Robert Sedgewick
+ *  @author Kevin Wayne
+ *
+ *  @param <Item> the generic type of an item in this bag
+ */
+public class Bag<Item> implements Iterable<Item> {
+    private Node<Item> first;    // beginning of bag
+    private int n;               // number of elements in bag
+
+    // helper linked list class
+    private static class Node<Item> {
+        private Item item;
+        private Node<Item> next;
+    }
+
+    /**
+     * Initializes an empty bag.
+     */
+    public Bag() {
+        first = null;
+        n = 0;
+    }
+
+    /**
+     * Returns true if this bag is empty.
+     *
+     * @return {@code true} if this bag is empty;
+     *         {@code false} otherwise
+     */
+    public boolean isEmpty() {
+        return first == null;
+    }
+
+    /**
+     * Returns the number of items in this bag.
+     *
+     * @return the number of items in this bag
+     */
+    public int size() {
+        return n;
+    }
+
+    /**
+     * Adds the item to this bag.
+     *
+     * @param  item the item to add to this bag
+     */
+    public void add(Item item) {
+        Node<Item> oldfirst = first;
+        first = new Node<Item>();
+        first.item = item;
+        first.next = oldfirst;
+        n++;
+    }
+
+
+    /**
+     * Returns an iterator that iterates over the items in this bag in arbitrary order.
+     *
+     * @return an iterator that iterates over the items in this bag in arbitrary order
+     */
+    public Iterator<Item> iterator()  {
+        return new ListIterator<Item>(first);  
+    }
+
+    // an iterator, doesn't implement remove() since it's optional
+    private class ListIterator<Item> implements Iterator<Item> {
+        private Node<Item> current;
+
+        public ListIterator(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;
+        }
+    }
+
+    /**
+     * Unit tests the {@code Bag} data type.
+     *
+     * @param args the command-line arguments
+     */
+    public static void main(String[] args) {
+        Scanner scanner = new Scanner(System.in);
+        Bag<String> bag = new Bag<String>();
+        while (scanner.hasNext()) {
+            String item = scanner.next();
+            bag.add(item);
+        }
+
+        System.out.println("size of bag = " + bag.size());
+        for (String s : bag) {
+            System.out.println(s);
+        }
+    }
+
+}