Collections in Java

Collection framework has one interface at top i.e. Collection. It is extended by Set, List and Queue interfaces. Map interface is also part of collection framework, but it does not extend Collection interface. 

List

A list is an ordered collection of elements. Its main implementations are ArrayList and LinkedList. ArrayList offers easier access of elements where as LinkedList offers faster add/delete.

ArrayList is internally implemented as an array of objects.

List lst = new ArrayList();

lst.add("item");

lst.addAll(set);

lst.get(1);  //or iterate and print

lst.set(2,"new item");  

lst.remove(2);

LinkedList uses nodes with each node pointing to the next node.

Set

Set is a collection of unique elements. It relies on equals() method to check for equality. Its main implementations are HashSet and TreeSet. The TreeSet is sorted as well. So addition/deletion is faster with a TreeSet. But HashSet offers easy retrieval.

Hashing is a technique of converting objects into numbers. This number is then used to identify a corresponding bucket. In HastSet, each bucket stores a set of elements. 

Set set = new HashSet();

set.add("item");

set.get(1); //or iterate and print

set.set(2,"new item");

lst.remove(2);

A TreeSet is internally implemented as a binary tree.

Queue

Queue is a FIFO based collection. LinkedList implements both List and Queue. A Deque is a double ended queue that can add or remove from both ends.

Map

Map is a collection of entries or key/value pairs. Its main implementations are HashMap and TreeMap. The keys have to be unique with one null key allowed. HashMap is preferred for easier insert, delete and retrieval of elements. TreeMap ensures that the keys are sorted.

HashMap is also implemented using hashing. There are buckets saved as an array. The hash function finds the bucket index from the key. Multiple keys can go into the same bucket. Each bucket stores the starting address of entries (key/value pairs) stored as linked lists. 

HashMap<String, Integer> map = new HashMap<>();

map.put("a", 10); //same for add,update

map.put("b", 30);

map.put("c", 20);

Integer a = map.get("b");

map.remove("c");

A TreeMap is internally implemented as a binary tree of entries.

Concurrent Collections

Concurrent Collection objects work on the clone, so they are thread safe. They are different from the synchronized Collections in that in synchronized Collections, locking is at the object level where as in Concurrent Collections, locking is at a much granular level like at a hash bucket. So Concurrent Collections do not throw Concurrent modification exception when we try to modify a Collection while iterating, thereby changing fail-fast to fail-safe.

CopyOnWriteArrayList This is the concurrent version of ArrayList

CopyOnWriteArraySet This is the concurrent version of a HashSet

ArrayBlockingQueue This queue waits for space to be vacated before inserting and space to be filled before removing. So this can be used in wait-notify issues.

ConcurrentHashMap This is the concurrent implementation of HashMap.

Collections class

Collections is a utility class that provides various static methods to work on Collection APIs like sort, reverse, min, max, copy etc.

Comparator

Classes like String and Integer implement the Comparable interface to provide a natural sorting order. Both TreeSet and TreeMap store elements in the sorted order where as other collection APIs can use Collections.sort() to sort their elements. However, it is the comparator that defines precisely what the sort order means. There are two ways of sorting.

1. Using Comparable interface

class A implements Comparable {

    public int compareTo(A a) {

        return this.compareTo(a);

    }

}

Collections.sort(list);

2. Using Comparator interface

class B implements Comparator {

    public int compare(B b1, B b2) {

        return b1.compareTo(b2);

    }

}

Collections.sort(list, new B());