JAVA Collection Framework

1. Collection

3. List: interface

List is a fundamental and widely-used collection type in the Java Collections Framework. Basically, a list collection stores elements by insertion order (either at the end or at a specific position in the list). A list maintains indices of its elements so it allows adding, retrieving, modifying, removing elements by an integer index (zero-based index; the first element is at 0-index, the second at 1-index, the third at 2-index, and so on). 

3.1 AbstractList: abstract

The AbstractList class in Java is a part of the Java Collection Framework and implements the Collection interface and the AbstractCollection class. It is used to implement an unmodifiable list, for which one needs to only extend this AbstractList Class and implement only the get() and the size() methods.

3.1.1 ArrayList: class

Java ArrayList class uses a dynamic array for storing the elements. It inherits AbstractList class and implements List interface.

The important points about Java ArrayList class are:

• Java ArrayList class can contain duplicate elements.
• Java ArrayList class maintains insertion order.
• Java ArrayList class is non-synchronized.
• Java ArrayList allows random access because array works at the index basis.
• In Java ArrayList class, manipulation is slow because a lot of shifting needs to occur if any element is removed from the array list.

Java ArrayList class extends AbstractList class which implements List interface. The List interface extends the Collection and Iterable interfaces in hierarchical order.

3.1.2 Vector: class

The Vector class implements a growable array of objects. Vectors basically fall in legacy classes but now it is fully compatible with collections.

• Vector implements a dynamic array that means it can grow or shrink as required. Like an array, it contains components that can be accessed using an integer index
• They are very similar to ArrayList but Vector is synchronised and has some legacy method which collection framework does not contain.
• It extends AbstractList and implements List interfaces.

3.1.2.1 Stack: class

Java Collection framework provides a Stack class which models and implements Stack data structure. The class is based on the basic principle of last-in-first-out. In addition to the basic push and pop operations, the class provides three more functions of empty, search and peek. The class can also be said to extend Vector and treats the class as a stack with the five mentioned functions. The class can also be referred to as the subclass of Vector.

4. Queue: interface

The Java Queue interface, java.util.Queue represents a data structure designed to have elements inserted at the end of the queue, and elements removed from the beginning of the queue. This is similar to how a queue in a supermarket works.

The Java Queue interface is a subtype of the Java Collection interface. It represents an ordered sequence of objects just like a Java List, but its intended use is slightly different.

4.1 AbstractQueue: abstract

4.1.1 PriorityQueue: class

A PriorityQueue is used when the objects are supposed to be processed based on the priority. It is known that a queue follows First-In-First-Out algorithm, but sometimes the elements of the queue are needed to be processed according to the priority, that’s when the PriorityQueue comes into play. The PriorityQueue is based on the priority heap. The elements of the priority queue are ordered according to the natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.

4.2 Deque: interface

4.2.1 AbstractLinkedList: abstract

4.2.1.1 LinkedList: class

Java LinkedList class uses a doubly linked list to store the elements. It provides a linked-list data structure. It inherits the AbstractList class and implements List and Deque interfaces.

The important points about Java LinkedList are:

• Java LinkedList class can contain duplicate elements.
• Java LinkedList class maintains insertion order.
• Java LinkedList class is non-synchronized.
• In Java LinkedList class, manipulation is fast because no shifting needs to occur.
• Java LinkedList class can be used as a list, stack or queue.

Java LinkedList class extends AbstractSequentialList class and implements List and Deque interfaces.

4.3 BlockingQueue: interface

The Java BlockingQueue interface, java.util.concurrent.BlockingQueue, represents a queue which is thread-safe to put elements into, and take elements out of from. In other words, multiple threads can be inserting and taking elements concurrently from a Java BlockingQueue, without any concurrency issues arising.

4.3.1 PriorityBlockingQueue: class

Unlike a standard queue, you can't just add any type of element to a PriorityBlockingQueue. There are two options:

• Adding elements which implement Comparable
• Adding elements which do not implement Comparable, on the condition that you provide a Comparator as well

By using either the Comparator or the Comparable implementations to compare elements, the PriorityBlockingQueue will always be sorted.

4.3.2 LinkedBlockingQueue: class

The LinkedBlockingQueue keeps the elements internally in a linked structure (linked nodes). This linked structure can optionally have an upper bound if desired. If no upper bound is specified, Integer.MAX_VALUE is used as the upper bound.

5. Set: interface

5.1 AbtractSet: abstract

5.1.1 HashSet: class

5.1.1.1 LinkedHashSet: class

• It extends HashSet class which extends AbstractSet class.
• It implements Set interface.
• Duplicate values are not allowed in LinkedHashSet.
• One NULL element is allowed in LinkedHashSet.
• It is an ordered collection which is the order in which elements were inserted into the set (insertion-order).
• Like HashSet, this class offers constant time performance for the basic operations(add, remove, contains and size).
• LinkedHashSet is not synchronized. If multiple threads access a hash set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.
• Use Collections.synchronizedSet(new LinkedHashSet()) method to get the synchronized LinkedHashSet.
• The iterators returned by this class’s iterator method are fail-fast and may throw ConcurrentModificationException if the set is modified at any time after the iterator is created, in any way except through the iterator’s own remove() method.
• LinkedHashSet also implements Searlizable and Cloneable interfaces.

5.2 SortedSet: interface

5.2.1 NavigableSet: interface

5.2.1.1 TreeSet: class

TreeSet is one of the most important implementations of the SortedSet interface in Java that uses a Tree for storage. The ordering of the elements is maintained by a set using their natural ordering whether or not an explicit comparator is provided. This must be consistent with equals if it is to correctly implement the Set interface. It can also be ordered by a Comparator provided at set creation time, depending on which constructor is used. The TreeSet implements a NavigableSet interface by inheriting AbstractSet class.
Few important features of TreeSet are as follows:

• TreeSet implements the SortedSet interface so duplicate values are not allowed.
• Objects in a TreeSet are stored in a sorted and ascending order.
• TreeSet does not preserve the insertion order of elements but elements are sorted by keys.
• TreeSet does not allow to insert Heterogeneous objects. It will throw classCastException at Runtime if trying to add hetrogeneous objects.
• TreeSet serves as an excellent choice for storing large amounts of sorted information which are supposed to be accessed quickly because of its faster access and retrieval time.
• TreeSet is basically implementation of a self-balancing binary search tree like Red-Black Tree. Therefore operations like add, remove and search take O(Log n) time. And operations like printing n elements in sorted order takes O(n) time.

3. Map: interface

3.1 AbstractMap: abstract

This abstract class provides a skeletal implementation of the Map interface, to minimize the effort required to implement this interface.

3.1.1 HashMap: class

HashMap Extends AbstractMap and provides Hash table based implementation of the Map interface. Refer HashMap in Java to know more about HashMap in Java.

3.1.1.1 LinkedHashMap: class

LinkedHashMap Extends HashMap and provides a specialized implementation for a Map that maintains the iteration ordering, which is normally the order in which keys were inserted into the map.  Refer LinkedHashMap in Java to know more about LinkedHashMap in Java.

3.1.2 IdentityHashMap: class

IdentityHashMap Extends AbstractMap and provides implementation where reference-equality is used in place of object-equality when comparing keys and values. In an IdentityHashMap, two keys k1 and k2 are considered equal if and only if (k1==k2) where as in normal Map implementations two keys k1 and k2 are considered equal if and only if (k1==null ? k2==null : k1.equals(k2)).

3.1.3 EnumMap: class

EnumMap Extends AbstractMap and provides specialized Map implementation for use with enum type keys.

3.1.4 WeakHashMap: class

WeakHashMap Extends AbstractMap and provides Hash table based implementation of the Map interface, with weak keys. An entry in a WeakHashMap will automatically be removed when its key is no longer in ordinary use.

3.2 SortedMap: interface

SortedMap is an interface in collection framework. This interface extends Map interface and provides a total ordering of its elements (elements can be traversed in sorted order of keys).

3.2.1 NavigableMap: interface

The Java NavigableMap interface, java.util.NavigableMap, is a sub-interface of the Java SortedMap interface. The NavigableMap interface has a few extensions to the SortedSet interface which makes it possible to navigate the keys and values stored in the map. I will take a closer look at these navigation methods in this Java NavigableMap tutorial.

3.2.1 TreeMap: class

TreeMap Extends AbstractMap and implements NavigableMap to provide an ordered Map. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used. Refer TreeMap in Java to know more about TreeMap in Java.

3.3 Dictionary: interface

util.Dictionary is an abstract class, representing a key-value relation and works similar to a map. Given a key, you can store values and when needed can retrieve the value back using its key. Thus, it is a list of key-value pairs.

3.3.1 Hashtable: class

Hashtable was part of the original java.util and is a concrete implementation of a Dictionary. However, Java 2 re-engineered Hashtable so that it also implements the Map interface. Thus, Hashtable is now integrated into the collections framework. It is similar to HashMap but is synchronized. Like HashMap, Hashtable stores key/value pairs in a hash table. When using a Hashtable, you specify an object that is used as a key and the value that you want to link to that key. The key is then hashed, and the resulting hash code is used as the index at which the value is stored within the table.

4. Advantages

4.1 List

Arrays are not resizable

• Reduced development effort by using core collection classes rather than implementing our own collection classes.
• Code quality is enhanced with the use of well-tested collections framework classes.
• Reduced effort for code maintenance by using collection classes shipped with JDK.
• Reusability and Interoperability

4.2 Benefit of Generics in Collections Framework

This avoids ClassCastException at Runtime because you will get the error at compilation. Also, Generics make code clean since we don’t need to use casting and instanceof operator. It also adds up to runtime benefit because the bytecode instructions that do type checking are not generated.

5. References

https://www.javatpoint.com/java-arraylist

https://www.geeksforgeeks.org/priority-queue-class-in-java-2/

http://tutorials.jenkov.com/java-util-concurrent/linkedblockingqueue.html

https://howtodoinjava.com/java/collections/java-priorityblockingqueue/

https://www.baeldung.com/java-priority-blocking-queue

http://tutorials.jenkov.com/java-collections/list.html

http://tutorials.jenkov.com/java-util-concurrent/blockingqueue.html

https://techvidvan.com/tutorials/java-collection-framework/

https://www.tutorialspoint.com/java/java_hashtable_class.htm

https://www.geeksforgeeks.org/java-util-dictionary-class-java/

https://www.codejava.net/java-core/collections/java-navigablemap-and-treemap-tutorial-and-examples

https://knpcode.com/java/collections/java-collections-framework-tutorial/

https://www.javamadesoeasy.com/2015/04/map-hierarchy-in-java-detailed-hashmap.html

https://www.javatpoint.com/collections-in-java

https://www.softwaretestingmaterial.com/map-in-java/

https://www.softwaretestingmaterial.com/collections-framework-in-java/

https://www.quora.com/Why-do-we-need-collections-in-Java

https://crunchify.com/what-is-java-collections-framework-benefits-of-collections-framework/

https://stackoverflow.com/questions/2497134/what-is-the-need-of-collection-framework-in-java