Collections

• A collection is a container: it stores a group of objects.
• All elements in the collection are the same type.
• A collection is used to hold objects when the order of the objects doesn't matter. Objects are retrieved using a key field: some part of the object that is used to identify it.
• Stacks and queues are accessed by position, collections are accessed by value.
• There are many data structures that provide this capability: lists, maps, tables, search trees; this is the most basic of all these.
• The equals method is used to compare the key field and find a matching object in the collection.
• Duplicate elements are allowed in a collection. Elements are considered to be equal if the equals method returns true when comparing the two elements.
• Null elements are not supported.
• Collections do not provide iteration through the collection. If you need to access all elements, to display or update them for example, then you need to use a different data structure.

Collection Interface

The Collection interface from our textbook.

Notice that errors and exceptional conditions are handled differently than they were in the Stack and Queue classes. The add method doesn't throw an exception if the Collection is full; instead it returns false to indicate that the object wasn't added. Similarly, the contains method returns true if the object is in the Collection and false if not. The get method returns a matching object, or null if no matching object is found.

So now we have seen three ways to handle the "my data structure is full" condition:

• throw an exception
• make it bigger so it never gets full
• return false to indicate that the object couldn't be added

We have the same options for handling problems in deleting (the data structure is empty or the object to be deleted is not found) and searching (the object is not found).

Collection Implementation: Array

Some comments on the array implementation:

• The first Collection implementation uses an array. Like the Stack, the Collection array is a fixed size, so it's possible for the Collection to be full.
• The first item is added to the Collection in location [0]. Each new item is added in the next location in the array. This is the same way that push works in the stack.
• The get, contains, and remove methods all need to search the Collection for an item that matches the parm. In the Collection class the method find does this searching, and it is called by the other methods.
• I don't like the way the designers use the location field with the find method. It is better to have the find method return the location, since it's always used right after the call to find. It's the value computed by find; it doesn't need to be a field because it isn't part of the data structure. Making it a field is like using a global variable.
• Since the order of elements is not fixed, the remove method can move the last element in the array to the position of the removed item. This avoids the need to move all of the following elements down to fill the gap.

Here is the ArrayCollection class.

Example - ArrayCollection

Suppose we have

ArrayCollection<String> myStrings = new ArrayCollection();

Draw the collection (the fields elements and numElements) after each of the following, and show any return value or output:

myStrings.add("true");
myStrings.add("blue");
myStrings.add("yes");
myStrings.add("green");
myStrings.add("sun");
myStrings.add("snow");
String str = myStrings.get("blue");
str = myStrings.get("red");
myStrings.remove("blue");
myStrings.remove("green");

Complexity

Look at the code for the ArrayCollection methods. For a Collection containing N elements, what is the best case and worst case of each of the following? Count the number of times each statement executes as a function of N, then get the big O.

add

remove

contains

get

isFull

isEmpty

size

Collection Implementation: Linked

Some comments on the linked implementation:

• The LinkedCollection implementation uses a linked list so it's not possible for the Collection to be full.
• Each new item is added to the Collection at the front of the list, since that's the most efficient place to add it. This is the same way that push works in the stack.
• The get, contains, and remove methods all need to search the Collection for an item that matches the parm. In the Collection class the method find does this searching, and it is called by the other methods. I have a similar objection to the design of find that I have with the array based collection class.
• To remove item A from a linked list, we need a pointer to the item before A. The find method uses location to search for the item to be removed. The location field starts out pointing to the first node. Each step in the search contains:

     previous = location;
     location = location.getLink();
     		

  Thus previous always points to the node before location. When the item to be removed is found, previous points to the node before.

Here is the LinkedCollection class.

Complexity

Look at the code for the LinkedCollection methods. For a Collection containing N elements, what is the best case and worst case of each of the following? Count the number of times each statement executes as a function of N, then get the big O.

add

remove

contains

get

isFull

isEmpty

size

Other Collections: Bags and Sets

The book presents two other collection classes, Bags and Sets.

You will see different definitions of a Bag in different references. Remember that the Collection allows duplicate elements. In our textbook, a Bag is a Collection with the following additional methods: