Java Collections— Oversimplified

More often than not you will need to deal with a group or collection of objects. There are various data structure that you could implement based on your use case and populate the collection of object into the implementation of the DS. Collections framework provides interfaces and concrete implementation of common data structures and algorithms to make the life of developers easier. Let’s have a look at what Java Collections framework has to offer from an oversimplified point of view.

Collection Framework Hierarchy

Collection

Sits atop the Collections Framework hierarchy representing a group of objects. Has no direct concrete implementation but is further extended by more specific interfaces like List, Queue and Set. Although Map is part of Collections Framework, but it doesn’t extend Collection class, more details on that later.

List <Interface>

Maintains insertion order and allows duplicate. Element can be accessed, searched and inserted based on index.

ArrayList<Class> — Resizable-array implementation of the List interface.

• Adding element at any position cost O(n).
• Allows null value and increases capacity by 50% when current capacity is full.
• Fetching element is constant O(1)
• Is not thread safe. Preferred if you have more read operation than write.

LinkedList<Class> — Doubly-linked list implementation of List and Deque which has a linear data structure consisting of nodes where each node holds data value and link to the next and previous node.

• Adding element at any position cost O(1). Allows null value.
• Fetching element is constant O(n)
• Is not thread safe. Preferred if you have more write operation than read.

Vector<Class>—Growable array like ArrayList with below below difference.

• Increases capacity by 100% when current capacity is full.
• Thread safe.

Queue<Interface>

Maintains insertion order and allows duplicate, same as list. So, how are they different? Queue follow FIFO(First In First Out) which means you can only insert element in the end and remove from start.

Deque<Interface> — Double ended queue, which means items can be added and remove from either ends.

ArrayDeque<Class> — Also known as Array Double Ended Queue, is a resizable array implementation of Deque.

• Doesn’t allow null values and is not thread safe.

PriorityQueue <Class>— You know how we said queue follows FIFO? well not this one. As the name suggests, it keeps element in order of their priority and are processed in the same order.

• Elements are either naturally ordered or based on Comparator provided at construction time.
• Doesn’t allow null and is not thread safe. You can use PriorityBlockingQueue for thread safe operation.
• O(log(n)) time for add and poll methods.

Set<Interface>

Collection of distinct elements.

HashSet<Class> — HashSet uses a transient HashMap to save unique elements.

• Insertion order is not maintained and is rather determined based on hashcode.
• Allows null value and is not Synchronized.
• Better suited for search operations.

LinkedHashSet<Class> — A linked-list and hash table implementation of Set. Extends HashSet so has all the same features except that it maintains insertion order. Better used in scenarios where you have more write operations.

TreeSet<Class> — We have a HashSet which maintain unique elements, LinkedHashSet which along with unique element also maintains insertion order, so what more does TreeSet has to offer? TreeSet implements SortedSet which kinda gives away the answer :) TreeSet sorts elements in their natural order or based on a comparator.

Map<Interface>

Saves elements in key-value pair. Preferred when save, write and search operation are based on key. Is part of the Collection Framework but doesn’t extend collection as the public methods in collection such as add, addAll etc doesn’t make sense in terms of key value pair DS.

HashMap<Class> — Saves elements in key value pair and can save only unique keys. The uniqueness of a key is determined based on equals method and the memory location where the key-value pair is to be save is dertmined by the hash value generated by the hashcode method.

Doesn’t maintain order, is not synchronized and allows null key.

LinkedHashMap<Class> — Following the patterns of Set implementation, LinkedHashMap as expected maintains insertion order.

Is not synchronized and allows null key.

TreeMap<Class> — Similar to TreeSet keeps the element in natural order of the key or based on comparator. Doesn’t allow null key.

As always, articles in the oversimplified series are meant to give you a peek into some important yet complex concepts in a simple form. It is highly advisable to read about each of the implementations and concepts in details as these are very important which requires deep dive for all developers.