Package algs13

Class ResizingArrayBag<Item>

java.lang.Object
algs13.ResizingArrayBag<Item>
All Implemented Interfaces:
Iterable<Item>

public class ResizingArrayBag<Item> extends Object implements Iterable<Item>
The ResizingArrayBag class represents a bag (or multiset) of generic items. It supports insertion and iterating over the items in arbitrary order.

This implementation uses a resizing array. See

invalid reference
LinkedBag
for a version that uses a singly linked list. The add operation takes constant amortized time; the isEmpty, and size operations take constant time. Iteration takes time proportional to the number of items.

For additional documentation, see Section 1.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:
Robert Sedgewick, Kevin Wayne
  • Field Details

  • Constructor Details

  • Method Details

    • isEmpty

      public boolean isEmpty()
      Is this bag empty?
      Returns:
      true if this bag is empty; false otherwise
    • size

      public int size()
      Returns the number of items in this bag.
      Returns:
      the number of items in this bag
    • resize

      private void resize(int capacity)
    • add

      public void add(Item item)
      Adds the item to this bag.
      Parameters:
      item - the item to add to this bag
    • iterator

      public Iterator<Item> iterator()
      Returns an iterator that iterates over the items in the bag in arbitrary order.
      Specified by:
      iterator in interface Iterable<Item>
      Returns:
      an iterator that iterates over the items in the bag in arbitrary order
    • main

      public static void main(String[] args)
      Unit tests the ResizingArrayBag data type.
      Parameters:
      args - the command-line arguments