Java - Collections

Collection interface

All Collection implementations classes should provide two general purpose constructors. This however can not be programatically enforced.

1. A no-arg constructor
2. A constructor that takes another Collection as parameter. 

The specification for the contains(Object o) method says: "returns true if and only if this collection contains at least one element e such that (o==null ? e==null : o.equals(e)). This does not mean that o.equals(e) will be called. The collection implementation is free to implement optimisations that avoid calling o.equals(e).

Interfaces

Collection >
Queue<E> | Deque<E> | BlockingQueue<E> | BlockingDeque<E>  
Set<E>   | SortedSet<E> | NavigableSet<E>
List<E> 

Classes

AbstractCollection >
AbstractQueue | AbstractDeque | AbstractSet | AbstractList

AbstractList
ArrayList | Vector | AbstractSequentialList >
LinkedList

AbstractSet >
TreeSet | HashSet | EnumSet


Iteration

1. Iterator<E> - hasNext(), next(), optional - remove()
2. ListIterator<E> extends Iterator<E>
1. Allows iteration in both directions.
2. New methods added are - hasPrevious(), previous(), previousIndex(), nextIndex(), optional - add(E), set(E)   

List<E>

ArrayList

ensureCapacity( newCapacity ), List<E> sublist( from, to ), removeAll( Collection ), retainAll( Collection ) 

• Allows null
• elements are stored in Object[] elementData.
• size (how many elements exist in the List) & capacity ( the maxIndex of the backing array | elements from index size to capacity are null ) are maintained.
• length of elementData = capacity of the List.
• ensureCapacity( newCapacity ) increases the capacity of list by 50%. If 50% is less than newCapacity the new Array size is = newCapacity.  
• CuncurrentModificationException is decided by maintaining modCount.
• trimtoSize() - trims null entries in the backing array Object[] = elementData by creating a copy of the Array.

LinkedList

• Each node is of type LinkedList.Entry
• maintains a reference to header node
• The header node has a null value.

Vector

• Elements stored in Object[] - elementData
• All methods are synchronised on the Vector Instance.
• trimToSize()

HashSet<E>

• Uniqueness is determined in terms of equals(Object) and hashCode() method.
• Backed by a HashMap instance.
• No ordering guarantee
• constant time performance for add(), remove(), contains() & size()

LinkedHashSet<E>

• Hashtable and LinkedList implementation of Set interface with predictable iteration order.
• Maintains doubly LinkedList running through all of its entries.
• Constant time performance for add(), contains() & remove()
• 
  
• Uniqueness is determined in terms of equals(Object) and hashCode() method.
• Backed by a HashMap instance.

SortedSet<E>

• Uniqueness is determined in terms of compareTo(Object) method.
• The Set interface is defined in terms of the equals operation BUT a sorted set performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the sorted set, equal. (Even if equals(Object) returns false).

TreeSet

• A NavigableSet implementation based on TreeMap.
• All values are mapped to the same Object instance referred as PRESENT.
• put( E ) - forwards to TreeMap.put ( E, PRESENT)
• contains( Object ) - Forwards to TreeMap.contains ( Object )
• remove ( Object ) - Forwards to TreeMap.remove ( Object ) == PRESENT   

ConcurrentSkipListSet<E>

• A NavigableSet & SortedSet implementation based on ConcurrentSkipListMap.
• Sorted based on Comparator / Comparable.

EnumSet

• Internally represented as bit-vectors which is extremely compact & efficient.
• Iteration is in natural order ( order of declaration of enum constants)
• Iterator is weakly consistent - does not throw ConcurrentModificationException 

Queue

Dequeue

PriorityQueue

• The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used