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 aListIteratortype, which extendsIteratorand addspreviousandhasPrevious.) - {% post_link Unfamiliar-OOP-Concepts-Adaptor-and-More 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 throughSortedSetinterface andNavigableSetinterface.
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)
This is not a finished post…