Java Collections

A Collection is an object that groups together several objects. The Java Collections framework comprises of...

• Interfaces
• Implementations
• Algorithms

Interfaces & Implementations

The different collection implementations conform to one or more of the generic interfaces shown in the interface hierarchy below...

Interface Hierarchy

Some important Collection interface methods

• size(), isEmpty()
• add(), remove(), contains()
• iterator(), toArray()
• Bulk operations - addAll(), removeAll(), retainAll(), containsAll()

Bulk operations are so called because they operate on entire collections.

Set interface models the mathematical set abstraction. 

• Duplicate elements are not allowed
• No additional methods are defined in this interface
• equals(), hashcode() methods can be used to compare different sets even though their implementations differ
• Implementations
• HastSet - hash table implementation (best performance for most scenarios)
• TreeSet - Red-Black tree implementation
• LinkedHashSet - hash table with a linked list running through it

List is an ordered collection

• Positional access methods - get(), set(), add(), addAll(), remove(), indexOf(), lastIndexOf()
• ListIterator<>, subList()
• Implementations
• ArrayList - best performance for most scenarios
• LinkedList

Queue interface models the queue abstraction

• Typically FIFO type of data structure (except in case of Priority Queues)
• Two types of methods
• Methods that throw exception on failure - add(), remove(), element()
• Methods that return special value on failure - offer(), poll(), peek()
• Implementations
• LinkedList
• PriorityQueue
• ArrayBlockQueue etc

Deque pronounced as deck is a double-ended queue. I like to think of it as a queue-stack hybrid

• Permits operations at both ends of the queue
• Two types of methods
• Methods that throw exception on failure - addFirst/Last(), removeFirst/Last(), getFirst/Last()
• Methods that return special value on failure - offerFirst/Last(), pollFirst/Last(), peekFirst/Last()
• Implements the Queue interface - add(), remove(), offer()... are also available
• Stack operations supported - push(), pop(), peek()
• Implementations
• LinkedList
• ArrayDeque etc

Map is an object that maps keys to values. It models the mathematical function abstraction. 

• No duplicate keys allowed
• Methods - put(), get(), remove(), containsKey(), containsValue()
• Collections views - keySet(), values(), entrySet()
• Implementations
• HastMap - hash table implementation 
• TreeMap - Red-Black tree implementation

SortedSet maintains elements in ascending order or according to the order specified by the Comparator provided at creation time. Several additional methods are provided to take advantage of the ordering. Useful for modelling word lists, membership rolls etc

SortedMap maintains the keys in ascending order or according to the order specified by Comparator provided at creation time. Useful for modelling dictionaries, directories etc

Algorithms
Algorithms provide useful computations like sorting and searching over the elements of the collection. They are polymorphic and can be used across the different collection implementations.