Java standard library has several interfaces for collections of objects. For a structure map, see here.

Here are common methods from each interface (Here I list the non-generic interfaces for simplicity. Adding support for generics does not add much conceptual complexity.)

Iterable Interface

Father interface of Collection.

  • retrieval: iterator (returns a iterator)
  • others: forEach (takes in a lambda consumer)

Collection Interface

Extends Iterable. Father interface of List, Queue and Set.

  • comparison: equals (this is testing whether each elements match)
  • membership test: contains, containsAll
  • retrieval: toArray
  • size: size, isEmpty

The below methods are optional (classes implementing Collection interface may throw UnsupportedOperationException for the following methods).

  • modification: add, addAll,remove, clear, removeIf (takes in a lambda predicate),
  • set operation: removeAll (set difference, takes in another collection and remove all seen in that collection), retainAll (set intersection, takes in another collection and retain all seen in that collection)

List Interface

Extends Collection. Supports all optional operations from Collection.

  • membership test: indexOf, lastIndexOf
  • retrieval: get, listIterator (return a ListIterator type, which extends Iterator and adds previous and hasPrevious.)
  • view: `subList`
  • modifying: replaceAll
  • other: sort

LinkedList, ArrayList, Vector implements List.

Queue Interface

Extends Collection.

Queue action Throws exception Returns special value
Insert add (from Collection) offer
Remove remove (from Collection)> poll
Examine element peek

Deque (pronounced as “deck”) interface extends Queue (but honestly we use a different set of renamed methods):

Action direction Head Head Tail Tail
Deque action Throws exception Returns special value Throws exception Returns special value
Insert addFirst offerFirst addLast offerLast
Remove removeFirst pollFirst removeLast pollLast
Examine getFirst peekFirst getLast peekLast

Deque also has removeFirstOccurence and removeLastOccurence as convenient methods. Of course, the set of methods from Queue still do what they should do in Deque.

How could an insertion operation fail? Sometimes the collections are implemented with capacity limit. Adding upon limit reached results in failure. In this case, add would throw IllegalStateException while offer returns false and cancels the insertion.

PriorityQueue implements Queue.

Queue has a dedicated interface while stack does not. In Java, stacks are represented in Java with the Stack class (and the generic version, of course). Stack extends Vector which implements List. Unlike Queue, methods in Java Stack class follow the traditional naming: push, pop (throw error if stack is empty), peek (throw error if stack is empty), search (returns base-1 index), empty.

Set Interface

Implements Collection. Has basically the same set of methods as Collection.

Set has two prominent branches of children.

  • The first lineage goes to TreeSet, passing through SortedSet interface and NavigableSet interface.

SortedSet gives the set the ability to be sorted. Thus, we have first, last.
SortedSet also supports view from headSet, tailSet and subSet (takes in a lower and/or upper bound and return a SortedSet view). Attempts to add elements out of the original bound to the view are disallowed.

NavigableSet gives the set the ability to find closet target. Methods lower, floor, ceiling, and higher return elements respectively <, <=, >= and > a given element, returning null if there is no such element.
NavigableSet has an additional view descendingSet and an additional iterator descendingIterator.
NavigableSet also supports deque-like methods pollFirst and pollLast.

Finally, TreeSet is just a NavigableSet implementation using TreeMap. Hence, no extra methods are added except for the ones it gets from other interfaces (clone from Cloneable etc).

The generic version TreeSet<T> requires either that T be Comparable, or that a Comparator is supplied as the first argument in constructor. e.g., SortedSet<String> rev_fauna = new TreeSet<String>(Collections.reverseOrder());

  • The second is hash sets.

HashSet is actually implemented with HashMap. It has no special methods other than those inherited from father interfaces except for the ones it gets from other interfaces (clone from Cloneable etc). LinkedHashSet, extends HashSet, is just a hash set that also maintains a doubly-linked through all entries to guarantee a predictable ordering.

Take note: size of all Set belongs to O(n), not O(1).

Map Interface

Independent all previous interfaces, but has similar methods.

  • size: size, isEmpty
  • modification: put, putAll, putIfAbsent, merge, remove, replace, clear
  • comparison: equals
  • membership test: containsKey, containsValue
  • view: entrySet, keySet, values (returns a multiset)
  • retrieval: get
  • others: forEach (takes in a lambda biconsumer)

Construction Ongoing

This is not a finished post. The final version may have drastic differences as compared to this draft.