Collections

Introduction to Collections

Today I am going to dive into a concept known as "Collections" in Java.  This blog post will be guided by the Collections chapter of Java Tutorials book denoted in the introduction.

Collections are defined as an object that groups multiple elements into a single unit.

Some of the actions that are associated with Collection are

1. Store - Collections are used to store many elements into one place
2. Retrieve - To retrieve data stored inside of the Collection and return it to who asked for it
3. Manipulate - To manipulate data stored inside of the Collection, but to not change other data.

The Java Collections Framework allows us to easily recreate and utilize different data structures so programmers don't have to.  

A few benefits includes...

1. Reducing Programming effort
2. Increases Programming speed and Quality
3. Allows communication between unrelated APIs
4. Fosters code reuse

You may find yourself asking, "This sounds like something familiar to what I know."  Actually if you have done any work with basic data structures in Java, you are already using the Java Collection Framework!  The JCF provides the interfaces for Lists(ArrayLists), Queues(LinkedLists), Maps(HashMap), and many more examples.

For each collections framework, it contains an interface, an implementation, and algorithms.

ArrayList Implementation

We take a look at ArrayList as an example.

An ArrayList implements a List interface.

Looking further to how ArrayLists are implemented...  Source Code

Examining the java file on a glance, we see the line...

private transient Object[] elementData;

This line lets us know that arrayList is actually made from an array.  Upon future investigation on the topic, I found a thread post by user Abhay Agarwal here where they pointed out that an arrayList is in its most basic form an auto-growable array, which can increase its size at run-time.  

As to determine how the array grows in the way that ArrayLists do, we look at the Java documentation for our answer. Java Doc on ArrayLists

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

The documentation specifies that the ArrayList will be at least the size you need it to be.  Examining Stack Overflow user mgmiller comment on How ArrayList Grow, looking through Sun's implementation of ArrayLists will try to increase the size of the array to 3/2 of the minimum size of the previous array size.  

int newCapacity = oldcapacity + (oldcapacity >> 1)

Using a bitwise operation, oldcapacity is shifted to the right by 1, effectively dividing its value by 2 and adding it to the original oldcapacity.  Therefore we end up with 3/2 of the old capacity. After the proper size is determined, the contents of the old array is copied into the new array.

While this is Sun's implementation of the auto-growable function of ArrayLists, the JavaDoc specifically specifies that one should not rely on this exact formula when programming.  Therefore, we are left to assume that ArrayLists may perform something similar to this method.

Traversing Collections

There are two ways to traverse Collections - 1) for-each loop 2) Iterators

All collections are able to use the for-each loop to go to each value(not index) of a Collection.  Take for example traversing an arrayList.

for(int n : myArrayList) {

System.out.println(n);

}

This simple for-each loop will print all integer values from myArrayList(note not the index).  In essence, the statement is saying, "For each integer in myArrayList, print it."  

The collection interface extends Iterable<E>, therefore all classes that a part of the Java Collection Framework are able to utilize an iterator to traverse through each value of its data.

The iterator class provides 3 methods for which you can work with: hasNext(), next(), and remove();  These form the basis for what you need to traverse through a Collection.

public interface Iterator<E> {

boolean hasNext();

E next();

void remove();

}

Card Dealing Example

I thought that this was a fun little example to see the power of Collections found in Java Tutorials.  

public static <E> List<E> dealHand(List<E> deck, int handsize) {

int decksize = deck.size();

List<E> handView = deck.subList(decksize- handsize, decksize);

List<E> hand = new ArrayList<E> (handView);

handView.clear();

return hand;

}

This method takes in a deck and the number of cards you want to draw.  Then the size is ascertained from the given deck, and the built-in method subList(from, to) which gives back the index from the size - the number of cards you want to draw, to the last card, effectively giving you the last set of cards.  From this new list, a separate ArrayList is created from this set.  When handView is cleared, the elements from handView are removed.  This is reflected in the original list deck, and therefore those cards are removed.

This basic function takes a deck you specify and you give it a number of cards and it will take the top five cards from the deck, returning the number of cards you specified as a list.  With collections, you are able to write code only having to import the data structures you need from java.util.  With each collection, a number of methods are included.  In the example above, we see that List contains the functions size() and subList().

Summary

I think this would be a good place to stop for the night!  As usual, here are some key points from today's blog post.

1. Collections are a way for programmers to store multiple elements in a single location.
2. Collections are implemented in Java Collection Framework
3. Collections provide the basis for reusable data structures
4. ArrayList are implemented as arrays that can automatically resize when needed
5. Collections can be traversed with a for-each loop or by an iterator

In the future, I will try to post my full code examples for people try out for themselves.  Thank you for reading this, and hope you check back for more programming adventures in the future!

~James