Data Structures & Algorithms Lecture Notes

6 October 2009 • Java Collections

Outline

• The Java Collection Framework.

• Interfaces

• Implementations

Collections

• The Java Collection Framework (JCF) contains

  • Interfaces describing collection behavior.

  • Implementation classes providing data structures.

  • Abstract classes for other implementations.

• Also other odds and ends: backwards compatibility, adapters, and such like.

Objectives

• Gather and organize several related and common data structures.

  • Gather and organize along object-oriented (polymorphic) lines.

• Provide a structure for developing other, more specialized data structures.

• Provide a mechanism for decoupling system components via consistent abstractions.

• Design and implementation leverage.

Collection Interface Hierarchy

'

Collection Interface

• A group of elements (objects).

  • Elements are ordered or not, duplicated or not.

  • The interface is generic in the element type.

• The Collection interface extends the Iterable interface.

  • Collections respond to the for-each statement.

Collection Methods

• Defines around 13 methods, some are optional.

  • add elements: add(), addAll()

  • removing elements: clear(), remove(), removeAll(), retainAll()

  • queries: contains(), isEmpty(), size()

  • conversions: toArray()

Optional Methods

• The element adding and removing methods are optional.

  • Some collections are immutable.

• Collection implementations should throw a UnsupportedOperationException when inapplicable optional methods are called.

Quiz Time!

• The addAll() signature is

  boolean addAll(Collection<? extends E> c)
  

  The removeAll() signature is

  boolean removeAll(Collection<?> c)
  

  Why are the type variable declarations in the two signatures different?

Collection Interface Hierarchy

'

The Queue Interface

• The Queue interface extends the Collection interface.

  		Throws		Returns
  		exception		special value
  Insert		add(e)		offer(e)
  Remove		remove()		poll()
  Examine		element()		peek()

• The behavior of the two method groups differs on error conditions.

The Deque Interface

• The Deque interface extends the Queue interface.

  • It adds front and back versions of the Queue operations.

    addFirst(e), removeFirst(), getFirst()
    offerFirst(e), pollFirst(), peekFirst()
    addLast(e), removeLast(), getLast()
    offerLast(e), pollLast(), peekLast()
    

Collection Interface Hierarchy

'

The List Interface

• The List interface is as expected.

  • However, it does define optional indexed-access methods.

    void add(int index, E element)
    E get(int index)
    boolean remove(int index)
    ListIterator<E> listIterator(int index) 
    

• The List interface is (more or less) implementation independent.

List Iterators

• The ListIterator interfaces extends the Iterator interface.

• Iterator (or cursor) positions lie between adjacent list elements.

  • Or before the first element or after the last element.

  

List Iterator Methods

• The List iterator methods are

  void add(E e)*
  boolean hasNext()
  boolean hasPrevious()
  E next()
  int nextIndex()
  E previous()
  int previousIndex()
  void remove()*
  void set(E e)*
  
  *optional
  

List Navigation

• The next() and previous() methods

  • return the appropriate list element and

  • move the iterator appropriately.

  

List Manipulations

• A new element is added before the next or after the previous element.

  

• Adding to an empty list is easy.

  

Removing Elements

• remove() removes the element returned by next() or previous().

  

• next() or previous() must be called before each call to remove().

Bulk Methods

• Some Collection methods accept a collection of elements.

  boolean containsAll(Collection<?> c)
  boolean removeAll(Collection<?> c)
  boolean retainAll(Collection<?> c)
  

• Bulk methods have the obvious abstract implementation.

  boolean xAll(Collection<?> c)
    boolean b = true
    for (Object o: c)
      b = x(o) && b
    return b 

Interface Declarations

• Remember: for greatest flexibility, use the highest interfaces possible as variable types.

  • Good:

    Set<Integer> iSet = 
      new HashSet<Integer>();
    

  • Bad:

    HashSet<Integer> iSet = 
      new HashSet<Integer>();
    

Implementation Hierarchy

'

Abstract Implementations

• The more practical collection interfaces contain many method definitions.

  • Implementing classes have to implement them all, if only to fail when called.

• The abstract implementation classes provide a skeleton implementation for further development.

  • The concrete class is a child of the abstract implementation class.

Example

• The AbstractQueue class implements the Queue interface.

  public abstract class AbstractQueue<E>
  extends AbstractCollection<E>
  implements Queue<E>

  • It contains around 40 methods.

• The PriorityQueue extends AbstractQueue.

  public class PriorityQueue<E>
  extends AbstractQueue<E>
  implements Serializable

Linked Lists

• The LinkedList class extends the AbstractSequentialList class.

  • And implements the Queue and Deque interfaces.

• The interfaces specify a doubly-linked list.

• The AbstractSequentialList class assumes a dynamic link implementation.

  • That is, indexing is expensive.

Array Lists

• The ArrayList class implements a linked list assuming indexing is cheap.

  • That is, an implementation based on dynamic arrays.

• ArrayLists are more efficient than are Vectors.

  • But ArrayLists aren’t thread safe and Vectors are.

Random-Access Iterators

• The RandomAccess interface indicates efficient indexing.

  • Faster:

    for (int i = 0; i < lst.size(); i++)
      f(lst.get(i))

  • Slower:

    for (Iterator i = lst.iterator(); i.hasNext(); )
      f(i.next())

• RandomAccess contains no methods; it just flags classes with efficient indexing.

Priority Queues

• The PriorityQueue class stores elements in increasing priority order (a min-priority queue).

• The queue elements can implement the Comparable interface.

• A queue can be created with a Comparator implementing, overriding the element comparable, if any.

Where’s Stacks?

• Stacks were added to Java before the Collection Framework (v. 1.0 vs v. 1.2).

'

Summary

• The Java Collection Framework designs and implements a group of common data structures.

• Declare variables with the most abstract interface type possible.

• Keep in mind that retreiving a value through a list iterator also moves the iterator.

References

• Collections (Chapter 13), Core Java vol. 1 eighth ed. by Cay Horstmann and Gary Cornell, Prentice Hall, 2008.

• The Java Collections Trail by Josh Bloch, Sun Microsystems.